Network Algorizmz

Question 1

Kruskal’s algoritghm?

Answer 1

1) List the edges in order of weight, smallest first
2) Choose the edge with the smallest weight
3) From the remaining edges, choose the one with the smallest weight, providing no cycle is formed
4) Repeat step 3 until all verticies are added

Question 2

Prim’s algorithm?

Answer 2

1) Choose a start vertex
2) Connect the start vertex to the nearest new vertex by adding the shortest edge
3) From any node added so far, add the smallest edge that adds a new vertex
4) Repeat 3 till all veritcies connected

Question 3

Prim’s algorithm via matrix?

Answer 3

1) Choose a start vertex, label the column corresponding with that vertex with a 1 and delete that row
2) look at columns numbered so far. circle the smallest undeleted entry and read off the vertex for the row
3) Label the column corresponding with this vertex with the next number and delete the row
4) Repeat till all rows deleted