We have seen the differences as well as the applications of both the techniques. In the last couple of tutorials, we explored more about the two traversal techniques for graphs i.e. DFS is widely used in Topological sorting. In the computer science field, we use it mostly for resolving symbol dependencies in linkers, data serialization, instruction scheduling, etc.

Topological Sorting: We use topological sorting when we need to schedule the jobs from the given dependencies among jobs.

Minimum Spanning Tree And Shortest Path: DFS traversal of the un-weighted graph gives us a minimum spanning tree and shortest path between nodes.

The contents of the stack give the path between x and y. We start with vertex x and then push all the vertices on the way to the stack till we encounter y.

Pathfinding: Given two vertices x and y, we can find the path between x and y using DFS.

Hence DFS is used to detect the cycles in a graph.

Detecting Cycles In The Graph: If we find a back edge while performing DFS in a graph then we can conclude that the graph has a cycle.

Useful in finding the shortest path between two nodes. The nodes are explored depth-wise until there are only leaf nodes and then backtracked to explore other unvisited nodes.īFS is performed with the help of queue data structure.ĭFS is performed with the help of stack data structure. The nodes are explored breadth wise level by level. Now let us look into the differences between the two. So far we have discussed both the traversal techniques for graphs i.e. To get the same sequence, we might want to insert the vertices in the reverse order. As the stacks follow LIFO order, we get a different sequence of DFS. The difference in output is because we use the stack in the iterative implementation. We use the same graph that we used in our recursive implementation. Output of Iterative Depth-first traversal: display the item or node only if its not visitedĬout << 'Output of Iterative Depth-first traversal: ' Void Graph::DFSUtil(int s, vector &visited) traverses all not visited vertices reachable from start node s Void addEdge(int v, int w) // add an edge to graph initially none of the vertices are visited Void DFSGraph::DFS_util(int v, bool visited)įor(i = adjList.begin() i != adjList.end() ++i)

Void DFS_util(int v, bool visited) // A function used by DFSĪdjList.push_back(w) // Add w to v’s list. Let’s implement the DFS traversal technique using C++. If we observe the given graph and the traversal sequence, we notice that for the DFS algorithm, we indeed traverse the graph depth-wise and then backtrack it again to explore new nodes. Now the stack is empty and the visited list shows the sequence of the depth-first traversal of the given graph. Its adjacent node 0 is already visited, hence we ignore it. Node 4 has only node 2 as its adjacent which is already visited, hence we ignore it.Īt this stage, only node 3 is present in the stack. Next, we mark 4 which is the top of the stack as visited. Its adjacent node 4 is added to the stack. As 0 is already in the visited list, we ignore it and we visit 2 which is the top of the stack.

We mark it as visited by adding it to the visited list. Next, we take one of the adjacent nodes to process i.e. Then we push all its adjacent nodes in the stack. First, we mark it as visited and add it to the visited list. Let 0 be the starting node or source node. For clarity purposes, we will use the same graph that we used in the BFS illustration. Let us now illustrate the DFS traversal of a graph. Step 4: Repeat steps 2 and 3 until the stack is empty.įrom the above pseudo-code, we notice that the DFS algorithm is called recursively on each vertex to ensure that all the vertices are visited.Step 3: Find all the adjacent nodes of the node marked visited and add the ones that are not yet visited, to the stack.Step 2: Pop the top item from the stack and add it to the visited list.

Step 1: Insert the root node or starting node of a tree or a graph in the stack.Next, we will see the algorithm and pseudo-code for the DFS technique. The edges that lead us to unexplored nodes are called ‘discovery edges’ while the edges leading to already visited nodes are called ‘block edges’. In DFS we use a stack data structure for storing the nodes being explored. Unlike BFS in which we explore the nodes breadthwise, in DFS we explore the nodes depth-wise.

Apa itu algoritma pemrograman