0
$\begingroup$

An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one. Got the first one but not the second.

What is the modern standard way to search a graph (assume undirected) given no other context? I've a notion that it might have something to do with Dijkstra's algorithm but IDK what. It makes sense that one way is to simply traverse the graph until you find the item you are looking for but it sure doesn't seem optimal.

$\endgroup$
3
  • 1
    $\begingroup$ This question is far too broad: one can write whole book chapters about this (e.g., chapter 3 of Russell and Norvig's Artificial Intelligence: A Modern Approach). $\endgroup$ Mar 31 '15 at 18:07
  • $\begingroup$ Actually, I think it was answered pretty well. It basically indicates that I still have a lot to learn about graphs. $\endgroup$
    – user447607
    Mar 31 '15 at 20:55
  • 2
    $\begingroup$ Wikipedia's list of graph search algorithms is a good place to start looking. $\endgroup$ Mar 31 '15 at 22:29
0
$\begingroup$

Interviewer was probably fishing for words like: preorder, inorder, postorder traversal and depth-first versus breadth-first. I am thinking of traversal as simply having an iterator over the graph that returns some vertices and edges in some particular order. As Richerby says, you could fill books with all the various ways that this could happen.

As for searching graphs, if they didn't mean traversal; then they probably meant searching for subsets efficiently: If a graph is known to have implicit structure (ie: find all edges in: 192.168.4.0/24 -> 10.0.3.2/24 by hour, etc), then various kinds of searches over src/dst/time are often possible. Facebook/Twitter, etc are utterly gigantic graphs of "at time T, A says X to B".

$\endgroup$
1
  • 1
    $\begingroup$ What do pre-/in-/post-order mean when the graph isn't a tree? There are many more search algorithms than just DFS and BFS. And I'm not sure why you're invoking IPv4 addresses or seaching geometrical areas/volumes in a question about searching in graphs. $\endgroup$ Mar 31 '15 at 22:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.