© 2012 Firstsoft Technologies (P) Limited. login Hi 'Guest' Home SiteMap Contact Us Disclaimer
 Study Abroad Education Loan College News Placement Book Shops E - Books Engg-Admission Edu-Classifieds Students-Forum
Easy Studies
 « NS2  Projects »

Home Implementation Of Graph Traverses Using Depth First Search▼

## Implementation Of Graph Traverses Using Depth First Search:

Depth First Search :

Depth first works by selection one vertex V of G as a start vertex; V is marked visited. Then each unvisited vertex adjacent to V is serached in trun using depth first serach recursively.This process continues until a dead end (i.e)a vertex with no adjacent unvisited vertices is encountered.At a deadend the algorithm backsup one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.

1.To check whether the undirected graph is connected or not.

2.To check whether the connected undirection graph is biconnected or not.]

3.To check the a Acyclicity of the directed graph.

Algorithm Steps:

Step 1: Choose any node in the graph . Designate it as the search node and mark    it as vivited.

Step 2: Using the adjacency matrix of the graph, find a node adjacent to the search node that has not been visited yet. Designate this as the new search node and mark it as visited.

Step 3: Repeat step 2 using t he new search node. If no nodes satisfying(2)  can be found, return to the previous search node and continue from there.

Step 4: When a return to the previous search in(3) is impossible,the serach from the originally choosen search node is complete.

Step 5: If the graph still contains unvisited nodes,choose any node that has  not been visited and repeat step(1) through(4).

C Program To Implement Graph Traverses Using Depth First Search

CPP Program To Implement Graph Traverses Using Depth First Search

⇓ Student Projects ⇓
⇑ Student Projects ⇑