hello world "HA! bet your all sick of that ain't cha!"
I have an assignment to implement Prims algorithm using a graph ADT we've made prior.
below is my current pseudo code:
create a variable smallest " smallest =9999"
create a variable for current smallest edge "default set yo the first edge we use aka graph[1]"
for(every vertex in vertexList) {
for(every vertex in adjacency lists "aka, every vertex adjacent to vertex"){
if(vertex <smaller) current vertex = smallest;
smallest edge = current edge
}
}
}
DELETE SMALLEST EDGE FROM GRAPH;
add smallest edge to edge return list;
add new vertex associated with edge to vertex list;
if vertex list is = to total number of edges
return edgelist
the problem I am having is the DELETE SMALLEST EDGE from graph bit, I dont have a function to handle this, that is, I dont have a function that will delete a refference to this node in the adjacency lists of other vertexs.
ex:
I take away edge AB and store it in a list, HOWEVER, I cannot think of a way to delete A from B's agency list. what should I do?
Copyright © 2024 QUIZLS.COM - All rights reserved.
Answers & Comments
Verified answer
Read http://en.wikipedia.org/wiki/Prim%27s_algorithm#De... if you are not 100% sure about the algorithm. You don't actually have to delete any edges.
let V be the set of vertices
let Vt be the set of vertices in the tree (initially empty)
add a random vertice to Vt
while Vt does not equal V
find pair of vertices u, v where u is in Vt, v is not in Vt, and cost(u, v) is minimal
add v to Vt
To find the pair of vertices with cheapest edge:
let minCost = infinity
let newVertex = undefined
for each vertex u in Vt
for each vertex v in u's neighbours
if cost(u, v) is less than minCost AND v is not in Vt
minCost = cost(u, v)
newVertex = v
return newVertex