# Depth traversal and breadth traversal of [Java] graph

There are two ways to represent a graph:

1. Adjacency matrix representation: it uses the structure of two-dimensional array to store graphs. The advantage is that it is easy to calculate by array subscript, and the disadvantage is that it wastes more space

2. Adjacency table representation: use one-dimensional array and linked list to store the graph, the advantage is to save storage space, the disadvantage is not easy to operate

Two common algorithms of graphs:

1. Depth first traversal

Depth first traversal is implemented by queue

Breadth first search is realized by backtracking algorithm

The specific code is as follows:

``````
// Defining graph by adjacency table
public class Graph {
private int v;

public  Graph(int v){
this.v = v;
for(int i = 0; i < v; i++){
}
}

public void addEdge(int s, int t){
}

public void bfs(int s, int t){
if(s == t) return;
boolean visited [] = new boolean[v];
visited[s] = true;
int [] prev = new int[v];
for(int i = 0; i < v; i++){
prev[i] = -1;
}
while(queue.size() != 0){
int w = queue.poll();
for(int i = 0; i < adj[w].size(); i++){
if(!visited[q]){
prev[q] = w;
if(q == t){
printPrev(prev, s, t);
return;
}
}
visited[q] = true;
}
}
}

// Print out path
public void printPrev(int prev[], int s, int t){
if(prev[t] != -1 && s != t){
printPrev(prev, s, prev[t]);
}
System.out.print(t + " ");
}

// Depth first search
boolean found = false;
public void dfs(int s, int t){
found = false;
boolean visited[] = new boolean[v];
visited[s] = true;
int [] prev = new int [v];
for(int i = 0; i < v; i++){
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
printPrev(prev, s, t);
}

// Using the idea of backtracking to realize depth traversal
public void recurDfs(int w, int t, boolean [] visited, int prev[]){
if(found == true) return;
visited[w] = true;
if(w == t){
found = true;
return;
}

for(int i = 0; i < adj[w].size(); i++){