answersLogoWhite

0


Best Answer

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.

User Avatar

Wiki User

โˆ™ 2011-03-16 03:39:54
This answer is:
๐Ÿ™
0
๐Ÿคจ
0
๐Ÿ˜ฎ
0
User Avatar
Study guides

Software and Applications (non-game)

20 cards

What is a programming language

What does DOS stand for

What is a software that is distributed for free

What is application software

โžก๏ธ
See all cards

Software and Applications (non-game)

21 cards

What is a programming language

What does DOS stand for

What is a software that is distributed for free

What is application software

โžก๏ธ
See all cards

Software and Applications (non-game)

23 cards

What is a programming language

What does DOS stand for

What is a software that is distributed for free

What is application software

โžก๏ธ
See all cards

Add your answer:

Earn +20 pts
Q: Will either kruskal or prim's algorithm work on negative edge graph?
Write your answer...
Submit
Related questions

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 of a greedy algorithm.


What is the complexity of kruskal's minimum spanning tree algorithm on a graph with n nodes and e edges?

o(eloge)


What is the difference between prims and kruskal's algorithm?

Prims select vertex to build minimum spanning tree....kruskal's select edge at a time.... Prims work perfect when lot of edges in graph .........whereas kruskal's want sorted edges... Prims O(E+VlogV) Kruskal O(ElogV)


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 with minimum weight connected to the current fringe whereas kruskal says that the next edge to be chosen dosent have to be connected to the current set of edges.


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 can only concentrate on one tree at a time * You can concentrate on only a few edges at a time Kruskal's method is better when * You can look at all of the edges at once * You can hold all of the vertices at once * You can hold a forest, not just one tree Basically, Kruskal's method is more time-saving (you can order the edges by weight and burn through them fast), while Prim's method is more space-saving (you only hold one tree, and only look at edges that connect to vertices in your tree).


What is the difference between Prims algorithm and kruskals algorithm for finding the minimum spanning tree of a graph?

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 with minimum weight connected to the current fringe whereas kruskal says that the next edge to be chosen dosent have to be connected to the set of vertices's Already Chosen.


What are difference between A and AO algorithm?

the main difference between the A*(A star) and AO*(AO star) algorithms is that A* algo is a OR graph algorithm and AO* is a AND-OR graph algorithm. In OR graph algorithm it just find only one solution (i.e either OR solution means this OR this OR this). But in the AND-OR graph algo it find more than one solution by ANDing two or more branches. for more details on AND-OR graph &amp; OR graph please refer the book "Artificial Intelligence" by Elaine Rich &amp; Kevin Knight. -AAA


What is prim algorithm?

Prim's algorithm is a 'graph algorithm' which uses a 'greedy approach' to find the minimum spanning tree of a graph.


Difference between a and ao?

the main difference between the A*(A star) and AO*(AO star) algorithms is that A* algo is a OR graph algorithm and AO* is a AND-OR graph algorithm. In OR graph algorithm it just find only one solution (i.e either OR solution means this OR this OR this). But in the AND-OR graph algo it find more than one solution by ANDing two or more branches. for more details on AND-OR graph &amp; OR graph please refer the book "Artificial Intelligence" by Elaine Rich &amp; Kevin Knight.


What is difference between resource allocation graph and resource allocation graph algorithm?

The graph is the the actual picture that shows the resource allocation; the algorithm is the method used to produce that graph.


Which is the best shortest path algorithm?

dijkstra's algorithm (note* there are different kinds of dijkstra's implementation) and growth graph algorithm


What is the difference between Prims algorithm and Dijkstras algorithm?

Both Prim's and Dijkstra's algorithm are manipulating with graphs but they have different roles. Dijkstra's algorithm is used to find the shortest path between any two nodes in a weighted graph while the Prim's algorithm finds the minimum spanning tree of a graph.


What is Dijkstra's algorithm?

Dijkstra's algorithm is a greedy algorithm used to determine the shortest path between two nodes in a graph. The algorithm is central to satellite navigation systems.


An algorithm to find whether a directed graph is connected or not?

You can use a The Depth-First Search algorithm.


What is a divergent bar graph?

A graph with a data spread which is both positive and negative can be displayed on a divergent bar graph. These could be constructed on either the x or y axis. Most of you will have seen such a graph which has been drawn on a population pyramid.


What is a negative cycle in Graph?

In a weighed graph, a negative cycle is a cycle whose sum of edge weights is negative


When you graph a quadratic function what will the shape of the graph be?

A parabola. An arch opening either north or south of the x-axis depending on the sign of the coefficient (negative opens down, positive opens up).


What is the slope of negative 8?

Slope cannot be determined by one number. You need either an equation, or two points that can be put on a graph.


How would a graph of negative and positive acceleration differ?

This depends on what the graph represents. If it is a graph of velocity on the vertical and time on the horizontal, then if acceleration is at a constant rate, the graph will be a straight line with positive slope (pointing 'up'). If acceleration stops, then the graph will be a horizontal line (zero acceleration or deceleration). If it is deceleration (negative acceleration), then the graph will have negative slope (pointing down).


Program in c to implement breath first search in a graph?

Who's your teacher? There is supposed to be a general algorithm breadth first search. You can use that algorithm. Programming languages do not matter, its the algorithm that counts. You can use any language you like. Its just a matter of learning C. Breadth first search algorithm: http://renaud.waldura.com/portfolio/graph-algorithms/ Hope this helps. Who's your teacher? There is supposed to be a general algorithm breadth first search. You can use that algorithm. Programming languages do not matter, its the algorithm that counts. You can use any language you like. Its just a matter of learning C. Breadth first search algorithm: http://renaud.waldura.com/portfolio/graph-algorithms/ Hope this helps.


How can you design an algorithm to check if a given graph is connected?

Use a simple DFS/BFS traversal. If you have gone through all nodes, the graph is connected.


How is declaration represented on a velocity time graph?

Deceleration (negative acceleration) is represented by a negative slope on a velocity-time graph.


What happends to the graph of a line when the slope is negative?

A straight line graph with negative slope slants downward from left to right.


Is a negative slope on the velocity vs time graph indicates that the objects is not moving?

A negative slope, called 'a negative gradient' by the intelligent, on a Velocity-Time Graph shows the deceleration of the object. This negative gradient is the positive deceleration and the negative acceleration.


A negative slope on the velocity vs. time graph indicates a negative acceleration?

True