1、圖的定義

我們知道，前面討論的數(shù)據(jù)結(jié)構(gòu)都有一個(gè)框架，而這個(gè)框架是由相應(yīng)的算法實(shí)現(xiàn)的，比如二叉樹搜索樹，左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值，右子樹所有結(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值，類似這種形狀使得它容易搜索數(shù)據(jù)和插入數(shù)據(jù)，樹的邊表示了從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的快捷方式。

而圖通常有個(gè)固定的形狀，這是由物理或抽象的問(wèn)題所決定的。比如圖中節(jié)點(diǎn)表示城市，而邊可能表示城市間的班機(jī)航線。如下圖是美國(guó)加利福利亞簡(jiǎn)化的高速公路網(wǎng)：

①、鄰接：

如果兩個(gè)頂點(diǎn)被同一條邊連接，就稱這兩個(gè)頂點(diǎn)是鄰接的，如上圖 I 和 G 就是鄰接的，而 I 和 F 就不是。有時(shí)候也將和某個(gè)指定頂點(diǎn)鄰接的頂點(diǎn)叫做它的鄰居，比如頂點(diǎn) G 的鄰居是 I、H、F。

②、路徑：

路徑是邊的序列，比如從頂點(diǎn)B到頂點(diǎn)J的路徑為 BAEJ，當(dāng)然還有別的路徑 BCDJ，BACDJ等等。

③、連通圖和非連通圖：

如果至少有一條路徑可以連接起所有的頂點(diǎn)，那么這個(gè)圖稱作連通的；如果假如存在從某個(gè)頂點(diǎn)不能到達(dá)另外一個(gè)頂點(diǎn)，則稱為非聯(lián)通的。

④、有向圖和無(wú)向圖：

如果圖中的邊沒(méi)有方向，可以從任意一邊到達(dá)另一邊，則稱為無(wú)向圖；比如雙向高速公路，A城市到B城市可以開車從A駛向B，也可以開車從B城市駛向A城市。但是如果只能從A城市駛向B城市的圖，那么則稱為有向圖。

⑤、有權(quán)圖和無(wú)權(quán)圖：

圖中的邊被賦予一個(gè)權(quán)值，權(quán)值是一個(gè)數(shù)字，它能代表兩個(gè)頂點(diǎn)間的物理距離，或者從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的時(shí)間，這種圖被稱為有權(quán)圖；反之邊沒(méi)有賦值的則稱為無(wú)權(quán)圖。

本篇博客我們討論的是無(wú)權(quán)無(wú)向圖。

2、在程序中表示圖

我們知道圖是由頂點(diǎn)和邊組成，那么在計(jì)算機(jī)中，怎么來(lái)模擬頂點(diǎn)和邊？

①、頂點(diǎn)：

在大多數(shù)情況下，頂點(diǎn)表示某個(gè)真實(shí)世界的對(duì)象，這個(gè)對(duì)象必須用數(shù)據(jù)項(xiàng)來(lái)描述。比如在一個(gè)飛機(jī)航線模擬程序中，頂點(diǎn)表示城市，那么它需要存儲(chǔ)城市的名字、海拔高度、地理位置和其它相關(guān)信息，因此通常用一個(gè)頂點(diǎn)類的對(duì)象來(lái)表示一個(gè)頂點(diǎn)，這里我們僅僅在頂點(diǎn)中存儲(chǔ)了一個(gè)字母來(lái)標(biāo)識(shí)頂點(diǎn)，同時(shí)還有一個(gè)標(biāo)志位，用來(lái)判斷該頂點(diǎn)有沒(méi)有被訪問(wèn)過(guò)（用于后面的搜索）。

/**
 * 頂點(diǎn)類
 * @author vae
 */
public class Vertex {
    public char label;
    public boolean wasVisited;
    public Vertex(char label){
        this.label = label;
        wasVisited = false;
    }
}

頂點(diǎn)對(duì)象能放在數(shù)組中，然后用下標(biāo)指示，也可以放在鏈表或其它數(shù)據(jù)結(jié)構(gòu)中，不論使用什么結(jié)構(gòu)，存儲(chǔ)只是為了使用方便，這與邊如何連接點(diǎn)是沒(méi)有關(guān)系的。

②、邊：

在前面講解各種樹的數(shù)據(jù)結(jié)構(gòu)時(shí)，大多數(shù)樹都是每個(gè)節(jié)點(diǎn)包含它的子節(jié)點(diǎn)的引用，比如紅黑樹、二叉樹。也有用數(shù)組表示樹，樹組中節(jié)點(diǎn)的位置決定了它和其它節(jié)點(diǎn)的關(guān)系，比如堆就是用數(shù)組表示。

然而圖并不像樹，圖沒(méi)有固定的結(jié)構(gòu)，圖的每個(gè)頂點(diǎn)可以與任意多個(gè)頂點(diǎn)相連，為了模擬這種自由形式的組織結(jié)構(gòu)，用如下兩種方式表示圖：鄰接矩陣和鄰接表（如果一條邊連接兩個(gè)頂點(diǎn)，那么這兩個(gè)頂點(diǎn)就是鄰接的）

鄰接矩陣：

鄰接矩陣是一個(gè)二維數(shù)組，數(shù)據(jù)項(xiàng)表示兩點(diǎn)間是否存在邊，如果圖中有 N 個(gè)頂點(diǎn)，鄰接矩陣就是 N*N 的數(shù)組。上圖用鄰接矩陣表示如下：　　

1表示有邊，0表示沒(méi)有邊，也可以用布爾變量true和false來(lái)表示。頂點(diǎn)與自身相連用 0 表示，所以這個(gè)矩陣從左上角到右上角的對(duì)角線全是 0 。

注意：這個(gè)矩陣的上三角是下三角的鏡像，兩個(gè)三角包含了相同的信息，這個(gè)冗余信息看似低效，但是在大多數(shù)計(jì)算機(jī)中，創(chuàng)造一個(gè)三角形數(shù)組比較困難，所以只好接受這個(gè)冗余，這也要求在程序處理中，當(dāng)我們?cè)黾右粭l邊時(shí)，比如更新鄰接矩陣的兩部分，而不是一部分。

鄰接表：

鄰接表是一個(gè)鏈表數(shù)組（或者是鏈表的鏈表），每個(gè)單獨(dú)的鏈表表示了有哪些頂點(diǎn)與當(dāng)前頂點(diǎn)鄰接。

3、搜索

在圖中實(shí)現(xiàn)最基本的操作之一就是搜索從一個(gè)指定頂點(diǎn)可以到達(dá)哪些頂點(diǎn)，比如從武漢出發(fā)的高鐵可以到達(dá)哪些城市，一些城市可以直達(dá)，一些城市不能直達(dá)。現(xiàn)在有一份全國(guó)高鐵模擬圖，要從某個(gè)城市（頂點(diǎn)）開始，沿著鐵軌（邊）移動(dòng)到其他城市（頂點(diǎn)），有兩種方法可以用來(lái)搜索圖：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。它們最終都會(huì)到達(dá)所有連通的頂點(diǎn)，深度優(yōu)先搜索通過(guò)棧來(lái)實(shí)現(xiàn)，而廣度優(yōu)先搜索通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)，不同的實(shí)現(xiàn)機(jī)制導(dǎo)致不同的搜索方式。

①、深度優(yōu)先搜索（DFS）

深度優(yōu)先搜索算法有如下規(guī)則：

規(guī)則1：如果可能，訪問(wèn)一個(gè)鄰接的未訪問(wèn)頂點(diǎn)，標(biāo)記它，并將它放入棧中。

規(guī)則2：當(dāng)不能執(zhí)行規(guī)則 1 時(shí)，如果棧不為空，就從棧中彈出一個(gè)頂點(diǎn)。

規(guī)則3：如果不能執(zhí)行規(guī)則 1 和規(guī)則 2 時(shí)，就完成了整個(gè)搜索過(guò)程。

對(duì)于上圖，應(yīng)用深度優(yōu)先搜索如下：假設(shè)選取 A 頂點(diǎn)為起始點(diǎn)，并且按照字母優(yōu)先順序進(jìn)行訪問(wèn)，那么應(yīng)用規(guī)則 1 ，接下來(lái)訪問(wèn)頂點(diǎn) B，然后標(biāo)記它，并將它放入棧中；再次應(yīng)用規(guī)則 1，接下來(lái)訪問(wèn)頂點(diǎn) F，再次應(yīng)用規(guī)則 1，訪問(wèn)頂點(diǎn) H。我們這時(shí)候發(fā)現(xiàn)，沒(méi)有 H 頂點(diǎn)的鄰接點(diǎn)了，這時(shí)候應(yīng)用規(guī)則 2，從棧中彈出 H，這時(shí)候回到了頂點(diǎn) F，但是我們發(fā)現(xiàn) F 也除了 H 也沒(méi)有與之鄰接且未訪問(wèn)的頂點(diǎn)了，那么再?gòu)棾?F，這時(shí)候回到頂點(diǎn) B，同理規(guī)則 1 應(yīng)用不了，應(yīng)用規(guī)則 2，彈出 B，這時(shí)候棧中只有頂點(diǎn) A了，然后 A 還有未訪問(wèn)的鄰接點(diǎn)，所有接下來(lái)訪問(wèn)頂點(diǎn) C，但是 C又是這條線的終點(diǎn)，所以從棧中彈出它，再次回到 A，接著訪問(wèn) D,G,I，最后也回到了 A，然后訪問(wèn) E，但是最后又回到了頂點(diǎn) A，這時(shí)候我們發(fā)現(xiàn) A沒(méi)有未訪問(wèn)的鄰接點(diǎn)了，所以也把它彈出?！，F(xiàn)在棧中已無(wú)頂點(diǎn)，于是應(yīng)用規(guī)則 3，完成了整個(gè)搜索過(guò)程。

深度優(yōu)先搜索在于能夠找到與某一頂點(diǎn)鄰接且沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)。這里以鄰接矩陣為例，找到頂點(diǎn)所在的行，從第一列開始向后尋找值為1的列；列號(hào)是鄰接頂點(diǎn)的號(hào)碼，檢查這個(gè)頂點(diǎn)是否未訪問(wèn)過(guò)，如果是這樣，那么這就是要訪問(wèn)的下一個(gè)頂點(diǎn)，如果該行沒(méi)有頂點(diǎn)既等于1（鄰接）且又是未訪問(wèn)的，那么與指定點(diǎn)相鄰接的頂點(diǎn)就全部訪問(wèn)過(guò)了（后面會(huì)用算法實(shí)現(xiàn)）。

②、廣度優(yōu)先搜索（BFS）

深度優(yōu)先搜索要盡可能的遠(yuǎn)離起始點(diǎn)，而廣度優(yōu)先搜索則要盡可能的靠近起始點(diǎn)，它首先訪問(wèn)起始頂點(diǎn)的所有鄰接點(diǎn)，然后再訪問(wèn)較遠(yuǎn)的區(qū)域，這種搜索不能用棧實(shí)現(xiàn)，而是用隊(duì)列實(shí)現(xiàn)。

規(guī)則1：訪問(wèn)下一個(gè)未訪問(wèn)的鄰接點(diǎn)（如果存在），這個(gè)頂點(diǎn)必須是當(dāng)前頂點(diǎn)的鄰接點(diǎn)，標(biāo)記它，并把它插入到隊(duì)列中。

規(guī)則2：如果已經(jīng)沒(méi)有未訪問(wèn)的鄰接點(diǎn)而不能執(zhí)行規(guī)則 1 時(shí)，那么從隊(duì)列列頭取出一個(gè)頂點(diǎn)（如果存在），并使其成為當(dāng)前頂點(diǎn)。

規(guī)則3：如果因?yàn)殛?duì)列為空而不能執(zhí)行規(guī)則 2，則搜索結(jié)束。

對(duì)于上面的圖，應(yīng)用廣度優(yōu)先搜索：以A為起始點(diǎn)，首先訪問(wèn)所有與 A 相鄰的頂點(diǎn)，并在訪問(wèn)的同時(shí)將其插入隊(duì)列中，現(xiàn)在已經(jīng)訪問(wèn)了 A,B,C,D和E。這時(shí)隊(duì)列（從頭到尾）包含 BCDE，已經(jīng)沒(méi)有未訪問(wèn)的且與頂點(diǎn) A 鄰接的頂點(diǎn)了，所以從隊(duì)列中取出B，尋找與B鄰接的頂點(diǎn)，這時(shí)找到F，所以把F插入到隊(duì)列中。已經(jīng)沒(méi)有未訪問(wèn)且與B鄰接的頂點(diǎn)了，所以從隊(duì)列列頭取出C，它沒(méi)有未訪問(wèn)的鄰接點(diǎn)。因此取出 D 并訪問(wèn) G，D也沒(méi)有未訪問(wèn)的鄰接點(diǎn)了，所以取出E，現(xiàn)在隊(duì)列中有 FG，在取出 F，訪問(wèn) H，然后取出 G，訪問(wèn) I，現(xiàn)在隊(duì)列中有 HI，當(dāng)取出他們時(shí)，發(fā)現(xiàn)沒(méi)有其它為訪問(wèn)的頂點(diǎn)了，這時(shí)隊(duì)列為空，搜索結(jié)束。

③、程序?qū)崿F(xiàn)

實(shí)現(xiàn)深度優(yōu)先搜索的棧StackX.class

package com.ys.graph;
public class StackX {
    private final int SIZE = 20;
    private int[] st;
    private int top;
    public StackX(){
        st = new int[SIZE];
        top = -1;
    }
    public void push(int j){
        st[++top] = j;
    }
    public int pop(){
        return st[top--];
    }
    public int peek(){
        return st[top];
    }
    public boolean isEmpty(){
        return (top == -1);
    }
}

實(shí)現(xiàn)廣度優(yōu)先搜索的隊(duì)列Queue.class

package com.ys.graph;
public class Queue {
    private final int SIZE = 20;
    private int[] queArray;
    private int front;
    private int rear;
    public Queue(){
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
    }
    public void insert(int j) {
        if(rear == SIZE-1) {
            rear = -1;
        }
        queArray[++rear] = j;
    }
    public int remove() {
        int temp = queArray[front++];
        if(front == SIZE) {
            front = 0;
        }
        return temp;
    }
    public boolean isEmpty() {
        return (rear+1 == front || front+SIZE-1 == rear);
    }
}

圖代碼 Graph.class

package com.ys.graph;
public class Graph {
    private final int MAX_VERTS = 20;//表示頂點(diǎn)的個(gè)數(shù)
    private Vertex vertexList[];//用來(lái)存儲(chǔ)頂點(diǎn)的數(shù)組
    private int adjMat[][];//用鄰接矩陣來(lái)存儲(chǔ) 邊,數(shù)組元素0表示沒(méi)有邊界，1表示有邊界
    private int nVerts;//頂點(diǎn)個(gè)數(shù)
    private StackX theStack;//用棧實(shí)現(xiàn)深度優(yōu)先搜索
    private Queue queue;//用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索
    /**
     * 頂點(diǎn)類
     * @author vae
     */
    class Vertex {
        public char label;
        public boolean wasVisited;
        public Vertex(char label){
            this.label = label;
            wasVisited = false;
        }
    }
    public Graph(){
        vertexList = new Vertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;//初始化頂點(diǎn)個(gè)數(shù)為0
        //初始化鄰接矩陣所有元素都為0，即所有頂點(diǎn)都沒(méi)有邊
        for(int i = 0; i < MAX_VERTS; i++) {
            for(int j = 0; j < MAX_VERTS; j++) {
                adjMat[i][j] = 0;
            }
        }
        theStack = new StackX();
        queue = new Queue();
    }
    //將頂點(diǎn)添加到數(shù)組中，是否訪問(wèn)標(biāo)志置為wasVisited=false(未訪問(wèn))
    public void addVertex(char lab) {
        vertexList[nVerts++] = new Vertex(lab);
    }
    //注意用鄰接矩陣表示邊，是對(duì)稱的，兩部分都要賦值
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }
    //打印某個(gè)頂點(diǎn)表示的值
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label);
    }
    /**深度優(yōu)先搜索算法:
     * 1、用peek()方法檢查棧頂?shù)捻旤c(diǎn)
     * 2、用getAdjUnvisitedVertex()方法找到當(dāng)前棧頂點(diǎn)鄰接且未被訪問(wèn)的頂點(diǎn)
     * 3、第二步方法返回值不等于-1則找到下一個(gè)未訪問(wèn)的鄰接頂點(diǎn)，訪問(wèn)這個(gè)頂點(diǎn)，并入棧
     *    如果第二步方法返回值等于 -1，則沒(méi)有找到，出棧
     */
    public void depthFirstSearch() {
        //從第一個(gè)頂點(diǎn)開始訪問(wèn)
        vertexList[0].wasVisited = true; //訪問(wèn)之后標(biāo)記為true
        displayVertex(0);//打印訪問(wèn)的第一個(gè)頂點(diǎn)
        theStack.push(0);//將第一個(gè)頂點(diǎn)放入棧中
        while(!theStack.isEmpty()) {
            //找到棧當(dāng)前頂點(diǎn)鄰接且未被訪問(wèn)的頂點(diǎn)
            int v = getAdjUnvisitedVertex(theStack.peek());
            if(v == -1) {   //如果當(dāng)前頂點(diǎn)值為-1，則表示沒(méi)有鄰接且未被訪問(wèn)頂點(diǎn)，那么出棧頂點(diǎn)
                theStack.pop();
            }else { //否則訪問(wèn)下一個(gè)鄰接頂點(diǎn)
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }
        //棧訪問(wèn)完畢，重置所有標(biāo)記位wasVisited=false
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    //找到與某一頂點(diǎn)鄰接且未被訪問(wèn)的頂點(diǎn)
    public int getAdjUnvisitedVertex(int v) {
        for(int i = 0; i < nVerts; i++) {
            //v頂點(diǎn)與i頂點(diǎn)相鄰（鄰接矩陣值為1）且未被訪問(wèn) wasVisited==false
            if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 廣度優(yōu)先搜索算法：
     * 1、用remove()方法檢查棧頂?shù)捻旤c(diǎn)
     * 2、試圖找到這個(gè)頂點(diǎn)還未訪問(wèn)的鄰節(jié)點(diǎn)
     * 3、 如果沒(méi)有找到，該頂點(diǎn)出列
     * 4、 如果找到這樣的頂點(diǎn)，訪問(wèn)這個(gè)頂點(diǎn)，并把它放入隊(duì)列中
     */
    public void breadthFirstSearch(){
        vertexList[0].wasVisited = true;
        displayVertex(0);
        queue.insert(0);
        int v2;
        while(!queue.isEmpty()) {
            int v1 = queue.remove();
            while((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                displayVertex(v2);
                queue.insert(v2);
            }
        }
        //搜索完畢，初始化，以便于下次搜索
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addEdge(0, 1);//AB
        graph.addEdge(1, 2);//BC
        graph.addEdge(0, 3);//AD
        graph.addEdge(3, 4);//DE
        System.out.println("深度優(yōu)先搜索算法 :");
        graph.depthFirstSearch();//ABCDE
        System.out.println();
        System.out.println("----------------------");
        System.out.println("廣度優(yōu)先搜索算法 :");
        graph.breadthFirstSearch();//ABDCE
    }
}

測(cè)試結(jié)果：

4、最小生成樹

對(duì)于圖的操作，還有一個(gè)最常用的就是找到最小生成樹，最小生成樹就是用最少的邊連接所有頂點(diǎn)。對(duì)于給定的一組頂點(diǎn)，可能有很多種最小生成樹，但是最小生成樹的邊的數(shù)量 E 總是比頂點(diǎn) V 的數(shù)量小1，即：

V = E + 1

這里不用關(guān)心邊的長(zhǎng)度，不是找最短的路徑（會(huì)在帶權(quán)圖中講解），而是找最少數(shù)量的邊，可以基于深度優(yōu)先搜索和廣度優(yōu)先搜索來(lái)實(shí)現(xiàn)。

比如基于深度優(yōu)先搜索，我們記錄走過(guò)的邊，就可以創(chuàng)建一個(gè)最小生成樹。因?yàn)镈FS 訪問(wèn)所有頂點(diǎn)，但只訪問(wèn)一次，它絕對(duì)不會(huì)兩次訪問(wèn)同一個(gè)頂點(diǎn)，但她看到某條邊將到達(dá)一個(gè)已訪問(wèn)的頂點(diǎn)，它就不會(huì)走這條邊，它從來(lái)不遍歷那些不可能的邊，因此，DFS 算法走過(guò)整個(gè)圖的路徑必定是最小生成樹。

//基于深度優(yōu)先搜索找到最小生成樹
public void mst(){
    vertexList[0].wasVisited = true;
    theStack.push(0);
    while(!theStack.isEmpty()){
        int currentVertex = theStack.peek();
        int v = getAdjUnvisitedVertex(currentVertex);
        if(v == -1){
            theStack.pop();
        }else{
            vertexList[v].wasVisited = true;
            theStack.push(v);
            displayVertex(currentVertex);
            displayVertex(v);
            System.out.print(" ");
        }
    }
    //搜索完畢，初始化，以便于下次搜索
    for(int i = 0; i < nVerts; i++) {
        vertexList[i].wasVisited = false;
    }
}

5、總結(jié)

圖是由邊連接的頂點(diǎn)組成，圖可以表示許多真實(shí)的世界情況，包括飛機(jī)航線、電子線路等等。搜索算法以一種系統(tǒng)的方式訪問(wèn)圖中的每個(gè)頂點(diǎn)，主要通過(guò)深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS），深度優(yōu)先搜索通過(guò)棧來(lái)實(shí)現(xiàn)，廣度優(yōu)先搜索通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)。最后需要知道最小生成樹是包含連接圖中所有頂點(diǎn)所需要的最少數(shù)量的邊。

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評(píng)論