# How do you use prim's algorithm to find a spanning tree of a connected graph with no weight on its edges?

Prims Algorithm is used when the given graph is dense , whereas Kruskals is used when the given is sparse,we consider this because of their time complexities even though both of them perform the same function of finding minimum spanning tree.

ismailahmed syed

### What is krushkal algorithm?

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example…

### Prove that a graph G is connected if and only if it has a spanning tree?

Proving this is simple. First, you prove that G has a spanning tree, it is connected, which is pretty obvious - a spanning tree itself is already a connected graph on the vertex set V(G), thus G which contains it as a spanning sub graph is obviously also connected. Second, you prove that if G is connected, it has a spanning tree. If G is a tree itself, then it must "contain" a spanning tree…

### What is the difference between Prims algorithm Kruskals algorithm and dijktras algorithm?

Well, Dijkstra algorithm is a way to find a path with minimum weight between 2 vertices's in a weighted graph. Prims And Kruskal algorithms are algorithms used to find the a path with minimum weight in a way that you can go from any vertex to another. Prims And Kruskal Algorithms are some how the same and both are greedy algorithms, but Prims insiste that the next edge to be chosen must be an edge…

### What are difference between Primes algorithm and Krushkals algorithm for finding the minimum spanning tree of a graph?

"What are difference between Prim's algorithm and Kruskal's algorithm for finding the minimum spanning tree of a graph?" Prim's method starts with one vertex of a graph as your tree, and adds the smallest edge that grows your tree by one more vertex. Kruskal starts with all of the vertices of a graph as a forest, and adds the smallest edge that joins two trees in the forest. Prim's method is better when * You…

### Define walk path and connected graph in an algorithm?

A "walk" is a sequence of alternating vertices and edges, starting with a vertex and ending with a vertex with any number of revisiting vertices and retracing of edges. If a walk has the restriction of no repetition of vertices and no edge is retraced it is called a "path". If there is a walk to every vertex from any other vertex of the graph then it is called a "connected" graph.

### What is the difference between Dijkstra's algorithm and Bellman-Ford's algorithm?

Both of these functions solve the single source shortest path problem. The primary difference in the function of the two algorithms is that Dijkstra's algorithm cannont handle negative edge weights. Bellman-Ford's algorithm can handle some edges with negative weight. It must be remembered, however, that if there is a negative cycle there is no shortest path.

### How is looping problem solve by switches and by routers?

The looping problem solved by switches by using an algorithm named Spanning Tree algorithm and Routers by using Dijkstra's shortest path algorithm. Switches handle the looping problem through making spanning tree. Switches: Switching handle the looping problem by building Spanning Tree. Spanning Tree Algorithm: There are possibilities in the extended LANs having loop like structure. Bridges and switch must be able to correctly handle loops. This addressed by having the bridge or switch run a…

### What is the difference between Dijkstra and Prim's algorithm?

Dijkstra's algorithm is almost identical to that of Prim's. The algorithm begins at a specific vertex and extends outward within the graph, until all vertices have been reached. The only distinction is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to the current vertex. More simply, Dijkstra's algorithm stores a summation of minimum cost edges whereas Prim's algorithm stores at most one minimum cost…

### What solid figure has 4 faces 9 edges and 6 vertices?

It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires that Faces + Vertices = Edges + 2 It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which requires that Faces + Vertices = Edges + 2 It is not any kind of simply connected solid figure because it does not satisfy the Euler characteristic which…

### What are the properties of a tree?

1. There is one and only one path between every pair of vertices in a tree, T. 2. A tree with n vertices has n-1 edges. 3. Any connected graph with n vertices and n-1 edges is a tree. 4. A graph is a tree if and only if it is minimally connected. Therefore a graph with n vertices is called a tree if 1. G is connected and is circuit less, or 2. G…

### Will either kruskal or prim's algorithm work on negative edge graph?

The correctness of either Prim's or Kruskal's algorithm, is not affected by negative edges in the graph. They both work fine with negative edges. The question boils down to "Does a Priority Queue of numbers work with negative numbers?" because of the fact that both Prim's and Kruskal's algorithm use a priority queue. Of course -- as negative numbers are simply numbers smaller than 0. The "<" sign will still work with negative numbers.