CODEWITHSUNDEEP
algorithmgraphiterationshortest-path
Verilocos
Verilocos

Reputation: 115

How to visit vertices in undirected graph

What are proper algorithms to visit all vertices of a undirected graph, from an arbitrary position? For example, given the following graph with 7 vertices, starting from #6:

enter image description here

There are many possible sequences: 67645321, 676421235, 6453212467, ...

How to iterate the vertices with shortest path (the first one)? Thanks.

Upvotes: 1

Views: 421

Answers (2)

pentadecagon
pentadecagon

Reputation: 4847

  1. Find the node furthest away from your starting node, that would be the node where the shortest path from your starting node has a maximum length. Call this node Q.

  2. Calculate the distance from Q to all other nodes in your graph. Call this distance D1, D2, ....

  3. Start walking at the starting node.

  4. Always walk to the nearest unvisited node.

  5. If there are more than one unvisited nodes within the same distance, i.e. if there are multiple unvisited nodes directly connected to the current one, walk to the one where Di is largest. Always walk away from Q.

Given your example graph you find Q=1 and D1=0, D2=1, D3=2, D4=2, D5=3, D6=3, D7=4. Starting from 6 you have 4 and 7 as options, and you pick 7 because D7>D4. From there you go to 4, because that's the nearest unvisited node. Then to 5, because D5>D2. Finally 3, 2, 1.

This algorithm is not perfect, and it needs some fine-tuning. For example, when picking Q in step 1. you could end up with node 3, because it has the same distance from 6, so you need some additional heuristic to resolve ties, maybe in favor of nodes where the fewest paths go. So you won't get a perfect result, but I'd say you will get something reasonable.

Upvotes: 1

Ken Cheung
Ken Cheung

Reputation: 1808

Follow up with my comment above,

1-2-3
  | |
  4-5
  |
  6-7

Sort by node value, smaller value go first, which results:

6-+-4-+-2-+-1
  `-7 `-5 `-3

Transverse the tree:

6-4-2-1-2-3-2-4-5-4-6-7

Some more optimization can be made, e.g. for each node keep the 'depth' or weight of each 'child', transverse the shallow child / light child first.

6-+-(5)-4-+-(3)-2-+-(1)-1
  `-(1)-7 `-(1)-5 `-(1)-3

Thus we transverse as below:

6-7-6-4-5-4-2-1-2-3

May have more methods to optimize, good luck!

Upvotes: 1

Related Questions