CODEWITHSUNDEEP
breadth-first-searchdirected-graph
Yashwanth CB
Yashwanth CB

Reputation: 194

breadth first traversal directed vs undirected graph

how does bfs on directed and undirected graph differ in implementation.

i found the following pseudocode on web. i am ok with undirected graph. but can't figure out how to implement it for directed graph.

 frontier = new Queue()
  mark root visited (set root.distance = 0)
  frontier.push(root)
  while frontier not empty {
     Vertex v = frontier.pop()
    for each successor v' of v {
    if v' unvisited {
        frontier.push(v')
        mark v' visited (v'.distance = v.distance + 1)
    }
    }
  }

Upvotes: 5

Views: 2516

Answers (1)

Codor
Codor

Reputation: 17605

The implementation in pseudocode is the same, except that the notion of successor would mean neighbor for an undirected graph but child (or similar) for a directed graph.

Upvotes: 2

Related Questions