摘要：圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模比如對交通流量建模頂點可以表示街道的十字路口邊可以表示街道加權的邊可以表示限速或者車道的數量建模人員可以用這個系統來判斷最佳路線及最有可能堵車的街道任何運輸系統都可以用圖來建模比如

可以用圖對現實中的很多系統建模. 比如對交通流量建模, 頂點可以表示街道的十字路口, 邊可以表示街道. 加權的邊可以表示限速或者車道的數量. 建模人員可以用這個系統來判斷最佳路線及最有可能堵車的街道.

任何運輸系統都可以用圖來建模. 比如, 航空公司可以用圖來為其飛行系統建模. 將每個機場看成頂點, 將經過兩個頂點的每條航線看作一條邊. 加權的邊可以表示從一個機場到另一個機場的航班成本, 或兩個機場間的距離, 這取決于建模的對象是什么.

包含局域網和廣域網(如互聯網)在內的計算機網絡, 同樣經常用圖來建模. 另一個可以用圖來建模的現實系統是消費市場, 頂點可以用來表示供應商和消費者.

乍一看, 圖和數或者二叉樹很像, 你可能會嘗試用樹的方式去創建一個圖類, 用節點來表示每一個頂點. 但這種情況下, 如果基于對象的方式去處理就會有問題, 因為圖可能增長到非常大. 用對象來表示圖很快就會變得效率低下, 所以我們要考慮表示頂點和邊的其它方案.

創建圖類的第一步就是要創建一個Vertex類來保存頂點和邊. 這個類的作用于鏈表和二叉查找樹的Node類一樣. Vertex類有兩個數據成員:

label: 表示頂點.

wasVisited: 表明這個頂點是否被訪問過的布爾值.

我們將所有頂點保存到數組中, 在圖類里, 可以通過它們在數組中的位置引用它們.

class Vertex {
    constructor(label, wasVisited) {
        this.label = label;
        this.wasVisited = wasVisited;
    }
};

圖的實際信息都保存在邊上面, 因為它們描述了圖的結構. 我們很容易像之前提到的那樣用二叉樹的方式去表示圖, 這是不對的. 二叉樹的表現形式相當固定, 一個父節點只能有兩個子節點, 而圖的結構卻要靈活得多, 一個頂點既可以有一條邊, 也可以有多條邊與它相連.

我們將表示圖的邊的方法稱為: 鄰接表 或者 _鄰接表數組_. 這種方法將邊存儲為頂點的相鄰頂點列表構成的數組, 并以此頂點作為索引. 使用這種方案, 當我們在程序中引用一個頂點時, 可以高效地訪問與整個頂點相連的所有頂點的列表. 比如, 如果頂點2與頂點0、1、3、4相連, 并且它存儲在數組中索引為2的位置, 那么, 訪問這個元素, 我們可以訪問到索引為2的位置處由頂點0、1、3、4組成的數組. 本章將選用這種表示方法.

0  -->  [2]
1  -->  [2]
2  -->  [0, 1, 3, 4]
3  -->  [2]
4  -->  [2]

另一種表示圖邊的方法被稱為: _鄰接矩陣_. 它是一個二維數組, 其中的元素表示兩個頂點之間是否有一條邊.

確定了如何在代碼中表示圖之后, 構建一個圖的類就容易多了.

class Graph {
    constructor(v) {
        this.vertices = v;
        this.edges = 0;
        this.adj = [];
        for(let i = 0; i < this.vertices; i++) {
            this.adj[i] = [""];
        };
    }
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    showGraph() {
        let str = "";
        for(let i = 0; i < this.vertices; i++) {
            str += i + "-->";
            for(let j = 0; j < this.vertices; j++) {
                if(this.adj[i][j] != undefined) {
                    str += this.adj[i][j] + " ";
                };
            };
            str += "
";
        };
        log(str)
    };
};

這個類會記錄一個圖表示了多少條邊, 并使用一個長度與圖的定點數相同的數組來記錄定點的數量. 通過for循環為數組中的每一個元素添加一個字數組來存儲所有的相鄰頂點, 并將所有元素初始化為空字符串.

添加邊addEdge()這個方法會傳入頂點A和B, 會先查找頂點A的領接表, 將頂點B添加到列表中, 然后再查找頂點B的領接表, 將頂點A加入列表. 最后將邊數edges加1.

showGraph()這個方法會通過打印所有頂點及其相鄰定點列表的方式來顯示圖.

const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();

//輸出
/**
0--> 1 2 
1--> 0 3 
2--> 0 4 
3--> 1 
4--> 2
**/

以上輸出顯示, 下面的用數字0, 1等來代替頂點0, 頂點1.
0有到1和2的邊.
1有到0和3的邊.
2有到0和4的邊.
3有到1的邊.
4有到2的邊.
當然, 這種顯示存在冗余, 例如, 0和1之間的邊和1到0之間的邊相同. 如果只是為了顯示, 這樣是不錯的, 但是在開始探索圖的路徑之前, 需要調整一下輸出.

確定從一個指定的頂點可以到達其他哪些頂點, 這是經常對圖執行的操作. 我們可能想通過地圖了解到從一個城鎮到另一個城鎮的路有哪些, 或者從一個機場到其它機場的航班有哪些等.

圖上的這些操作使用搜索算法執行的. 在圖上可以執行兩種基礎搜索:

深度優先搜索.

廣度優先搜索.

深度優先包括從一條路徑的其實頂點開始追溯, 直到到達最后一個頂點, 然后回溯, 繼續追溯下一條路徑, 直到到達最后的頂點, 如此往復, 直到沒有路徑為止. 這不是在搜索特定的路徑, 而是通過搜索來查看在圖中有哪些路徑可以選擇.
這里盜個圖.

深度優先: 訪問一個沒有訪問過的頂點, 將它標記為已訪問, 再遞歸去訪問在初始頂點的領接表中其它沒有訪問過的頂點.

要讓該算法運行, 需要向Graph類添加一個數組, 用來存儲已訪問過的頂點(marked), 將它所有元素的值全部初始化為false. Graph類的代碼片段顯示了這個新數組及其初始化的過程.

window.log = console.log.bind(console)

class Vertex {
    constructor(label, wasVisited) {
        this.label = label;
        this.wasVisited = wasVisited;
    }
};

class Graph {
    constructor(v) {
        this.vertices = v;
        this.edges = 0;
        this.adj = [];
        this.marked = [];
        for(let i = 0; i < this.vertices; i++) {
            this.adj[i] = [""];
            this.marked[i] = false;
        };
    }
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    showGraph() {
        let str = "";
        for(let i = 0; i < this.vertices; i++) {
            str += i + "-->";
            for(let j = 0; j < this.vertices; j++) {
                if(this.adj[i][j] != undefined) {
                    str += this.adj[i][j] + " ";
                };
            };
            str += "
";
        };
        log(str)
    };
    // 深度優先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點可以到達: " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.dfs(i)
            }
        })
    }
};

const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);

廣度優先從第一個頂點開始, 嘗試訪問盡可能靠近它的頂點. 本質上, 這種搜索在圖上是逐層移動的, 首先檢查最靠近第一個頂點的層, 再逐漸向下移動到離起始頂點最遠層.

這里盜個圖.

廣度優先算法使用了抽象的隊列而不是數組來對已訪問過的頂點進行排序. 算法原理:

查找與當前頂點相鄰的未訪問頂點, 將其添加到已訪問頂點列表及隊列中.

從圖中去除下一個頂點v, 添加到已訪問的頂點列表.

將所有與v相鄰的未訪問頂點添加到隊列.

// 廣度優先算法
bfs(s) {
    const queue = [];
    this.marked[s] = true;
    queue.push(s); // 添加至隊尾
    while (queue.length) {
        const v = queue.shift(); // 從隊首刪除
        if (this.adj[v] != undefined) {
            log("哪些點可以到達: " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.marked[i] = true;
                queue.push(i);
            }
        })
    }
}

圖最常見的操作之一就是尋找從一個頂點到另一個頂點的最短路徑. 考慮下例: 假期中, 你將在兩個星期時間里游歷10大聯盟城市, 去觀看棒球比賽. 你希望通過最短路徑算法, 找出開車游歷這10個大聯盟城市, 去觀看棒球比賽. 你希望通過最短路徑算法, 找出開車游歷這10個城市行駛的最小里程數. 另一個最短路徑問題涉及創建一個計算機網絡時的開銷, 其中包括兩臺電腦之間傳遞數據的時間, 或兩臺電腦建立和維護連接的成本. 最短路徑算法可以幫助確定構建此網絡的最有效方法.

在執行廣度優先時, 會自動查找從一個頂點到另一個頂點的最短路徑. 例如, 要查找從頂點A到頂點D的最短路徑, 我們首先會查找從A到D是否有任何一條單邊路徑, 接著查找兩條邊的路徑, 以此類推. 這是廣度優先算法的過程, 因此我們可以輕松地修改廣度優先算法, 找出最短路徑.

要查找最短路徑, 需要修改廣度優先算法來記錄從一個頂點到另一個頂點的路徑. 需要對Graph類做一些修改.

首先, 需要一個數組來保存從一個頂點到下一個頂點的所有的邊. 我們將這個數組命名為edgeTo. 因為從始至終都是使用廣度優先算法函數, 所以每次都會遇到一個沒有標記的頂點, 除了對它進行標記外, 還會從鄰接列表中我們正在探索的那個頂點添加一條邊到這個頂點.

修改了bfs()方法以及在constructor()中定義edgeTo屬性.
我們還需要一個函數pathTp()用于展示圖中連接到不同頂點的路徑. pathTo()創建一個棧, 用來存儲于指定頂點有共同邊的所有頂點. 以及一個簡單的輔助方法: hasPathTo().

window.log = console.log.bind(console)

class Vertex {
    constructor(label, wasVisited) {
        this.label = label;
        this.wasVisited = wasVisited;
    }
};

class Graph {
    constructor(v) {
        this.vertices = v;
        this.edges = 0;
        this.edgeTo = []; // 保存從一個頂點到下一個頂點的所有邊
        this.adj = [];
        this.marked = [];
        for(let i = 0; i < this.vertices; i++) {
            this.adj[i] = [""];
            this.marked[i] = false;
        };
    }
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    showGraph() {
        let str = "";
        for(let i = 0; i < this.vertices; i++) {
            str += i + "-->";
            for(let j = 0; j < this.vertices; j++) {
                if(this.adj[i][j] != undefined) {
                    str += this.adj[i][j] + " ";
                };
            };
            str += "
";
        };
        log(str)
    }
    // 深度優先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點可以到達: " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.dfs(i)
            }
        })
    }
    // 廣度優先算法
    bfs(s) {
        const queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加至隊尾
        while (queue.length) {
            const v = queue.shift(); // 從隊首刪除
            if (this.adj[v] != undefined) {
                log("哪些點可以到達: " + v);
            };
            (this.adj[v] || []).forEach(i => {
                if(!this.marked[i]) {
                    this.edgeTo[i] = v;
                    this.marked[i] = true;
                    queue.push(i);
                }
            })
        }
    }
    // 創建一個棧 存儲于指定頂點有共同邊的所有頂點
    pathTo(v) {
        const source = 0;
        if (!this.hasPathTo(v)) {
            return undefined;
        };

        const path = [];
        for (let i = v; i != source; i = this.edgeTo[i]) {
            path.push(i);
        };
        path.push(source);
        return path;
    }
    hasPathTo(v) {
        return this.marked[v];
    }
};

const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.bfs(0);
const vertex = 4;
const paths = g.pathTo(vertex);
let res = "";
while (paths.length > 0) {
    if (paths.length > 1) {
        res += paths.pop() + "-";
    } else {
        res += paths.pop();
    }
};
log(res);

輸出:

0-2-4

也就是從頂點0到頂點4的最短路徑.

拓撲排序 會對有向圖的所有頂點進行排序, 使有向邊從前面的頂點指向后面的頂點. eg:

-CS1
    |-CS2
        |-匯編語言
        |-數據結構
            |-操作系統
            |-算法

這個例子的拓撲排序將會是一下序列:

CS1

CS2

匯編語言

數據結構

操作系統

算法

課程3和課程4可以同時上, 課程5和課程6也可以.

這類問題被稱為 優先級約束調度 , 每個大學生對此都很熟悉. 就好像只有先上過大學英語1的課程才能上大學英語2的課程一樣.

拓撲排序算法與深度優先算法類似. 不同的是, 拓撲排序算法不會立即輸出已訪問的頂點, 而是訪問當前頂點鄰接表中的所有相鄰頂點, 直到這個列表窮盡時, 才將當前頂點壓入棧中.

拓撲排序算法被拆分為兩個方法. 第一個topSort(), 會設置排序進程并調用一個輔助方法topSortHelper(), 然后顯示排序號的頂點列表.

主要工作實在遞歸方法topSortHelper()中完成的. 這個方法會將當前頂點標記為已訪問, 然后遞歸訪問當前頂點領接表中的每個相鄰頂點, 標記這些頂點為已訪問. 最后 將當前頂點壓入棧.

Graph類也將被修改, 這樣不僅可以用于數字頂點, 還可以用于符號頂點. 在代碼中, 每個頂點都只標注了數字, 但是我們添加了一個vertexList數組, 將各個頂點關聯到一個符號(上面的課程名稱).

下面將展示整個部分的完整定義, 包括用于拓撲排序的方法, 以確保Graph類的新的定義更清晰. showGraph()方法也將被修改, 這樣可以顯示符號名稱而不只是顯示頂點數字.

window.log = console.log.bind(console)

class Vertex {
    constructor(label) {
        this.label = label;
    }
};

class Graph {
    constructor(v) {
        this.vertices = v;
        this.vertexList = [];
        this.edges = 0;
        this.edgeTo = []; // 保存從一個頂點到下一個頂點的所有邊
        this.adj = [];
        this.marked = [];
        for(let i = 0; i < this.vertices; i++) {
            this.adj[i] = [];
            this.marked[i] = false;
        };
    }
    topSort() {
        const stack = [];
        const visited = [];
        for (let i = 0; i < this.vertices; i++) {
            visited[i] = false;
        };
        for (let i = 0; i < this.vertices; i++) {
            if (visited[i] == false) {
                this.topSortHelper(i, visited, stack);
            }
        };
        for (let i = stack.length - 1; i >= 0; i--) {
            log(this.vertexList[stack[i]])
        };
    }
    topSortHelper(v, visited, stack) {
        visited[v] = true;

        (this.adj[v] || []).forEach(w => {
            if (!visited[w]) {
                this.topSortHelper(w, visited, stack)
            }
        });
        stack.push(v)
    }
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    showGraph() {
        var visited = [];
        for (let i = 0; i < this.vertices; i++) {
            let str = this.vertexList[i] + "-->";
            visited.push(this.vertexList[i]);
            for (let j = 0; j < this.vertices; j++) {
                if (this.adj[i][j] != undefined) {
                    if (visited.indexOf(this.vertexList[j]) < 0) {
                        str += this.vertexList[j] + " ";
                    }
                }
            };
            visited.pop();
            log(str)
        };
        log(" ");
    }
    // 深度優先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點可以到達: " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.dfs(i)
            }
        })
    }
    // 廣度優先算法
    bfs(s) {
        const queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加至隊尾
        while (queue.length) {
            const v = queue.shift(); // 從隊首刪除
            if (this.adj[v] != undefined) {
                log("哪些點可以到達: " + v);
            };
            (this.adj[v] || []).forEach(i => {
                if(!this.marked[i]) {
                    this.edgeTo[i] = v;
                    this.marked[i] = true;
                    queue.push(i);
                }
            })
        }
    }
    // 創建一個棧 存儲于指定頂點有共同邊的所有頂點
    pathTo(v) {
        const source = 0;
        if (!this.hasPathTo(v)) {
            return undefined;
        };

        const path = [];
        for (let i = v; i != source; i = this.edgeTo[i]) {
            path.push(i);
        };
        path.push(source);
        return path;
    }
    hasPathTo(v) {
        return this.marked[v];
    }
};

const g = new Graph(6);
g.addEdge(1, 2);
g.addEdge(2, 5);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(0, 1);
g.vertexList = [ "CS1", "CS2", "數據結構", "匯編語言", "操作系統", "算法" ];
g.showGraph();
g.topSort();

輸出結果:

CS1-->
CS2-->CS1 數據結構 匯編語言 
數據結構-->CS1 CS2 
匯編語言-->CS1 
操作系統-->CS1 
算法-->CS1 
  
CS1
CS2
操作系統
匯編語言
數據結構
算法