The usage of graph traversal algorithm

Question

I am reading the materials related to graph in Data Structures and Algorithms in C++ 4e(By Adam Drozdek). In his implementation of Graph Breadth First Search, the psuedo code is like:

BFS():
    for all vertices u
        num(u) = 0
    edges = null
    i = 1
    while there is a vertex v such that num(v) is 0
        num(v)++
        enqueue(v)
        while queue is not empty
            v = dequeue()
            if num(u) is 0
                num(u) = i++
                enqueue(u)
                attach edge(v,u) to edges
    output edges

Basically, in the implementation of graph, we already keep a set of all vertices and a set of all edges. In BFS, the algorithm first enumerate every vertex not visited in this set to traverse the complete graph.

My question is: since we already store all the vertex in a set, we can loop through the set to operate on a particular vertex without using BFS algorithm. Why do we need a graph traversal algorithm and what is main use?

Bernhard Barker · Accepted Answer · 2014-04-11 07:10:46Z

2

There are many uses for BFS and DFS...
To give you an idea for BFS:

You have a graph representing a social network and want to make friend suggestions for a particular user. Then, you do a BFS. The closer the vertices (people), the better rank in the friends suggestion list. (If the number of users is large, it makes sense to stop at a distance of 3 and not do the BFS on the entire graph).
Solution space searching. Extremely useful when the solution space is infinite. (see Game Trees)
Shortest paths (if the edges have the same weight and there are no loops). Dijkstra adapted it to work for variable weights (see Dijkstra's algorithm).

edited Apr 11, 2014 at 7:10

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

answered Mar 27, 2014 at 14:45

Radu

3844 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vschon Over a year ago

So the objective of traversal algorithm is not mainly on visiting some vertices, but on exploring the relationship among different vertices, right?

Radu Over a year ago

Could say so. However, when you visit vertices you could also call some function. Maybe I want to assign a priority to all Vertices, the closer they are, the greater the priority. Thus, I do a BFS and call a function on each node visit. This function assigns the priority. When you get to trees, you will see that there are multiple applications to the various tree-traversals too (pre-order, in-order and post-order).

Codor · Accepted Answer · 2014-03-27 14:49:47Z

1

For instance, typically DFS is implicitly used when a tree is traversed recursively.

answered Mar 27, 2014 at 14:49

Codor

17.6k9 gold badges32 silver badges59 bronze badges

3 Comments

Vschon Over a year ago

Yes, I understand that tree inorder and preorder traversals is the sames as DFS. I am just confused because actually in the implementation of graphs, actually the vertex and edges are stored in an array, not like tree nodes using pointers to link to each other. In tree, we need the traversal literally to visit every node. However, in graph, if we need to visit some node, it seems looping through the vector that contains the vertices is more straightforward. I guess the graph traversal algo is more used to detect the relationship between vertices instead of just purely visiting the nodes. (?)

Radu Over a year ago

Well, you could also do that in a tree (you store all the addresses of the nodes in an array and then you have access to any of them in constant time). However, visiting a node is not the same thing as having access to it. It's more a matter of how you get there. You, as the programmer, might have access to all vertices, but it might happen that you are not able to "visit" a vertex because it is isolated.

Vschon Over a year ago

I tried a toy program to find the maze paths using graph traversal algorithms and now have a better understanding of its usage. Thanks a lot. Right, visit is very different from getting the physical access to..

Collectives™ on Stack Overflow

The usage of graph traversal algorithm

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related