문제

I generated this Minimum Spanning Tree using Kruskal algorithm and I have a hard time generating paths between two nodes. Can someone help me with pseudocode? I tried using Adjacency List and Adjaceny matrix

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------
도움이 되었습니까?

해결책

If you just want any path between two nodes, a Breadth First Search would do, and would generate the shortest path (because its a minimum spanning tree).

다른 팁

Spanning trees, by definition, have no cycles (or loops), so at most you can only have one path (i.e. not "paths", plural) between two nodes.

Perhaps I'm not understanding the question. Are you trying to find how two given nodes are connected in your tree?

If so, it sounds to me like the simplest brute force on this, where you would just follow from one point along its possible edges, perhaps by pushing and popping possibilities from a stack, would be worst-case O(Edges) run time, which would be trivial compared to Kruskal's Algorithm. Do you need something faster?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top