DFS

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here. Example So consider the tree: 1 / \ 2 3 / \ / \ 4 5 6 7 The BFS or level order traversal here is : [Read More]

What is dfs? This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game. To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later. DFS(graph G, vertex s) mark s as explored for every edge (s, v): if v unexplored DFS(G, v) Example : Consider the graph: [Read More]

Definition Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering. A topological ordering of a directed graph G is a labeling f of G’s nodes (1…n) such that: (1) the f(v)’s are the set {1, 2, … , n} (2) if (u, v) in G, then f(u) < f(v) … the graph should move in forward direction. [Read More]

Graph search algorithms are important but lets have some motivations. Motivation behind graph search Here are few motivations: Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier. [Read More]

There are two possible traversal methods for a graph: i. Breadth-First Traversal ii. Depth-First Traversal i. Breadth-First Traversal: Traverse all the vertices starting from a given ‘start vertex’. Hence, such a traversal follows the ‘neighbour-first’ principle by considering the following: - No vertex is visited more than once - Only those vertices that can be reached are visited Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i. [Read More]

Consider this tree (which is a graph without a cycle) : Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem. A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. [Read More]