Depth First Search Algorithm
A DFS algorithm, as the name implies, is used to search deeper in the graph, whenever possible. The edges are explored, out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the source vertex. DFS uses stack structure to maintain the order in which the vertices are to be processed.
Step 1: Initialize all nodes to ready state (status = 1)
Step 2: Push the starting node in stack and change its status to the waiting state (status = 2)
Step 3: Repeat step 4 and 5 until stack is empty
Step 4: pop the top node n of stack. Process n and change the status of n to the processed state (status = 3)
Step 5: Push on to the stack, all the neighbor of n that are in ready state (status = 1), and change their status to the waiting state (status = 2) [End of the step 3 loop]
Step 6: exit
Output:
|
|
Comments (3)
Leave a Reply
- Breadth First Search Algorithm
A breadth first search traversal method, visits all the successors of a visited node before visiting any successor of any of its child nodes. This is a contradiction to depth first traversal method; which visits the successor of a visited node before visiting any of its brothers, i.e., children of the same parent. A depth [...]...
- Prim Algorithm
Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of the weights of the tree edges in T is as small as possible. Such a tree is called as minimum spanning tree and represents the most inexpensive way of connecting all the [...]...
- Graphs
A graph is an important non linear data structure. This data structure is used to represent relationship between pairs of elements, which may not, necessarily, be hierarchical in nature. A graph is defined as: “Graph G is an ordered set (V, E), where V(G) represents the set of elements, called vertices, and E(G) represents the [...]...
- Dijkstra Algorithm
Dijkstra algorithm gets its name from the Dutch computer scientist Edsger Dijkstra who invented this algorithm in 1959. It is used to find the shortest path between two non-negative nodes in a graph. Dijkstra algorithm is widely used for the purpose of routing. For any giving node in a graph the algorithm finds the path [...]...
- Kruskal’s Algorithm
An algorithm which is used to create a minimum spanning tree is attributed to Kruskal’s algorithm. The nodes of the graph are initially considered as n distinct partial trees with one node each. At each step of the algorithm, two distinct partial trees are connected into a single partial tree by an edge of the [...]...
it is very good that alogrithem but iwant cod c++
and steps of that alogrithem
very bad algorithm.
please modify it.
9846388009……….
it was a good algorithm though i wasn’t understand it enough , it should be clarified correctly and explain it words for words… please have a dev c++ and java..(can u)