BFS from an input file

[coder47]

I need to create a BFS traversal on a graph from an input file given in this format.

4
1:2 3 4
2:4
3:4
4:

The first line is the number of nodes in the graph. The following lines are the node followed by a colon and the adjacent nodes. I need to print an output that displays the output list, the parent of each node, and the distance of each node to the starting node. Such as

D=1 2 3 4
1.p=nil, 2.p=1, 3.p=1, 4.p=1
1.d=0, 2.d=1, 3.d=1, 4.d=1

The BFS function will take the starting node as a parameter. I am having troubling figuring out how to read in the file and and construct the graph so that I can make the BFS function for the graph. The colon is throwing me off. I am not sure how to differentiate in my program that the values after the colon are stored as different information than the value before the colon. Once I have the graph constructed I have an idea how to do the traversal.

[Duthomhas]

The colon is relatively unimportant. The newline matters more. Use std::getline() to read the lines, and use a std::istringstream to get the numbers. After reading the first number, use something like myss.ignore( s.length(), ':' ) to get rid of the colon, then use a loop to get every target vertex.

You can store the directed graph any way you want. A simple two-dimensional array would do. Make it big, and only use the cells you need.

The BFS algorithm is pretty straight-forward. Once you decide on a data structure you'll use for the graph and read it from file, then you'll have a better idea how to write the BFS.

Also, don't forget that you'll need to keep track of which nodes have been visited, since your assignment doesn't appear to specify that the graph must be acyclic.

Hope this helps.