Breaking
Graph

# Depth First Search

## Data structure Description

Depth First Search algorithm is an algorithm to search node from tree or graph. DFS algorithm starts traversing from the root. It traverses each branch before backtracking. DFS takes less memory compared than Breadth first search and not necessary to store all of the child pointers at each level.

The major drawback in depth-First Search is not guaranteed to find the solution. If it finds the solution, it may not be minimal solution.

Write a program to implement depth first search using the graph?

## Source Code

```package com.dsacode.DataStructre.graph;

import java.util.Stack;

class Vertex{
public char label;
public boolean wasVisited;

public Vertex(char lab){
label = lab;
wasVisited = false;
}
}

public class DepthFirstSearch {
private final int MAX_VERTS = 20;
private Vertex vertexList[];
private int nVerts;
private Stack < Integer > theStack;

public DepthFirstSearch() {

vertexList = new Vertex[MAX_VERTS];
nVerts = 0;
for(int y = 0; y < MAX_VERTS; y++)
for(int x = 0; x < MAX_VERTS; x++)
theStack = new Stack < Integer >();
}

vertexList[nVerts++] = new Vertex(lab);
}

public void addEdge(int start, int end)   {
}

public void displayVertex(int v) {
System.out.print(vertexList[v].label+"->");
}

public void dfs() {
vertexList.wasVisited = true;
displayVertex(0);
theStack.push(0);

while( !theStack.isEmpty() ) {
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1)
theStack.pop();
else {
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}

for(int j = 0; j < nVerts; j++)
vertexList[j].wasVisited = false;
}

for(int j = 0; j < nVerts; j++)
return j;
return -1;
}

public static void main(String[] args) {
DepthFirstSearch theGraph = new DepthFirstSearch();

System.out.print("Visits from source to destination using DFS: ");
theGraph.dfs();
System.out.println();
}

}```

## Output

```Visits from source to destination using DFS: A->B->C->D->E
```

#### 1 Comment

1. Hi Dear, are you really visiting this website regularly, if so afterward you will without doubt take pleasant knowledge.