參考自文章：https://blog.csdn.net/ntt5667781/article/details/52743342

1、圖的存儲(chǔ)

在開(kāi)始各類(lèi)圖算法之前，先將圖的結(jié)構(gòu)進(jìn)行分類(lèi)樱溉。
圖的表示，在實(shí)際實(shí)現(xiàn)過(guò)程中腰素，有以下幾種基本的方式可以來(lái)表示圖。
1） 鄰接矩陣：對(duì)于較小或者中等規(guī)模的圖的構(gòu)造較為適用蛤织，因?yàn)樾枰猇*V大小的空間。
2） 邊的數(shù)組：使用一個(gè)簡(jiǎn)單的自定義edge類(lèi)鸿染，還有兩個(gè)變量指蚜，分別代表邊的兩個(gè)端點(diǎn)編號(hào)，實(shí)現(xiàn)簡(jiǎn)單牡昆，但是在求每個(gè)點(diǎn)的鄰接點(diǎn)的時(shí)候?qū)崿F(xiàn)較為困難姚炕。
3） 鄰接表數(shù)組：較為常用，使用一個(gè)以頂點(diǎn)為索引的數(shù)組丢烘，數(shù)組每個(gè)元素都是和該頂點(diǎn)相鄰的頂點(diǎn)列表柱宦，這種數(shù)組占空間相對(duì)于鄰接矩陣少了很多，并且能很好的找到某個(gè)給定點(diǎn)的所有鄰接點(diǎn)播瞳。

按照?qǐng)D中邊的方向?qū)D分成有向圖和無(wú)向圖：
1）無(wú)向圖：圖中的邊沒(méi)有方向掸刊。
2）有向圖：圖中的邊有方向。
對(duì)于有向圖和無(wú)向圖的具體實(shí)現(xiàn)表示可以使用前面介紹的三種方法赢乓，兩種圖在表示的時(shí)候大部分的實(shí)現(xiàn)代碼都是一致的忧侧。

普通無(wú)向圖的鄰接數(shù)組表示方法以及鄰接矩陣表示方法的具體實(shí)現(xiàn)代碼如下：

package graph;

import java.util.*;

public class Graph {
    private int V;
    private int E;
    private List<Integer>[] adj;
    private int[][] a;
    public Graph(int V){
        this.E = 0;
        this.V = V;
        adj = new ArrayList[V];
        a = new int[V][V];
        for(int i=0;i<V;i++){
            adj[i] = new ArrayList<Integer>();

        }
    }
    //無(wú)向圖是沒(méi)有方向的，所以需要在兩個(gè)定點(diǎn)添加頂點(diǎn)信息
    public void addEdge(int v1,int v2){
        a[v1][v2] = 1;
        a[v2][v1] = 1;
        adj[v1].add(v2);
        adj[v2].add(v1);
        this.E++;
    }

    public int getV(){
        return this.V;
    }

    public int getE(){
        return this.E;
    }
    //鄰接數(shù)組返回給定點(diǎn)的所有鄰接點(diǎn)
    public List<Integer> adj(int i){
        return adj[i];
    }

    //鄰接矩陣返回給定點(diǎn)的所有鄰接點(diǎn)
    public List<Integer> adj1(int i){
        List<Integer> list = new ArrayList<Integer>();
        for(int j = 0;j<this.V;j++){
            if(a[i][j] == 1){
                list.add(j);
            }
        }
        return list;
    }

    public static void main(String[] args){
        Graph graph = new Graph(5);
        graph.addEdge(0,1);
        graph.addEdge(0,3);
        graph.addEdge(3,1);
        System.out.println(graph.getE());
        List<Integer> adj = graph.adj(0);
        for(int i=0;i<adj.size();i++){
            System.out.print(adj.get(i) + " ");
        }
    }
}

無(wú)權(quán)有向圖的具體實(shí)現(xiàn)代碼如下：

package graph;

import java.util.*;

public class DirectedGraph {
    private int V;  //圖中的頂點(diǎn)數(shù)目
    private int E;  //圖中的邊數(shù)目
    private List<Integer>[] adj;  //鄰接數(shù)組
    private int[][] a;   //鄰接矩陣

    public DirectedGraph(int V) {
        this.E = 0;
        this.V = V;
        adj = new ArrayList[V];
        a=new int[V][V];
        for (int i = 0; i < V; i++)
            adj[i] = new ArrayList<>();
    }
    //由于無(wú)向圖中的邊是有方向的牌芋，所以添加邊的時(shí)候需要只需要在起始點(diǎn)的鄰接列表中添加頂點(diǎn)信息蚓炬。
    public void addEdge(int v1, int v2) {
        a[v1][v2]=1;
        adj[v1].add(v2);
        E++;
    }

    public int getV() {
        return V;
    }

    public int getE() {
        return E;
    }
    //鄰接數(shù)組返回給定點(diǎn)的所有鄰接點(diǎn)
    public List<Integer> adj(int i) {
        return adj[i];
    }
    //鄰接矩陣返回給定點(diǎn)的所有鄰接點(diǎn)
    public List<Integer> adj1(int i){
        List<Integer> list=new ArrayList<Integer>();
        for(int j=0;j<V;j++){
            if(a[i][j] == 1)
                list.add(j);
        }
        return list;
    }

    public static void main(String[] args){
        DirectedGraph graph = new DirectedGraph(5);
        graph.addEdge(0,1);
        graph.addEdge(0,3);
        graph.addEdge(3,1);
        System.out.println(graph.getE());
        List<Integer> adj = graph.adj1(0);
        for(int i=0;i<adj.size();i++){
            System.out.print(adj.get(i) + " ");
        }
    }
}

2、圖的遍歷算法

2.1 深度優(yōu)先搜索

介紹兩種比較基礎(chǔ)的圖遍歷算法躺屁，廣度優(yōu)先搜索和深度優(yōu)先搜索肯夏。
1）深度優(yōu)先搜索：這是一種典型的遞歸算法用來(lái)搜索圖（遍歷所有的頂點(diǎn)）；
思想：從圖的某個(gè)頂點(diǎn)i開(kāi)始犀暑，將頂點(diǎn)i標(biāo)記為已訪問(wèn)頂點(diǎn)驯击，并將訪問(wèn)頂點(diǎn)i的鄰接列表中沒(méi)有被標(biāo)記的頂點(diǎn)j，將頂點(diǎn)j標(biāo)記為已訪問(wèn)耐亏，并在訪問(wèn)頂點(diǎn)j的鄰接列表中未被標(biāo)記的頂點(diǎn)k依次深度遍歷下去徊都，直到某個(gè)點(diǎn)的所有鄰接列表中的點(diǎn)都被標(biāo)記為已訪問(wèn)后，返回上層广辰。重復(fù)以上過(guò)程直到圖中的所有頂點(diǎn)都被標(biāo)記為已訪問(wèn)暇矫。
深度優(yōu)先遍歷和樹(shù)的先序訪問(wèn)非常類(lèi)似，盡可能深的去訪問(wèn)節(jié)點(diǎn)择吊。深度優(yōu)先遍歷的大致過(guò)程（遞歸版本）：
a）在訪問(wèn)一個(gè)節(jié)點(diǎn)的時(shí)候袱耽，將其設(shè)置為已訪問(wèn)。
b）遞歸的訪問(wèn)被標(biāo)記頂點(diǎn)的鄰接列表中沒(méi)有被標(biāo)記的所有頂點(diǎn)
（非遞歸版本）:
圖的非遞歸遍歷我們借助棧來(lái)實(shí)現(xiàn)干发。
a）如果棧為空朱巨，則退出程序，否則枉长，訪問(wèn)棧頂節(jié)點(diǎn)冀续，但不彈出棧點(diǎn)節(jié)點(diǎn)琼讽。
b）如果棧頂節(jié)點(diǎn)的所有直接鄰接點(diǎn)都已訪問(wèn)過(guò)，則彈出棧頂節(jié)點(diǎn)洪唐，否則钻蹬，將該棧頂節(jié)點(diǎn)的未訪問(wèn)的其中一個(gè)鄰接點(diǎn)壓入棧，同時(shí)凭需，標(biāo)記該鄰接點(diǎn)為已訪問(wèn)问欠，繼續(xù)步驟a。
該算法訪問(wèn)頂點(diǎn)的順序是和圖的表示有關(guān)的粒蜈，而不只是和圖的結(jié)構(gòu)或者是算法有關(guān)顺献。

深度優(yōu)先探索是個(gè)簡(jiǎn)單的遞歸算法(當(dāng)然借助棧也可以實(shí)現(xiàn)非遞歸的版本)，但是卻能有效的處理很多和圖有關(guān)的任務(wù)枯怖，比如：
a) 連通性：ex:給定的兩個(gè)頂點(diǎn)是否聯(lián)通 or 這個(gè)圖有幾個(gè)聯(lián)通子圖注整。
b) 單點(diǎn)路徑：給定一幅圖和一個(gè)固定的起點(diǎn)，尋找從s到達(dá)給定點(diǎn)的路徑是否存在度硝，若存在肿轨，找出這條路徑。

尋找路徑：
為了實(shí)現(xiàn)這個(gè)功能蕊程，需要在上面實(shí)現(xiàn)的深度優(yōu)先搜索中中增加實(shí)例變量edgeTo[]椒袍，它相當(dāng)于繩索的功能，這個(gè)數(shù)組可以找到從每個(gè)與起始點(diǎn)聯(lián)通的頂點(diǎn)回到起始點(diǎn)的路徑（具體實(shí)現(xiàn)的思路非常巧妙： 從邊v-w第一次訪問(wèn)w的時(shí)候藻茂，將edgeTo[w]的值跟新為v來(lái)記住這條道路驹暑，換句話(huà)說(shuō)，v-w是從s到w的路徑上最后一條已知的邊捌治，這樣搜索結(jié)果就是一條以起始點(diǎn)為根結(jié)點(diǎn)的樹(shù)岗钩，也就是edgeTo[]是個(gè)有父鏈接表示的樹(shù)纽窟。）

深度優(yōu)先搜索的遞歸實(shí)現(xiàn)版本和非遞歸版本

package graph;

import java.util.*;

public class DepthFirstSearch {
    //用來(lái)記錄頂點(diǎn)的標(biāo)記狀態(tài) true表示為已訪問(wèn)肖油，false表示為未被訪問(wèn)。
    private boolean[] marked;
    private int count;
    //用來(lái)記錄頂點(diǎn)索引所對(duì)應(yīng)的父結(jié)點(diǎn)臂港，假設(shè)遍歷是從s到達(dá)的t那么edgeTo[s所對(duì)的所用]=t;
    private int[] edgeTo;
    //起始點(diǎn)
    private int s;
    private Stack<Integer> stack = new Stack<Integer>();

    public DepthFirstSearch(Graph G,int s){
        marked = new boolean[G.getV()];
        edgeTo = new int[G.getV()];
        this.s = s;
        stack.push(s);
        dfs(G,s);
    }

    //遞歸形式實(shí)現(xiàn)
    public void dfs(Graph G,int s){
        marked[s] = true;
        count ++;
        for(int temp:G.adj(s)){
            if(!marked[temp]){
                edgeTo[temp] = s;
                dfs(G,temp);
            }
        }
    }

    //非遞歸形式實(shí)現(xiàn)
    public void dfs(Graph G){
        while(!stack.isEmpty()){
            s = stack.peek();
            boolean needPop = true;
            marked[s] = true;
            count++;
            for(int temp:G.adj(s)){
                if(!marked[temp]){
                    needPop = false;
                    stack.push(temp);
                    edgeTo[temp]=s;
                    break;
                }
            }
            if(needPop)
                stack.pop();
        }
    }

    public boolean hasPathTo(int v){
        return marked[v];
    }
    //得到到達(dá)v的一個(gè)路徑
    public List<Integer> pathTo(int v){
        if(!hasPathTo(v))
            return null;
        List<Integer> list = new ArrayList<Integer>();
        list.add(v);
        v = edgeTo[v];
        while(v!=s) {
            list.add(v);
            v = edgeTo[v];
        }
        list.add(s);
        Collections.reverse(list);
        return list;
    }

    public int count(){
        return count;
    }

    public static void main(String[] args){
        int V = 5;
        Graph G=new Graph(V);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(1,3);
        G.addEdge(3,4);
        int s=0;
        DepthFirstSearch dfs=new  DepthFirstSearch(G,s);
        for(int v=0;v<G.getV();v++){
            if(dfs.hasPathTo(v))
                for(int x:dfs.pathTo(v))
                    if(x==s)
                        System.out.print(x);
                    else
                        System.out.print("-"+x);
            System.out.println();
        }
    }
}

DFS其實(shí)還可以解決很多在無(wú)向圖中的基礎(chǔ)性問(wèn)題,比如：

計(jì)算圖中的連通子圖的數(shù)量

package graph;

public class ConnectComponent {
    private boolean[] marked;
    private int[] id;
    private int count;

    public ConnectComponent(Graph G){
        marked = new boolean[G.getV()];
        id = new int[G.getV()];
        for(int i=0;i<G.getV();i++){
            if(!marked[i]){
                dfs(G,i);
                count++;
            }
        }
    }

    public void dfs(Graph G,int s){
        marked[s] = true;
        id[s] = count;
        for(int temp : G.adj(s)){
            if(!marked[temp]){
                dfs(G,temp);
            }
        }
    }

    public boolean connected(int v,int w){
        return id[v] == id[w];
    }

    public int id(int v){
        return id[v];
    }

    public int getCount(){
        return count;
    }

    public static void main(String[] args){
        int V = 5;
        Graph G=new Graph(V);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(3,4);
        int s=0;
        ConnectComponent graph = new ConnectComponent(G);
        System.out.println(graph.getCount());
        System.out.println(graph.connected(0,2));
        System.out.println(graph.connected(0,4));
    }
}

檢測(cè)圖中是否有環(huán)

package graph;

public class CycleDetect {
    private boolean[] marked;
    private boolean flag;

    public CycleDetect(Graph G){
        marked = new boolean[G.getV()];
        for(int s=0;s<G.getV();s++){
            if(!marked[s]){
                dfs(G,s,s);
            }
        }
    }

    public void dfs(Graph G,int s,int initial){
        marked[s] = true;
        for(int temp:G.adj(s)){
            if(!marked[temp]){
                dfs(G,temp,initial);
            } else{
                if(temp == initial){
                    flag = true;
                    return;
                }
            }
        }
    }

    public boolean hasCycle(){
        return flag;
    }
}

二分圖問(wèn)題
即能否用兩種顏色給這個(gè)圖進(jìn)行著色

package graph;

public class IsBiagraph {
    private boolean[] marked;
    private boolean[] color;
    private boolean flag = true;

    public IsBiagraph(Graph G){
        marked = new boolean[G.getV()];
        color = new boolean[G.getV()];

        for(int s = 0;s<G.getV();s++){
            if(!marked[s]){
                dfs(G,s);
            }
        }
    }

    public void dfs(Graph G,int s){
        marked[s] = true;
        for(int temp:G.adj(s)){
            if(!marked[temp]){
                color[temp] = !color[s];
                dfs(G,temp);
            }
            else{
                if(color[temp]==color[s])
                    flag = false;
            }
        }

    }

    public boolean isBiagragh(){
        return flag;
    }
}

有關(guān)二分圖的博客參考：https://blog.csdn.net/x_y_q_/article/details/51920683

2.2 廣度優(yōu)先搜索

前面說(shuō)過(guò)森枪，深度優(yōu)先搜索得到的路徑不僅取決于圖的結(jié)構(gòu)，還取決于圖的表示以及遞歸調(diào)用的性質(zhì)审孽，但是如果要求最短的路徑（給定圖G和起始點(diǎn)s尋找給定點(diǎn)v和s間是否存在路徑县袱，如果存在，找出最短的路徑）佑力，那么使用前面的DFS算法并不能解決該問(wèn)題式散，所以出現(xiàn)了廣度優(yōu)先搜索BFS來(lái)實(shí)現(xiàn)這個(gè)目的，廣度優(yōu)先搜索也是其他算法的基礎(chǔ)打颤。
在程序中暴拄，搜索一幅圖的時(shí)候會(huì)遇到有很多條邊都需要被遍歷的情況漓滔，我們會(huì)選擇其中一條并將其他邊留到以后再繼續(xù)搜索，在DFS中使用棧結(jié)構(gòu)乖篷，使用LIFO的規(guī)則來(lái)描述响驴，從有待搜索的通道中選取最晚遇到的那個(gè)通道，然而在BFS算法中撕蔼，我們希望按照與起點(diǎn)的距離來(lái)遍歷所有的頂點(diǎn)豁鲤，使用FIFO（隊(duì)列）來(lái)進(jìn)行搜索，也就是搜索最先遇到的那個(gè)通道鲸沮。
BFS:使用一個(gè)隊(duì)列來(lái)保存所有已經(jīng)被標(biāo)記過(guò)的但是其鄰接點(diǎn)還未被檢查過(guò)的頂點(diǎn)琳骡，現(xiàn)將頂點(diǎn)加入隊(duì)列中，然后重復(fù)下面的操作诉探，直至隊(duì)列為空：
1）取隊(duì)列中的下一個(gè)頂點(diǎn)v并標(biāo)記它
2）將與v相鄰的所有的未被標(biāo)記的頂點(diǎn)加入隊(duì)列中日熬。

廣度優(yōu)先算法

package graph;

import java.util.*;

public class BreadFirstSearch {
    private boolean[] marked;
    private int[] edgeTo;
    //起點(diǎn)
    private int s;

    public BreadFirstSearch(Graph G,int s){
        marked = new boolean[G.getV()];
        edgeTo = new int[G.getV()];
        this.s = s;
        bfs(G,s);
    }

    public void bfs(Graph G,int s){
        Queue<Integer> queue = new LinkedList<Integer>();
        marked[s] = true;
        queue.offer(s);
        while(!queue.isEmpty()){
            s = queue.poll();
            for(int temp:G.adj(s)){
                if(!marked[temp]){
                    marked[temp] = true;
                    edgeTo[temp] = s;
                    queue.offer(temp);
                }
            }
        }
    }

    public boolean hasPathTo(int v){
        return marked[v];
    }

    public List<Integer> pathTo(int v){
        List<Integer> path = new ArrayList<Integer>();
        if(!marked[v]) return path;
        path.add(v);
        v = edgeTo[v];
        while(v!=s){
            path.add(v);
            v = edgeTo[v];
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }
}