Node.js 圖的處理 (2)

基本介紹

教學目標

透過 Node.js 實作廣度優先搜尋找出圖元件中所有節點。

前置作業

  1. 完成 Node.js 套件安裝與設置。

使用教學

撰寫程式

graph.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
var create = function (v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
}
this.addEdge = addEdge;
this.show = show;
this.bfs = bfs;
return this
}
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges ++;
}
function show() {
for (var i = 0; i < this.vertices; ++i) {
for (var j = 0; j < this.vertices; ++j) {
if (this.adj[i][j] != undefined && this.adj[i][j] != "") {
console.log( i + " -> " + this.adj[i][j]);
}
}
}
}
function bfs(v) {
if (v == 0) {
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
}
var queue = [];
this.marked[v] = true;
queue.push(v);
while (queue.length > 0) {
var v = queue.shift();
if (v != undefined) {
console.log(v);
}
for (var w=0; w<this.adj[v].length; w++) {
if (!this.marked[this.adj[v][w]]) {
this.marked[this.adj[v][w]] = true;
queue.push(this.adj[v][w]);
}
}
}
}
module.exports.create = create;

algorithm.js

1
2
3
4
5
6
7
8
9
10
11
var graph = require("./graph.js");
var g1 = graph.create(5);
g1.addEdge(0,1);
g1.addEdge(0,2);
g1.addEdge(1,3);
g1.addEdge(2,4);

console.log("圖元件");
g1.show();
console.log("廣度優先搜尋");
g1.bfs(0);

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
5
6
7
8
9
10
11
12
13
圖元件
0 -> 1
0 -> 2
1 -> 3
2 -> 4
3 -> 1
4 -> 2
廣度優先搜尋
0
1
2
3
4

相關資源