JavaScript數據結構——圖的實現

来源:https://www.cnblogs.com/jaxu/archive/2019/08/14/11338294.html
-Advertisement-
Play Games

在電腦科學中，圖是一種網路結構的抽象模型，它是一組由邊連接的頂點組成。一個圖G = (V, E)由以下元素組成： V：一組頂點 E：一組邊，連接V中的頂點 下圖表示了一個圖的結構： 在介紹如何用JavaScript實現圖之前，我們先介紹一些和圖相關的術語。 如上圖所示，由一條邊連接在一起的頂點稱為 ...


　　在電腦科學中，圖是一種網路結構的抽象模型，它是一組由邊連接的頂點組成。一個圖G = (V, E)由以下元素組成：

  • V：一組頂點
  • E：一組邊，連接V中的頂點

　　下圖表示了一個圖的結構：

　　在介紹如何用JavaScript實現圖之前，我們先介紹一些和圖相關的術語。

　　如上圖所示，由一條邊連接在一起的頂點稱為相鄰頂點，A和B是相鄰頂點，A和D是相鄰頂點，A和C是相鄰頂點......A和E是不相鄰頂點。一個頂點的度是其相鄰頂點的數量，A和其它三個頂點相連，所以A的度為3，E和其它兩個頂點相連，所以E的度為2......路徑是一組相鄰頂點的連續序列，如上圖中包含路徑ABEI、路徑ACDG、路徑ABE、路徑ACDH等。簡單路徑要求路徑中不包含有重覆的頂點，如果將環的最後一個頂點去掉，它也是一個簡單路徑。例如路徑ADCA是一個環，它不是一個簡單路徑，如果將路徑中的最後一個頂點A去掉，那麼它就是一個簡單路徑。如果圖中不存在環，則稱該圖是無環的。如果圖中任何兩個頂點間都存在路徑，則該圖是連通的，如上圖就是一個連通圖。如果圖的邊沒有方向，則該圖是無向圖，上圖所示為無向圖，反之則稱為有向圖，下圖所示為有向圖：

　　在有向圖中，如果兩個頂點間在雙向上都存在路徑，則稱這兩個頂點是強連通的，如上圖中C和D是強連通的，而A和B是非強連通的。如果有向圖中的任何兩個頂點間在雙向上都存在路徑，則該有向圖是強連通的，非強連通的圖也稱為稀疏圖。

　　此外，圖還可以是加權的。前面我們看到的圖都是未加權的，下圖為一個加權的圖：

　　可以想象一下，前面我們介紹的樹和鏈表也屬於圖的一種特殊形式。圖在電腦科學中的應用十分廣泛，例如我們可以搜索圖中的一個特定頂點或一條特定的邊，或者尋找兩個頂點間的路徑以及最短路徑，檢測圖中是否存在環等等。

　　存在多種不同的方式來實現圖的數據結構，下麵介紹幾種常用的方式。

鄰接矩陣

　　在鄰接矩陣中，我們用一個二維數組來表示圖中頂點之間的連接，如果兩個頂點之間存在連接，則這兩個頂點對應的二維數組下標的元素的值為1，否則為0。下圖是用鄰接矩陣方式表示的圖：

　　如果是加權的圖，我們可以將鄰接矩陣中二維數組裡的值1改成對應的加權數。鄰接矩陣方式存在一個缺點，如果圖是非強連通的，則二維數組中會有很多的0，這表示我們使用了很多的存儲空間來表示根本不存在的邊。另一個缺點就是當圖的頂點發生改變時，對於二維數組的修改會變得不太靈活。

鄰接表

　　圖的另外一種實現方式是鄰接表，它是對鄰接矩陣的一種改進。鄰接表由圖中每個頂點的相鄰頂點列表所組成。如下圖所示，我們可以用數組、鏈表、字典或散列表來表示鄰接表。

關聯矩陣

　　我們還可以用關聯矩陣來表示圖。在關聯矩陣中，矩陣的行表示頂點，列表示邊。關聯矩陣通常用於邊的數量比頂點多的情況下，以節省存儲空間。如下圖所示為關聯矩陣方式表示的圖：

　　下麵我們重點看下如何用鄰接表的方式表示圖。我們的Graph類的骨架如下，它用鄰接表方式來實現無向圖：

class Graph {
    constructor () {
        this.vertices = []; // 用來存放圖中的頂點
        this.adjList = new Dictionary(); // 用來存放圖中的邊
    }

    // 向圖中添加一個新頂點
    addVertex (v) {}

    // 向圖中添加a和b兩個頂點之間的邊
    addEdge (a, b) {}
}

　　在Graph類中，我們用數組vertices來保存圖中的所有頂點，用字典（請參考《JavaScript數據結構——字典和散列表的實現》一文中的Dictionary類）adjList來保存圖中每一個頂點到相鄰頂點的關係列表，在字典中，頂點被作為鍵值。請參考前面我們給出的鄰接表的示意圖。然後在Graph類中，我們提供兩個方法，方法addVertex()用來向圖中添加一個新頂點，方法addEdge()用來向圖中添加給定的頂點a和頂點b之間的邊。讓我們來看下這兩個方法的實現。

addVertex (v) {
    if (!this.vertices.includes(v)) {
        this.vertices.push(v);
        this.adjList.set(v, []);
    }
}

　　要添加一個新頂點，首先要判斷該頂點在圖中是否已經存在了，如果已經存在則不能添加。如果不存在，就在vertices數組中添加一個新元素，然後在字典adjList中添加一個以該頂點作為key的新元素，值為空數組。

addEdge (a, b) {
    // 如果圖中沒有頂點a，先添加頂點a
    if (!this.adjList.has(a)) {
        this.addVertex(a);
    }
    // 如果圖中沒有頂點b，先添加頂點b
    if (!this.adjList.has(b)) {
        this.addVertex(b);
    }

    this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊
    this.adjList.get(b).push(a); // 在頂點b中添加指向頂點a的邊
}

　　addEdge()方法也很簡單，首先要確保給定的兩個頂點a和b在圖中必須存在，如果不存在，則調用addVertex()方法進行添加，然後分別在字典中找到鍵值為頂點a和鍵值為頂點b的元素，在對應的值中添加一個新元素。
　　下麵是Graph類的完整代碼，其中的toString()方法是為了我們測試用的，它的存在不是必須的。

 1 class Graph {
 2     constructor () {
 3         this.vertices = []; // 用來存放圖中的頂點
 4         this.adjList = new Dictionary(); // 用來存放圖中的邊
 5     }
 6 
 7     // 向圖中添加一個新頂點
 8     addVertex (v) {
 9         if (!this.vertices.includes(v)) {
10             this.vertices.push(v);
11             this.adjList.set(v, []);
12         }
13     }
14 
15     // 向圖中添加a和b兩個頂點之間的邊
16     addEdge (a, b) {
17         // 如果圖中沒有頂點a，先添加頂點a
18         if (!this.adjList.has(a)) {
19             this.addVertex(a);
20         }
21         // 如果圖中沒有頂點b，先添加頂點b
22         if (!this.adjList.has(b)) {
23             this.addVertex(b);
24         }
25 
26         this.adjList.get(a).push(b); // 在頂點a中添加指向頂點b的邊
27         this.adjList.get(b).push(a); // 在頂點b中添加指向頂點a的邊
28     }
29 
30     // 獲取圖的vertices
31     getVertices () {
32         return this.vertices;
33     }
34 
35     // 獲取圖中的adjList
36     getAdjList () {
37         return this.adjList;
38     }
39 
40     toString() {
41         let s = '';
42         this.vertices.forEach((v) => {
43             s += `${v} -> `;
44             this.adjList.get(v).forEach((n) => {
45                 s += `${n} `;
46             });
47             s += '\n';
48         });
49         return s;
50     }
51 }
Graph

　　對於本文一開始給出的圖，我們添加下麵的測試用例：

let graph = new Graph();
let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
myVertices.forEach((v) => {
    graph.addVertex(v);
});
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());

　　下麵是測試結果：

A -> B C D 
B -> A E F 
C -> A D G 
D -> A C G H 
E -> B I 
F -> B 
G -> C D 
H -> D 
I -> E

　　可以看到，與示意圖是相符合的。

　　和樹類似，我們也可以對圖進行遍歷，以訪問圖中的所有頂點。圖的遍歷方式分為兩種：廣度優先（Breadth-First Search，BFS）和深度優先（Depth-First Search，DFS）。對圖的遍歷可以用來尋找特定的頂點或兩個頂點之間的最短路徑，以及檢查圖是否連通、圖中是否含有環等。

演算法 數據結構 描述
深度優先 棧 將圖的頂點存入棧中（有關棧的介紹可以參考《JavaScript數據結構——棧的實現與應用》），頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問。
廣度優先 隊列 將圖的頂點存入隊列中（有關隊列的介紹可以參考《JavaScript數據結構——隊列的實現與應用》），最先入隊列的頂點先被探索。

　　在接下來要實現的演算法中，我們按照如下的約定對圖中的頂點進行遍歷，每個頂點最多訪問兩次：

  • 白色：表示該頂點未被訪問。
  • 灰色：表示該頂點被訪問過，但未被探索。
  • 黑色：表示該頂點被訪問並且被探索過。

廣度優先

　　廣度優先演算法會從指定的第一個頂點開始遍歷圖，先訪問這個頂點的所有相鄰頂點，然後再訪問這些相鄰頂點的相鄰頂點，以此類推。最終，廣度優先演算法會先廣後深地訪問圖中的所有頂點。下麵是廣度優先遍歷的示意圖：

　　由於我們採用鄰接表的方式來存儲圖的數據，對於圖的每個頂點，都有一個字典與之對應，字典的鍵值為頂點的值，字典的內容為與該頂點相鄰的頂點列表。基於這種數據結構，我們可以考慮將所有頂點的鄰接頂點存入隊列，然後依次處理隊列中的頂點。下麵是具體的遍歷步驟：

  1. 將開始頂點存入隊列。
  2. 遍歷開始頂點的所有鄰接頂點，如果這些鄰接頂點沒有被訪問過（顏色為白色），則將它們標記為被訪問（顏色為灰色），然後加入隊列。
  3. 將開始頂點標記為被處理（顏色為黑色）。
  4. 迴圈處理隊列中的頂點，直到隊列為空。

　　下麵是該演算法的具體實現：

let Colors = {
    WHITE: 0,
    GREY: 1,
    BLACK: 2
};

let initializeColor = vertices => {
    let color = {};
    vertices.forEach(v => color[v] = Colors.WHITE);
    return color;
};

let breadthFirstSearch = (graph, startVertex, callback) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let queue = new Queue();

    queue.enqueue(startVertex);

    while (!queue.isEmpty()) {
        let u = queue.dequeue();
        adjList.get(u).forEach(n => {
            if (color[n] === Colors.WHITE) {
                color[n] = Colors.GREY;
                queue.enqueue(n);
            }
        });


        color[u] = Colors.BLACK;
        if (callback) callback(u);
    }
};

　　breadthFirstSearch()方法接收一個graph對象，圖的數據通過該對象傳入。參數startVertex指定了遍歷的起始頂點。回調函數callback規定了要如何處理被遍歷到的頂點。

　　首先通過initializeColor()函數將所有的頂點標記為未被訪問過（顏色為白色），這些顏色保存在以頂點值為key的color對象中。圖的vertices和adjList屬性可以通過getVertices()和getAdjList()方法得到，然後構造一個隊列queue（有關隊列類Queue請參考《JavaScript數據結構——隊列的實現與應用》），按照上面描述的步驟對圖的頂點進行遍歷。

　　在前面我們給出的測試用例的基礎上，添加下麵的代碼，來看看breadthFirstSearch()方法的執行結果：

breadthFirstSearch(graph, 'A', value => console.log(`visited vertex: ${value}`));

　　參數graph為前面測試用例中Graph類的實例，也就是我們用來保存圖的數據的對象，'A'被作為遍歷的起始頂點，在回調函數中，列印一行文本，用來展示頂點被遍歷的順序。下麵是測試結果：

visited vertex: A
visited vertex: B
visited vertex: C
visited vertex: D
visited vertex: E
visited vertex: F
visited vertex: G
visited vertex: H
visited vertex: I

　　嘗試將'I'作為起始頂點，看看執行結果：

visited vertex: I
visited vertex: E
visited vertex: B
visited vertex: A
visited vertex: F
visited vertex: C
visited vertex: D
visited vertex: G
visited vertex: H

　　為了方便理解，我們將頂點I放到最上面。從頂點I開始，首先遍歷到的是它的相鄰頂點E，然後是E的相鄰頂點B，其次是B的相鄰頂點A和F，A的相鄰頂點C和D，C的相鄰頂點G（D已經被遍歷過了），最後是D的相鄰頂點H（C和G已經被遍歷過了）。

尋找最短路徑

　　前面展示了廣度優先演算法的工作原理，我們可以使用它做更多的事情，例如在一個圖G中，從頂點v開始到其它所有頂點間的最短距離。我們考慮一下如何用BFS來實現尋找最短路徑。

　　假設兩個相鄰頂點間的距離為1，從頂點v開始，在其路徑上每經過一個頂點，距離加1。下麵是對breadthFirstSearch()方法的改進，用來返回從起始頂點開始到其它所有頂點間的距離，以及所有頂點的前置頂點。

let BFS = (graph, startVertex) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let queue = new Queue();
    let distances = {};
    let predecessors = {};

    queue.enqueue(startVertex);

    // 初始化所有頂點的距離為0，前置節點為null
    vertices.forEach(v => {
        distances[v] = 0;
        predecessors[v] = null;
    });

    while (!queue.isEmpty()) {
        let u = queue.dequeue();
        adjList.get(u).forEach(n => {
            if (color[n] === Colors.WHITE) {
                color[n] = Colors.GREY;
                distances[n] = distances[u] + 1;
                predecessors[n] = u;
                queue.enqueue(n);
            }
        });


        color[u] = Colors.BLACK;
    }

    return {distances, predecessors};
};

　　在BFS()方法中，我們定義了兩個對象distances和predecessors，用來保存從起始頂點出發到其它所有頂點的距離以及這些頂點的前置頂點。BFS()方法不需要callback回調函數，因為它會自行輸出最終結果。與breadthFirstSearch()方法的邏輯類似，只不過在開始的時候將所有頂點的距離初始化為0，前置頂點初始化為null，然後在遍歷的過程中，重新設置頂點的distances值和predecessors值。我們仍然將頂點A作為起始頂點，來看看測試結果：

console.log(BFS(graph, 'A'));
{
  distances: { A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 },
  predecessors: {
    A: null,
    B: 'A',
    C: 'A',
    D: 'A',
    E: 'B',
    F: 'B',
    G: 'C',
    H: 'D',
    I: 'E'
  }
}

　　如你所見，distances為從頂點A開始到其它所有頂點的最短距離（相鄰頂點間的距離為1），predecessors記錄了所有頂點的前置頂點。以BFS()方法的返回結果為基礎，通過下麵的代碼，我們可以得出從頂點A開始到其它所有頂點的最短路徑：

let shortestPathA = BFS(graph, 'A');
let startVertex = 'A';
myVertices.forEach(v => {
    let path = new Stack();
    for (let v2 = v; v2 !== startVertex; v2 = shortestPathA.predecessors[v2]) {
        path.push(v2);
    }

    path.push(startVertex);
    let s = path.pop();
    while (!path.isEmpty()) {
        s += ` - ${path.pop()}`;
    }

    console.log(s);
});

　　其中的Stack類可以參考《JavaScript數據結構——棧的實現與應用》。下麵是對應的執行結果：

A
A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I

 　　以上我們說的都是未加權的圖，對於加權的圖，廣度優先演算法並不是最合適的。下麵給出了另外幾種最短路徑演算法：

Dijkstra - 尋找從指定頂點到其它所有頂點的最短路徑的貪心演算法。

 1 const INF = Number.MAX_SAFE_INTEGER;
 2 const minDistance = (dist, visited) => {
 3   let min = INF;
 4   let minIndex = -1;
 5   for (let v = 0; v < dist.length; v++) {
 6     if (visited[v] === false && dist[v] <= min) {
 7       min = dist[v];
 8       minIndex = v;
 9     }
10   }
11   return minIndex;
12 };
13 const dijkstra = (graph, src) => {
14   const dist = [];
15   const visited = [];
16   const { length } = graph;
17   for (let i = 0; i < length; i++) {
18     dist[i] = INF;
19     visited[i] = false;
20   }
21   dist[src] = 0;
22   for (let i = 0; i < length - 1; i++) {
23     const u = minDistance(dist, visited);
24     visited[u] = true;
25     for (let v = 0; v < length; v++) {
26       if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
27         dist[v] = dist[u] + graph[u][v];
28       }
29     }
30   }
31   return dist;
32 };
dijkstra

Floyd-Warshall - 計算圖中所有最短路徑的動態規划算法。

 1 const floydWarshall = graph => {
 2   const dist = [];
 3   const { length } = graph;
 4   for (let i = 0; i < length; i++) {
 5     dist[i] = [];
 6     for (let j = 0; j < length; j++) {
 7       if (i === j) {
 8         dist[i][j] = 0;
 9       } else if (!isFinite(graph[i][j])) {
10         dist[i][j] = Infinity;
11       } else {
12         dist[i][j] = graph[i][j];
13       }
14     }
15   }
16   for (let k = 0; k < length; k++) {
17     for (let i = 0; i < length; i++) {
18       for (let j = 0; j < length; j++) {
19         if (dist[i][k] + dist[k][j] < dist[i][j]) {
20           dist[i][j] = dist[i][k] + dist[k][j];
21         }
22       }
23     }
24   }
25   return dist;
26 };
floydWarshall

Kruskal - 求解加權無向連通圖的最小生成樹（MST）的貪心演算法。

 1 const INF = Number.MAX_SAFE_INTEGER;
 2 const find = (i, parent) => {
 3   while (parent[i]) {
 4     i = parent[i]; // eslint-disable-line prefer-destructuring
 5   }
 6   return i;
 7 };
 8 const union = (i, j, parent) => {
 9   if (i !== j) {
10     parent[j] = i;
11     return true;
12   }
13   return false;
14 };
15 const initializeCost = graph => {
16   const cost = [];
17   const { length } = graph;
18   for (let i = 0; i < length; i++) {
19     cost[i] = [];
20     for (let j = 0; j < length; j++) {
21       if (graph[i][j] === 0) {
22         cost[i][j] = INF;
23       } else {
24         cost[i][j] = graph[i][j];
25       }
26     }
27   }
28   return cost;
29 };
30 const kruskal = graph => {
31   const { length } = graph;
32   const parent = [];
33   let ne = 0;
34   let a;
35   let b;
36   let u;
37   let v;
38   const cost = initializeCost(graph);
39   while (ne < length - 1) {
40     for (let i = 0, min = INF; i < length; i++) {
41       for (let j = 0; j < length; j++) {
42         if (cost[i][j] < min) {
43           min = cost[i][j];
44           a = u = i;
45           b = v = j;
46         }
47       }
48     }
49     u = find(u, parent);
50     v = find(v, parent);
51     if (union(u, v, parent)) {
52       ne++;
53     }
54     cost[a][b] = cost[b][a] = INF;
55   }
56   return parent;
57 };
kruskal

Prime - 求解加權無向連通圖的最小生成樹（MST）的貪心演算法。

 1 const INF = Number.MAX_SAFE_INTEGER;
 2 const minKey = (graph, key, visited) => {
 3   // Initialize min value
 4   let min = INF;
 5   let minIndex = 0;
 6   for (let v = 0; v < graph.length; v++) {
 7     if (visited[v] === false && key[v] < min) {
 8       min = key[v];
 9       minIndex = v;
10     }
11   }
12   return minIndex;
13 };
14 const prim = graph => {
15   const parent = [];
16   const key = [];
17   const visited = [];
18   const { length } = graph;
19   for (let i = 0; i < length; i++) {
20     key[i] = INF;
21     visited[i] = false;
22   }
23   key[0] = 0;
24   parent[0] = -1;
25   for (let i = 0; i < length - 1; i++) {
26     const u = minKey(graph, key, visited);
27     visited[u] = true;
28     for (let v = 0; v < length; v++) {
29       if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
30         parent[v] = u;
31         key[v] = graph[u][v];
32       }
33     }
34   }
35   return parent;
36 };
prim

深度優先

　　深度優先演算法從圖的第一個頂點開始，沿著這個頂點的一條路徑遞歸查找到最後一個頂點，然後返回並探查路徑上的其它路徑，直到所有路徑都被訪問到。最終，深度優先演算法會先深後廣地訪問圖中的所有頂點。下麵是深度優先遍歷的示意圖：

　　我們仍然採用和廣度優先演算法一樣的思路，一開始將所有的頂點初始化為白色，然後沿著路徑遞歸探查其餘頂點，當頂點被訪問過，將顏色改為灰色，如果頂點被探索過（處理過），則將顏色改為黑色。下麵是深度優先演算法的具體實現：

let depthFirstSearchVisit = (u, color, adjList, callback) => {
    color[u] = Colors.GREY;
    if (callback) callback(u);

    adjList.get(u).forEach(n => {
        if (color[n] === Colors.WHITE) {
            depthFirstSearchVisit(n, color, adjList, callback);
        }
    });

    color[u] = Colors.BLACK;
};

let depthFirstSearch = (graph, callback) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);

    vertices.forEach(v => {
        if (color[v] === Colors.WHITE) {
            depthFirstSearchVisit(v, color, adjList, callback);
        }
    });
};

　　具體執行步驟為：

  1. 將圖中所有頂點的顏色初始化為白色。
  2. 遍歷頂點，此時A作為第一個頂點，它的顏色為白色，於是調用函數depthFirstSearchVisit()，並將頂點A、color、graph.adjList作為參數傳入。
  3. 在depthFirstSearchVisit()函數內部，由於頂點A被訪問過了，所以將顏色設置為灰色，並執行callback回調函數（如果存在），然後遍歷A的鄰接頂點B、C、D。
  4. B未被訪問過，顏色為白色，所以將B作為參數遞歸調用depthFirstSearchVisit()函數。B設置為灰色，callback('B')。遍歷B的鄰接節點E和F。
  5. E未被訪問過，顏色為白色，所以將E作為參數遞歸調用depthFirstSearchVisit()函數。E設置為灰色，callback('E')。遍歷E的鄰接節點I。
  6. I未被訪問過，顏色為白色，所以將I作為參數遞歸調用depthFirstSearchVisit()函數。I設置為灰色，callback('I')。I沒有鄰接節點，然後將I設置為黑色。遞歸返回到5。
  7. E沒有其它鄰接節點，將E設置為黑色。遞歸返回到4。
  8. 遍歷B的另一個鄰接節點F，F未被訪問過，顏色為白色，所以將F作為參數遞歸調用depthFirstSearchVisit()函數。F設置為灰色，callback('F')。F沒有鄰接節點，然後將F設置為黑色。遞歸返回到4。
  9. B的所有鄰接節點都被訪問過了，將B設置為黑色。遞歸返回到3。
  10. 訪問A的第二個鄰接節點C，C未被訪問過，顏色為白色，所以將C作為參數遞歸調用depthFirstSearchVisit()函數。C設置為灰色，callback('C')。遍歷C的鄰接節點D、G。
  11. D未被訪問過，顏色為白色，所以將D作為參數遞歸調用depthFirstSearchVisit()函數。D設置為灰色，callback('D')。遍歷D的鄰接節點G和H。
  12. G未被訪問過，顏色為白色，所以將G作為參數遞歸調用depthFirstSearchVisit()函數。G設置為灰色，callback('G')。G沒有鄰接節點，然後將G設置為黑色。遞歸返回到11。
  13. 遍歷D的另一個鄰接節點H，H未被訪問過，顏色為白色，所以將H作為參數遞歸調用depthFirstSearchVisit()函數。H設置為灰色，callback('H')。H沒有鄰接節點，然後將H設置為黑色。遞歸返回到11。
  14. D的所有鄰接節點都被訪問過了，將D設置為黑色。遞歸返回到10。
  15. 遍歷C的另一個鄰接節點G，由於G已經被訪問過，對C的鄰接節點的遍歷結束。將C設置為黑色。遞歸返回到3。
  16. 訪問A的最後一個鄰接節點D，由於D已經被訪問過，對A的鄰接節點的遍歷結束。將A設置為黑色。
  17. 然後對剩餘的節點進行遍歷。由於剩餘的節點都被設置為黑色了，所以程式結束。

　　對應的測試用例及執行結果如下：

depthFirstSearch(graph, value => console.log(`visited vertex: ${value}`));
visited vertex: A
visited vertex: B
visited vertex: E
visited vertex: I
visited vertex: F
visited vertex: C
visited vertex: D
visited vertex: G
visited vertex: H

　　為了便於理解，我們將整個遍歷過程用下麵的示意圖來展示：

　　前面說過，深度優先演算法的數據結構是棧，然而這裡我們並沒有使用棧來存儲任何數據，而是使用了函數的遞歸調用，其實遞歸也是棧的一種表現形式。另外一點，如果圖是連通的（即圖中任何兩個頂點之間都存在路徑），我們可以對上述代碼中的depthFirstSearch()方法進行改進，只需要對圖的起始頂點開始遍歷一次就可以了，而不需要遍歷圖的所有頂點，因為從起始頂點開始的遞歸就可以覆蓋圖的所有頂點。

拓撲排序

　　前面展示了深度優先演算法的工作原理，我們可以使用它做更多的事情，例如拓撲排序（toplogical sorting，也叫做topsort或者toposort）。與廣度優先演算法類似，我們也對上面的depthFirstSeach()方法進行改進，以說明如何使用深度優先演算法來實現拓撲排序：

let DFSVisit = (u, color, discovery, finished, predecessors, time, adjList) => {
    color[u] = Colors.GREY;
    discovery[u] = ++time.count;

    adjList.get(u).forEach(n => {
        if (color[n] === Colors.WHITE) {
            predecessors[n] = u;
            DFSVisit(n, color, discovery, finished, predecessors, time, adjList);
        }
    });

    color[u] = Colors.BLACK;
    finished[u] = ++time.count;
};

let DFS = graph => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let discovery = {};
    let finished = {};
    let predecessors = {};
    let time = { count: 0 };

    vertices.forEach(v => {
        finished[v] = 0;
        discovery[v] = 0;
        predecessors[v] = null;
    });

    vertices.forEach(v => {
        if (color[v] === Colors.WHITE) {
            DFSVisit(v, color, discovery, finished, predecessors, time, adjList);
        }
    });

    return {discovery, finished, predecessors};
};

　　DFS()方法會輸出圖中每個頂點的發現時間和探索時間，我們假定時間從0開始，每經過一步時間值加1。在DFS()方法中，我們用變數discovery，finished，predecessors來保存每個頂點的發現時間、探索時間和前置頂點（這個和廣度優先演算法中尋找最短路徑中的一致，但最終執行結果會有區別），最終的輸出結果中也會反映這三個值。這裡需要註意的是，變數time之所以被定義為對象而不是一個普通的數字，是因為我們需要在函數間傳遞這個變數，如果只是作為值傳遞，函數內部對變數的修改不會影響到它的原始值，但是我們就是需要在函數遞歸調用的過程中不斷記錄time的變化過程，所以採用值傳遞的方式顯然不行。因此我們將time定義為一個對象，對象被作為引用傳遞給函數，這樣在函數內部對它的修改就會反映到原始值上。

　　來看看對DFS()方法的測試結果：

console.log(DFS(graph));
{
  discovery: { A: 1, B: 2, C: 10, D: 11, E: 3, F: 7, G: 12, H: 14, I: 4 },
  finished: { A: 18, B: 9, C: 17, D: 16, E: 6, F: 8, G: 13, H: 15, I: 5 },
  predecessors: {
    A: null,
    B: 'A',
    C: 'A',
    D: 'C',
    E: 'B',
    F: 'B',
    G: 'D',
    H: 'D',
    I: 'E'
  }
}

　　我們將結果反映到示意圖上，這樣更加直觀：

　　示意圖上每一個頂點左邊的數字是頂點的發現時間，右邊的數字是頂點的探索時間，全部完成時間是18，可以結合前面的深度優先演算法遍歷過程

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 背景線條實現
    背景線條實現 原文：goodallocator ...
  • 純手寫實現ajax分頁功能
    前言 最近用到了這個功能，百度大半天，網上的不是有各種問題就是需要引入其他的插件，無奈，只能自己寫，大致功能已經完成。前端頁面用bootstrap做樣式，分頁功能用ajax實現，沒用其他插件哦，只引入引這些： 簡介 相關概念： ajax：非同步的javascript和xml 指的是在不刷新網頁的情況下 ...
  • JavaScript之基本包裝類型
    為了能更好的操作基本類型值，JavaScript提供了3個特殊的引用類型：Boolean，Number和String。這些引用類型和傳統對象相似，有自己的屬性和方法，但也具備各自的特殊行為。 一 基本包裝類型簡介 我們知道，基本類型的值是沒有屬性和方法的，不能被改變的。但是上面3個特殊的引用類型賦予 ...
  • js中的數組去掉空值
    //result 是有空值的數組//r是處理好的數組var r = result.filter(function (s) { return s && s.trim();}); ...
  • jsTree樹插件
    前言 關於樹的數據展示，前後用過兩個插件，一是zTree，二是jsTree，無論是提供的例子（可下載），還是提供的API在查找時的便捷程度，zTree比jsTree強多了，也很容易上手，所以這裡只講下jsTree的使用 官網：https://www.jstree.com 中文API文檔：https: ...
  • js工廠函數創建對象與對象構造函數的理解
    工廠函數，顧名思義，就是通過一個＂工廠的加工＂ 來創建一個函數 這種操作在需要創建多個相似對象時可以有效地減少重覆代碼，但是這樣有個缺點就是，每次調用工廠函數創建的對象都是獨立的object，不存在繼承關係，顯然，這樣的面向對象編程失去了靈魂 於是, 對象構造函數就出現了 使用構造函數有幾個要註意的 ...
  • Vue觸發隱藏input file的方法
    1、使用input透明覆蓋法 將input的z-index設置為1以上的數字並覆蓋到需點擊的內容上，將input的樣式opacity設置為0（即為透明度為0），這樣通過綁定在input上的change事件觸發 推薦 2、使用vue的ref參數直接操作input的點擊事件觸發 3、使用HTML的lab ...
  • Vue中jsx的最簡單用法
    最終頁面顯示效果為 主頁面 parent.vue 子頁面child.vue有兩種方法 第一種 第二種 這是兩個最簡單的例子 參考鏈接 https://cn.vuejs.org/v2/guide/render-function.html ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類