How to construct BFS-suitable data structure for adjacency list?

Question

Interview question on building and searching an adjacency tree, but I've never worked with them before, so I'm not sure where to begin.

I have a file containing data like:

2 13556 225 235
225 2212 226
2212 8888 2213
8888 144115 72629 141336 8889 146090 129948 167357
144115 160496 163089 144114 144116
...

formatted as such:

<parent node> <child node> [ <child node> [ …] ]

Every edge has length 1.

I then need to calculate the shortest path between two of the nodes (the two are specified in the question). Then, I need to provide the estimated complexity in big-O notation.

The latter I can probably fudge, though I've never even heard of it until now and wikipedia doesn't help me much in terms of understanding how to break down a search function into big-O, but I'll worry about that later (unless someone has a good link they could share).

My concern now is trying to model this data and then search it for the shortest path. Like I said, I've never worked with this kind of structure before so I'm kind of at a loss as to where to even begin. I found another question on adjacency lists here, but it doesn't appear to be quite what I'm looking for, unless I'm just totally missing the point. Seems to me, the input data would need to be re-organized to satisfy the structure used in that question, whereas I'm reading my data from a file so I would think I'd need to traverse every node and list of nodes to determine if I have already entered a parent and that could take a long time, potentially. I also don't see how I'd create a bfs search using that structure either.

There are lots of examples of searching out there, so I can likely sort out that part, but any help in getting a data model started that would be suitable for loading from the data file and suitable for a bfs search (or, if there's a better search option out there, please school me), would be of great help.

Answer 1

You'll like be storing this data in a HashTable<int, List<int>> (Dictionary) (Links), key being int (NodeID) and value being List<int>, where these are the possible destinations from the node which is the key.

You'll need to have another HashTable<int, int> (ShortestPathLastStep), which will store two NodeIDs. This will represent the last step in the shortest path to arrive at a given node. You need this to be able to play back the shortest path.

To perform a BFS (Breadth-First-Search) you'll use a Queue<int> (bfsQueue). Push the start node (given in your question) onto the queue. Now execute the following algorithm

-- currentNodeID = pop bfsQueue
---- children = Links[NodeID]
------ foreach (childNodeID in children)
--------- if (childNodeID == destinationNodeID)
----------- exit and playback shortest path
----------if (!ShortestPathLastStep.contains(childNodeID))
------------ ShortestPathLastStep.Add(childNodeID, currentNodeID);
----------bfsQueue.Push(childNodeID);
----------goto first line

This solution assumes traveling between any two nodes is a constant cost. It is ideal for BFS because the first time you arrive at the destination you will have taken the shortest path (not true if links have variable length). If links are not constant length you'll have to add more logic when deciding to overwrite the ShortestPathLastStep value, you won't be able to exit until your queue is EMPTY and you'll only be pushing nodes onto the queue if you've never been to the node (it won't exist in the short path list) or you've discovered this new way of arriving there is shorter than the last way of getting there (now you'll have to recalculate shortest distances for the nodes you can get to from this node).