Graph Traversal BFS & DFS | Minimum Spanning Tree | Kruskal & Prims | Data Structure & Algorithm

TRAVERSING A GRAPH

Breadth-First Search The general idea behind a breadth-first search beginning at a starting node A is as follows. First we examine the starting node A. Then we examine all the neighbors of A. Then we examine all the neighbors of the neighbors of A. And so on. Naturally, we need to keep track of the neighbors of a node, and we need to guarantee that no node is processed more than once. This is accomplished by using a queue to hold nodes that are waiting to be processed. and by using a field STATUS which tells us the current status of any node. The algorithm follows. Algorithm BFS: This algorithm executes a breadth-first search on a graph G beginning at a starting node A. 1. Initialize all nodes to the ready state 2. Put the starting node A in QUEUE and change its status to the waiting state 3. Repeat Steps 4 and 5 until QUEUE is empty: 4. Remove the front node N of QUEUE. Process N and change the status of N to the processed state 5. Add to the rear of QUEUE all the neighbors of N that are in the steady state (STATUS = I). and change their status to the waiting state. (End of Step 3 loop. ) 6. Exit. Depth-First Search The general idea behind a depth-first search beginning at a starting node A is as follows. First we examine the starting node A. Then we examine each node N along a path P which begins at A; that is, we process a neighbor of A, then a neighbor of a neighbor of A, and so on. After coming to a "dead end," that is, to the end of the path P, we backtrack on P until we can continue along another, path P. And so on. The algorithm is very similar-to the breadth-first search except now we use a stack instead of the queue. Algorithm DFS: This algorithm executes a depth-first search on a graph G beginning at a starting node A. 1. Initialize all nodes to the ready state 2. Push the starting node A onto STACK and change its status to the waiting state 3. Repeat Steps 4 and 5 until STACK is empty. 4. Pop the top node N of STACK. Process N and change its status to the processed state 5. Push onto STACK all the neighbors of N that are still in the ready state and change their status to the waiting state (End of Step 3 loop.] 6. Exit. SHORTEST PATH ALGORITHMS In this section, we will discuss algorithm to calculate the shortest path between the vertices of a graph G. Minimum spanning tree : It uses an adjacency list to find the shortest path. A spanning tree of a connected, undirected graph G is a sub-graph of G which is a tree that connects all the vertices together. A graph G can have many different spanning trees. We can assign weights to each edge (which is a number that represents how unfavorable the edge is), and use it to assign a weight to a spanning tree by calculating the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) is defined as a spanning tree with weight less than or equal to the weight of every other spanning tree. In other words, a minimum spanning tree is a spanning tree that has weights associated with its edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum. Prim's Algorithm Prim's algorithm is a greedy algorithm that is used to form a minimum spanning tree for a connected weighted undirected graph. In other words, the algorithm builds a tree that includes every vertex and a subset of the edges in such a way that the total weight of all the edges in the tree is minimized. . Algorithm Prims Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END Of LOOP] Step 5: EXIT Kruskal's Algorithm Kruskal's algorithm is used to find the minimum spanning tree for a connected weighted graph. The algorithm aims to find a subset of the edges that forms a tree that includes every vertex. The total weight of all the edges in the tree is minimized. However, if the graph is not connected, then it finds a minimum spanning forest. Note that a forest is a collection of trees. Similarly, a minimum spanning forest is a collection of minimum spanning trees. Kruskal's algorithm is an example of a greedy algorithm, as it makes the locally optimal choice at each stage with the hope of finding the global optimum. Kruskal Algorithm Step 1: Create a forest in such a way that each graph is a separate tree. Step 2: Create a priority queue Q that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY Step 4: Remove an edge from Q Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest (for combining two trees into one tree). ELSE Discard the edge Step 6: END For more details click here