How to get the MAX level(depth) of a vertex in a b

问题:

I am new to boost graphs and graph theory in general. As it happens my limited knowledge on terminology of graph algorithms is making things difficult for me. Anyways here is what I am trying to do.

I am using boost::adjacency_list and let's say I have a vertex

struct Node {
    int level;
}

Now I have a whole graph constructed and I want to find the level of each node. Level for me means here the maximum depth of a node from the root. For example consider the graph (assuming 118 is the root node)

118 -> 122
118 -> 120
122 -> 120
122 -> 121
121 -> 125
121 -> 123
123 -> 125
125 -> 124

then level of 122 is 1, 120 is 2, 121 is 2, 123 is 3, 125 is 4, and 124 is 5.

Is there any algorithm in boost that lets me do this. My bet is that it is boost::bredth_first_visit. But I am not sure how to use it correctly so that it puts the correct values in Node.level while visiting.

I found another post on stack overflow on similar issue and this was kind of the solution (it is not compiling for me.)

typedef boost::property_map<TaskGraph, boost::vertex_color_t>::type color_map_t;
color_map_t colorMap; //Create a color map
boost::breadth_first_visit(graph, *boost::vertices(graph).first, boost::color_map(colorMap));

What I want to do is something like

boost::breadth_first_visit(graph, *boost::vertices(graph).first, /*What goes here so that Node.level gets the level*/);

Thanks for the help and sorry for the terminology. Not sure if level is the correct term in graph theory.

回答1:

Take a look at Dijkstra's Algorithm. There is no simple way to do this, boost::breadth_first_visit will traverse every node, but keep in mind you will still have to calculate the "levels" which I will refer to as costs.

Say you have this graph:

   a->b
   b->c
   a->c

What is the "level" of C, two or three? Here you would probably want to use the term "cost" instead. Here, the least cost option is 2. In this case, if each C has two parent pointers, you need to traverse each parent pointer recursively back up the the starting node, incrementing your cost along the way.

That would look like this:

   cost=1
   c->b
       cost=2
       b->a
           cost=3 
   c->a
       cost=2

回答2:

If what you are looking for is the longest path (you say "maximum cost") you should be aware of the following:

In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP.

From Wikipedia, longest path problem.

If your graph is a tree (i.e. if it has no cycles) then the longest path is equal to the shortest path as there is only one path between any pair of nodes, and you can use Breadth First Search, as pointed out by the other answers.