Can Breadth First Search be used on Directed Acyclic Graph?

1
votes

Can Breadth First Search be used on Directed Acyclic Graph?

For example, you start with the root node (say it has 3 connected nodes, edges all pointing towards them from the root), following BFS, you visit the first connected node from the root following the directed edge, and you got to come back to the root node and visit the second connected node if it were an undirected graph, but you can't in the case of directed graph, so I assume BFS cannot be used on Directed Acyclic Graph?

Also,a line of nodes as such 1 -> 2 -> 3 -> 4 can be considered as a Directed Acyclic Graph, correct?

Thank

2
algorithmbreadth-first-search
BFS can be used on any graph by coloring the visited nodes. - Nir Alfasi
@alfasin Could you explain why my assumption is wrong based on what I explained? - user3466314
Because in BFS you'll queue all the neighbours of root and then start pop'ing them. The fact that there is no edge pointing back is irrelevant. - Nir Alfasi
BFS is used to find the shortest path from one node to any other node in a graph. This has nothing to do with finding a simple path that visits every node. And second, what is the definition of root in DAG ? a node that has only "out" edges ? what if there are few such nodes ? - Nir Alfasi
@user3466314 What do you mean by "can it be used" exactly? What are you trying to achieve? Shortest path between two nodes or...? Yes, BFS can be used to find the shortest path between two nodes in a DAG. - ggorlen

2 Answers

0
votes

Short answer : Yes

To respond more precisely to your question, if there is no edge from a given node pointing to a root then you don't "have to" go back to the root, like others said in the comments.

The fact that the graph has cycles or not is not important because in BFS algorithms a node is supposed to be marked when you visit it. The mark is then used to not enqueue the node a second time (i.e to visit it only once), so the cycle is some how broken. Just check the pseudo-code on Wikipedia.

An yes the "line of node" you mentioned is a DAG, but a very special one.

P.S : Sorry to dig up this question but I asked it to myself, searched the internet, saw it, keep searching and find some answers, so I thought it could help somebody else in the future.

-1
votes

1 -> 2 -> 3 -> 4 is a DAG

BFS means breath fast search. if u start bfs from a node u, every node which are reachable from u will be found but those nodes that are not reachable from u are not found.

example G (V,E ) a graph v={1,2,3,4} E={(1,2),(1,3),(4,1)} if u run bfs from node 1 ,node 2 and 3 will be discovered but 4 will be undiscovered

but if u run bfs from 4 every node will be discovered

So if u know the topological sorting of the DAG u can run bfs from the nodes in the topological order every node will be discovered and their level will be calculated correctly.