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

2. Breadth first traversal

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;
    private LinkedList<Integer> adj[];

    public  Graph(int v){
        this.v = v;
        adj = new LinkedList[v];
        for(int i = 0; i < v; i++){
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t){
        adj[s].add(t);
        adj[t].add(s);
    }

    // breadth-first search 
    public void bfs(int s, int t){
        if(s == t) return;
        boolean visited [] = new boolean[v];
        visited[s] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        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++){
                int q = adj[w].get(i);
                if(!visited[q]){
                    prev[q] = w;
                    if(q == t){
                        printPrev(prev, s, t);
                        return;
                    }
                }
                visited[q] = true;
                queue.add(q);
            }
        }
    }

    // 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++){
            int q = adj[w].get(i);
            if(!visited[q]){
                prev[q] = w;
                recurDfs(q, t, visited, prev);
            }
        }
    }
}