摘要：圖的定義用圖對現(xiàn)實(shí)中的系統(tǒng)建?？梢杂脠D對現(xiàn)實(shí)中的很多系統(tǒng)建模比如對交通流量建模頂點(diǎn)可以表示街道的十字路口邊可以表示街道加權(quán)的邊可以表示限速或者車道的數(shù)量建模人員可以用這個系統(tǒng)來判斷最佳路線及最有可能堵車的街道任何運(yùn)輸系統(tǒng)都可以用圖來建模比如

可以用圖對現(xiàn)實(shí)中的很多系統(tǒng)建模. 比如對交通流量建模, 頂點(diǎn)可以表示街道的十字路口, 邊可以表示街道. 加權(quán)的邊可以表示限速或者車道的數(shù)量. 建模人員可以用這個系統(tǒng)來判斷最佳路線及最有可能堵車的街道.

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

包含局域網(wǎng)和廣域網(wǎng)(如互聯(lián)網(wǎng))在內(nèi)的計算機(jī)網(wǎng)絡(luò), 同樣經(jīng)常用圖來建模. 另一個可以用圖來建模的現(xiàn)實(shí)系統(tǒng)是消費(fèi)市場, 頂點(diǎn)可以用來表示供應(yīng)商和消費(fèi)者.

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

創(chuàng)建圖類的第一步就是要創(chuàng)建一個Vertex類來保存頂點(diǎn)和邊. 這個類的作用于鏈表和二叉查找樹的Node類一樣. Vertex類有兩個數(shù)據(jù)成員:

label: 表示頂點(diǎn).

wasVisited: 表明這個頂點(diǎn)是否被訪問過的布爾值.

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

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

圖的實(shí)際信息都保存在邊上面, 因?yàn)樗鼈兠枋隽藞D的結(jié)構(gòu). 我們很容易像之前提到的那樣用二叉樹的方式去表示圖, 這是不對的. 二叉樹的表現(xiàn)形式相當(dāng)固定, 一個父節(jié)點(diǎn)只能有兩個子節(jié)點(diǎn), 而圖的結(jié)構(gòu)卻要靈活得多, 一個頂點(diǎn)既可以有一條邊, 也可以有多條邊與它相連.

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

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

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

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

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)
    };
};

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

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

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

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
**/

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

確定從一個指定的頂點(diǎn)可以到達(dá)其他哪些頂點(diǎn), 這是經(jīng)常對圖執(zhí)行的操作. 我們可能想通過地圖了解到從一個城鎮(zhèn)到另一個城鎮(zhèn)的路有哪些, 或者從一個機(jī)場到其它機(jī)場的航班有哪些等.

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

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

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

深度優(yōu)先包括從一條路徑的其實(shí)頂點(diǎn)開始追溯, 直到到達(dá)最后一個頂點(diǎn), 然后回溯, 繼續(xù)追溯下一條路徑, 直到到達(dá)最后的頂點(diǎn), 如此往復(fù), 直到?jīng)]有路徑為止. 這不是在搜索特定的路徑, 而是通過搜索來查看在圖中有哪些路徑可以選擇.
這里盜個圖.

深度優(yōu)先: 訪問一個沒有訪問過的頂點(diǎn), 將它標(biāo)記為已訪問, 再遞歸去訪問在初始頂點(diǎn)的領(lǐng)接表中其它沒有訪問過的頂點(diǎn).

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

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)
    };
    // 深度優(yōu)先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點(diǎn)可以到達(dá): " + 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);

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

這里盜個圖.

廣度優(yōu)先算法使用了抽象的隊(duì)列而不是數(shù)組來對已訪問過的頂點(diǎn)進(jìn)行排序. 算法原理:

查找與當(dāng)前頂點(diǎn)相鄰的未訪問頂點(diǎn), 將其添加到已訪問頂點(diǎn)列表及隊(duì)列中.

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

將所有與v相鄰的未訪問頂點(diǎn)添加到隊(duì)列.

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

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

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

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

首先, 需要一個數(shù)組來保存從一個頂點(diǎn)到下一個頂點(diǎn)的所有的邊. 我們將這個數(shù)組命名為edgeTo. 因?yàn)閺氖贾两K都是使用廣度優(yōu)先算法函數(shù), 所以每次都會遇到一個沒有標(biāo)記的頂點(diǎn), 除了對它進(jìn)行標(biāo)記外, 還會從鄰接列表中我們正在探索的那個頂點(diǎn)添加一條邊到這個頂點(diǎn).

修改了bfs()方法以及在constructor()中定義edgeTo屬性.
我們還需要一個函數(shù)pathTp()用于展示圖中連接到不同頂點(diǎn)的路徑. pathTo()創(chuàng)建一個棧, 用來存儲于指定頂點(diǎn)有共同邊的所有頂點(diǎn). 以及一個簡單的輔助方法: 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 = []; // 保存從一個頂點(diǎn)到下一個頂點(diǎn)的所有邊
        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)
    }
    // 深度優(yōu)先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點(diǎn)可以到達(dá): " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.dfs(i)
            }
        })
    }
    // 廣度優(yōu)先算法
    bfs(s) {
        const queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加至隊(duì)尾
        while (queue.length) {
            const v = queue.shift(); // 從隊(duì)首刪除
            if (this.adj[v] != undefined) {
                log("哪些點(diǎn)可以到達(dá): " + v);
            };
            (this.adj[v] || []).forEach(i => {
                if(!this.marked[i]) {
                    this.edgeTo[i] = v;
                    this.marked[i] = true;
                    queue.push(i);
                }
            })
        }
    }
    // 創(chuàng)建一個棧 存儲于指定頂點(diǎn)有共同邊的所有頂點(diǎn)
    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

也就是從頂點(diǎn)0到頂點(diǎn)4的最短路徑.

-CS1
    |-CS2
        |-匯編語言
        |-數(shù)據(jù)結(jié)構(gòu)
            |-操作系統(tǒng)
            |-算法

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 = []; // 保存從一個頂點(diǎn)到下一個頂點(diǎn)的所有邊
        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(" ");
    }
    // 深度優(yōu)先算法
    dfs(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            log("哪些點(diǎn)可以到達(dá): " + v);
        };
        (this.adj[v] || []).forEach(i => {
            if(!this.marked[i]) {
                this.dfs(i)
            }
        })
    }
    // 廣度優(yōu)先算法
    bfs(s) {
        const queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加至隊(duì)尾
        while (queue.length) {
            const v = queue.shift(); // 從隊(duì)首刪除
            if (this.adj[v] != undefined) {
                log("哪些點(diǎn)可以到達(dá): " + v);
            };
            (this.adj[v] || []).forEach(i => {
                if(!this.marked[i]) {
                    this.edgeTo[i] = v;
                    this.marked[i] = true;
                    queue.push(i);
                }
            })
        }
    }
    // 創(chuàng)建一個棧 存儲于指定頂點(diǎn)有共同邊的所有頂點(diǎn)
    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", "數(shù)據(jù)結(jié)構(gòu)", "匯編語言", "操作系統(tǒng)", "算法" ];
g.showGraph();
g.topSort();

CS1-->
CS2-->CS1 數(shù)據(jù)結(jié)構(gòu) 匯編語言 
數(shù)據(jù)結(jié)構(gòu)-->CS1 CS2 
匯編語言-->CS1 
操作系統(tǒng)-->CS1 
算法-->CS1 
  
CS1
CS2
操作系統(tǒng)
匯編語言
數(shù)據(jù)結(jié)構(gòu)
算法