Full Question:
Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.
Breadth-First Search (BFS)
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic algorithm. From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed"
*must see Depth-First Search (DFS) to compare and understanding graph traversal deeply. Interviewer may ask DFS after BFS.
Below pseudo code shows the algorithm of BFS
Describe the Algorithm for a Breath-First Graph Traversal.
Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.
Breadth-First Search (BFS)
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic algorithm. From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed"
*must see Depth-First Search (DFS) to compare and understanding graph traversal deeply. Interviewer may ask DFS after BFS.
Below pseudo code shows the algorithm of BFS
algorithm BFS(x)
visit(start node)
queue <- start node
WHILE queue is not empty DO
x <- queue
FOR each y such that (x,y) is an edge and y has not been visited yet DO
visit(y)
queue <- y
END
END
visit(start node)
queue <- start node
WHILE queue is not empty DO
x <- queue
FOR each y such that (x,y) is an edge and y has not been visited yet DO
visit(y)
queue <- y
END
END
Describe the Algorithm for a Breath-First Graph Traversal.