Data Algorithm

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

相關資源

Node.js 圖的處理 (1)

基本介紹

教學目標

透過 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
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.dfs = dfs;
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 dfs(v) {
if (v == 0) {
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
}
this.marked[v] = true;
if (this.adj[v] != undefined) {
console.log(v)
}
for (var w = 0; w <this.adj[v].length; w++) {
if (!this.marked[this.adj[v][w]]) {
this.dfs(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.dfs(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
3
2
4

相關資源

Node.js 排序處理 (3)

基本介紹

教學目標

透過 Node.js 實作資料結構與演算法中的插入排序法。

前置作業

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

使用教學

撰寫程式

algorithm.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
var data = [];
var number = 500
for (var n = 0; n < number; n++) {
data[n] = Math.floor(Math.random() * (number + 1))
}

var shell_sort_start = new Date().getTime();
var shell_sort_result = shellSort(data.slice());
var shell_sort_stop = new Date().getTime();
var shell_sort_elapsed = shell_sort_stop - shell_sort_start;

console.log("希爾排序法");
console.log("原始資料: " + data );
console.log("排序結果: " + shell_sort_result );
console.log("花費時間: " + shell_sort_elapsed + " 毫秒" );

function shellSort(data) {
var gap = data.length / 2;
while (gap >= 1) {
for (var i = gap; i < data.length; i++) {
for (var j = i; j >= gap && data[j] < data[j-gap]; j -= gap) {
var temp = data[j];
data[j] = data[j-gap];
data[j-gap] = temp;
}
}
gap = parseInt(gap / 2);
}
return data;
}

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
希爾排序法
原始資料: 333,61,75,320,193,500,161,197,459,318,43,145,367,57,380,332,5,69,53,143,340,332,4,96,313,12,204,148,490,354,177,292,335,449,87,412,380,291,474,167,431,76,388,349,17,481,52,216,272,486,290,178,262,383,495,38,76,389,232,486,249,156,346,172,500,63,180,85,122,370,138,59,115,243,76,100,366,470,123,182,153,322,58,66,149,238,363,118,361,48,44,49,128,192,400,156,460,406,333,232,495,5,197,436,472,321,104,317,268,207,378,97,137,322,298,207,242,258,229,179,143,61,263,137,127,275,90,426,374,18,43,33,444,121,264,119,313,322,334,194,435,328,369,230,54,345,40,297,260,314,461,30,26,417,235,398,18,378,10,282,225,143,450,239,170,135,47,483,163,117,336,392,194,370,288,259,357,36,253,266,95,22,403,399,218,404,375,136,141,289,132,234,291,24,248,424,344,332,72,78,353,333,386,476,23,460,41,274,67,445,206,318,126,24,133,394,96,364,38,25,247,454,387,335,7,232,370,395,75,168,328,49,77,295,75,473,225,399,346,313,235,398,474,486,350,133,413,45,140,361,281,17,115,466,53,157,349,314,197,406,5,52,304,17,195,403,153,115,38,24,172,473,286,344,9,63,309,244,90,431,228,470,31,210,211,231,225,408,346,209,325,483,367,247,486,229,382,256,209,483,335,362,223,199,373,444,437,71,118,222,424,414,457,15,413,325,439,166,163,179,376,135,388,221,54,64,416,247,91,136,393,131,417,105,145,288,149,353,170,99,209,395,386,268,202,284,372,64,293,499,483,194,158,173,484,5,242,196,372,487,51,475,205,274,416,348,155,399,133,249,318,288,240,85,28,131,481,484,490,271,405,253,40,348,229,412,77,406,236,403,212,268,322,220,85,380,416,335,59,227,420,137,190,420,142,285,138,368,140,269,339,22,495,297,69,285,358,374,467,110,147,393,458,61,332,181,256,56,277,48,291,329,384,382,352,361,119,466,112,167,123,237,251,296,228,412,260,154,208,133,50,381,395,352,443,356,450,341,339,466,332,48,262,434,174,308,454,211,136,255,353,343,347,74,17,0,8,194,181,25,384,144,344,308,339,336,229,72,334,133,475,132,237,151,268,126,497,141,8,89
排序結果: 0,4,5,5,5,5,7,8,8,9,10,12,15,17,17,17,17,18,18,22,22,23,24,24,24,25,25,26,28,30,31,33,36,38,38,38,40,40,41,43,43,44,45,47,48,48,48,49,49,50,51,52,52,53,53,54,54,56,57,58,59,59,61,61,61,63,63,64,64,66,67,69,69,71,72,72,74,75,75,75,76,76,76,77,77,78,85,85,85,87,89,90,90,91,95,96,96,97,99,100,104,105,110,112,115,115,115,117,118,118,119,119,121,122,123,123,126,126,127,128,131,131,132,132,133,133,133,133,133,135,135,136,136,136,137,137,137,138,138,140,140,141,141,142,143,143,143,144,145,145,147,148,149,149,151,153,153,154,155,156,156,157,158,161,163,163,166,167,167,168,170,170,172,172,173,174,177,178,179,179,180,181,181,182,190,192,193,194,194,194,194,195,196,197,197,197,199,202,204,205,206,207,207,208,209,209,209,210,211,211,212,216,218,220,221,222,223,225,225,225,227,228,228,229,229,229,229,230,231,232,232,232,234,235,235,236,237,237,238,239,240,242,242,243,244,247,247,247,248,249,249,251,253,253,255,256,256,258,259,260,260,262,262,263,264,266,268,268,268,268,269,271,272,274,274,275,277,281,282,284,285,285,286,288,288,288,289,290,291,291,291,292,293,295,296,297,297,298,304,308,308,309,313,313,313,314,314,317,318,318,318,320,321,322,322,322,322,325,325,328,328,329,332,332,332,332,332,333,333,333,334,334,335,335,335,335,336,336,339,339,339,340,341,343,344,344,344,345,346,346,346,347,348,348,349,349,350,352,352,353,353,353,354,356,357,358,361,361,361,362,363,364,366,367,367,368,369,370,370,370,372,372,373,374,374,375,376,378,378,380,380,380,381,382,382,383,384,384,386,386,387,388,388,389,392,393,393,394,395,395,395,398,398,399,399,399,400,403,403,403,404,405,406,406,406,408,412,412,412,413,413,414,416,416,416,417,417,420,420,424,424,426,431,431,434,435,436,437,439,443,444,444,445,449,450,450,454,454,457,458,459,460,460,461,466,466,466,467,470,470,472,473,473,474,474,475,475,476,481,481,483,483,483,483,484,484,486,486,486,486,487,490,490,495,495,495,497,499,500,500
花費時間: 1 毫秒

相關資源

Node.js 排序處理 (2)

基本介紹

教學目標

透過 Node.js 實作資料結構與演算法中的插入排序法。

前置作業

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

使用教學

撰寫程式

algorithm.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
var data = [];
var number = 500
for (var n = 0; n < number; n++) {
data[n] = Math.floor(Math.random() * (number + 1))
}

var insertion_sort_start = new Date().getTime();
var insertion_sort_result = insertionSort(data.slice());
var insertion_sort_stop = new Date().getTime();
var insertion_sort_elapsed = insertion_sort_stop - insertion_sort_start;

console.log("插入排序法");
console.log("原始資料: " + data );
console.log("排序結果: " + insertion_sort_result );
console.log("花費時間: " + insertion_sort_elapsed + " 毫秒" );

function insertionSort(data) {
var temp, inner;
for (var outer = 1; outer <= data.length - 1 ; ++outer) {
temp = data[outer];
inner = outer;
while (inner > 0 && data[inner - 1] >= temp) {
data[inner] = data[inner - 1];
--inner;
}
data[inner] = temp;
}
return data;
}

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
插入排序法
原始資料: 343,479,136,358,299,408,11,453,404,430,41,203,272,259,336,61,109,83,322,433,168,72,481,246,284,52,64,233,85,310,427,357,454,172,472,220,498,329,211,283,308,470,308,209,319,179,96,198,454,426,399,396,418,24,408,79,180,168,79,215,256,388,428,132,75,109,463,258,276,178,317,355,238,314,40,385,425,160,159,322,261,184,419,391,214,359,184,374,48,14,20,402,371,113,347,194,10,91,428,372,215,459,174,61,151,446,454,226,411,390,213,399,159,272,7,132,308,428,428,196,313,189,215,301,110,82,252,478,277,440,218,406,1,308,214,8,37,352,102,410,79,422,213,75,455,381,354,223,249,6,166,269,168,137,322,33,54,338,122,306,410,420,337,172,164,438,464,354,266,451,378,222,208,147,469,309,88,443,229,357,86,330,110,90,288,436,425,168,122,220,227,185,389,243,383,500,44,45,9,13,276,398,14,383,248,201,440,173,350,495,159,492,364,466,229,416,0,52,428,390,444,128,374,297,185,119,136,228,84,117,10,205,111,77,496,125,66,391,29,388,4,111,410,110,449,423,60,467,41,113,299,451,343,322,376,99,46,204,55,452,38,36,57,31,90,6,58,426,405,220,286,181,26,27,362,209,6,256,383,141,449,379,264,100,42,317,401,7,124,152,182,16,324,108,81,31,333,17,322,106,468,163,479,414,19,226,253,468,382,438,58,455,415,92,264,270,391,249,496,177,182,143,33,226,54,142,220,44,242,453,12,219,246,56,72,329,377,431,163,122,213,117,166,58,288,43,224,261,431,20,214,48,100,386,108,31,287,215,35,158,72,294,158,428,164,52,369,96,314,391,354,111,474,348,31,363,204,101,304,493,201,223,95,67,37,478,110,348,316,57,264,444,195,21,248,471,108,6,337,322,379,189,146,185,357,377,491,147,8,327,289,184,375,355,418,422,293,281,89,289,146,267,430,485,426,60,107,361,94,333,319,343,257,177,24,220,243,326,351,280,257,265,136,289,15,67,155,485,234,71,490,137,268,112,131,475,406,274,87,30,379,13,361,275,440,498,6,476,52,369,265,394,196,387,283,309,122,296,48,74,5,336,348,182,499,33,47,291,256,134,130,159,477,382,392,415,37,118,144,341
排序結果: 0,1,4,5,6,6,6,6,6,7,7,8,8,9,10,10,11,12,13,13,14,14,15,16,17,19,20,20,21,24,24,26,27,29,30,31,31,31,31,33,33,33,35,36,37,37,37,38,40,41,41,42,43,44,44,45,46,47,48,48,48,52,52,52,52,54,54,55,56,57,57,58,58,58,60,60,61,61,64,66,67,67,71,72,72,72,74,75,75,77,79,79,79,81,82,83,84,85,86,87,88,89,90,90,91,92,94,95,96,96,99,100,100,101,102,106,107,108,108,108,109,109,110,110,110,110,111,111,111,112,113,113,117,117,118,119,122,122,122,122,124,125,128,130,131,132,132,134,136,136,136,137,137,141,142,143,144,146,146,147,147,151,152,155,158,158,159,159,159,159,160,163,163,164,164,166,166,168,168,168,168,172,172,173,174,177,177,178,179,180,181,182,182,182,184,184,184,185,185,185,189,189,194,195,196,196,198,201,201,203,204,204,205,208,209,209,211,213,213,213,214,214,214,215,215,215,215,218,219,220,220,220,220,220,222,223,223,224,226,226,226,227,228,229,229,233,234,238,242,243,243,246,246,248,248,249,249,252,253,256,256,256,257,257,258,259,261,261,264,264,264,265,265,266,267,268,269,270,272,272,274,275,276,276,277,280,281,283,283,284,286,287,288,288,289,289,289,291,293,294,296,297,299,299,301,304,306,308,308,308,308,309,309,310,313,314,314,316,317,317,319,319,322,322,322,322,322,322,324,326,327,329,329,330,333,333,336,336,337,337,338,341,343,343,343,347,348,348,348,350,351,352,354,354,354,355,355,357,357,357,358,359,361,361,362,363,364,369,369,371,372,374,374,375,376,377,377,378,379,379,379,381,382,382,383,383,383,385,386,387,388,388,389,390,390,391,391,391,391,392,394,396,398,399,399,401,402,404,405,406,406,408,408,410,410,410,411,414,415,415,416,418,418,419,420,422,422,423,425,425,426,426,426,427,428,428,428,428,428,428,430,430,431,431,433,436,438,438,440,440,440,443,444,444,446,449,449,451,451,452,453,453,454,454,454,455,455,459,463,464,466,467,468,468,469,470,471,472,474,475,476,477,478,478,479,479,481,485,485,490,491,492,493,495,496,496,498,498,499,500
花費時間: 2 毫秒

相關資源

Node.js 排序處理 (1)

基本介紹

教學目標

透過 Node.js 實作資料結構與演算法中的氣泡排序法。

前置作業

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

使用教學

撰寫程式

algorithm.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
var data = [];
var number = 500
for (var n = 0; n < number; n++) {
data[n] = Math.floor(Math.random() * (number + 1))
}

var bubble_sort_start = new Date().getTime();
var bubble_sort_result = bubbleSort(data.slice());
var bubble_sort_stop = new Date().getTime();
var bubble_sort_elapsed = bubble_sort_stop - bubble_sort_start;

console.log("氣泡排序法");
console.log("原始資料: " + data );
console.log("排序結果: " + bubble_sort_result );
console.log("花費時間: " + bubble_sort_elapsed + " 毫秒" );

function bubbleSort(data) {
for (var outer = data.length; outer > 1 ; --outer) {
for (var inner = 0; inner < outer; ++inner) {
if (data[inner] > data[inner + 1]) {
var temp = data[inner];
data[inner] = data[inner + 1];
data[inner + 1] = temp;
}
}
}
return data;
}

執行程式

1
$ node algorithm.js

執行結果

1
2
3
4
氣泡排序法
原始資料: 282,53,179,417,249,73,371,282,13,247,461,237,302,110,57,53,193,185,28,226,173,396,224,215,258,116,388,37,48,464,259,357,2,405,415,190,290,27,353,324,120,449,21,88,242,147,247,257,478,124,332,16,155,85,14,127,424,355,369,454,69,145,380,86,22,140,474,390,467,269,430,486,324,224,413,210,9,130,62,176,230,347,495,278,184,92,339,49,123,435,53,58,310,97,353,498,405,105,364,46,308,265,275,365,121,107,391,397,43,335,369,93,116,308,62,57,140,56,463,278,420,483,383,282,421,282,205,278,295,243,160,30,77,44,206,356,442,334,313,140,93,470,230,372,135,305,77,192,221,235,396,426,36,454,193,403,394,364,207,154,97,108,485,476,272,173,275,214,336,194,412,193,91,285,137,422,181,497,301,156,476,420,235,375,403,169,114,303,27,6,456,442,62,484,239,319,119,237,158,27,481,204,76,181,213,158,478,130,48,75,192,467,367,379,246,82,309,178,23,371,151,12,477,288,68,129,215,63,443,192,34,123,233,260,88,150,334,222,181,490,46,10,392,160,370,62,383,222,441,270,103,299,218,251,170,259,458,500,427,232,24,404,436,376,304,74,312,26,24,29,190,90,108,299,324,216,188,488,214,87,52,33,264,85,160,329,170,217,461,36,267,467,195,306,170,198,186,100,425,417,341,171,326,404,415,372,414,172,465,485,349,251,43,190,432,302,286,388,273,460,318,116,381,472,75,416,419,206,8,450,307,316,75,343,372,52,474,419,487,2,493,25,490,148,459,73,73,418,169,225,459,421,326,392,134,350,126,336,126,240,348,107,65,238,291,30,296,124,127,94,200,426,111,57,159,76,82,387,62,107,471,429,207,90,161,376,130,115,416,117,257,119,450,212,7,274,39,423,157,403,176,221,409,16,147,188,483,411,323,349,176,128,357,466,410,310,440,25,253,498,256,356,76,175,380,282,416,91,107,403,428,402,350,76,193,206,479,40,132,58,345,36,318,31,302,279,302,387,216,282,404,66,131,201,411,422,479,192,204,347,238,90,410,465,431,178,437,243,31,335,356,92,397,288,310,93,398,484,57,465,183,265,115,444,293,335,390,380,309,241,105,169,206,429,387,347,23,486,461,251
排序結果: 2,2,6,7,8,9,10,12,13,14,16,16,21,22,23,23,24,24,25,25,26,27,27,27,28,29,30,30,31,31,33,34,36,36,36,37,39,40,43,43,44,46,46,48,48,49,52,52,53,53,53,56,57,57,57,57,58,58,62,62,62,62,62,63,65,66,68,69,73,73,73,74,75,75,75,76,76,76,76,77,77,82,82,85,85,86,87,88,88,90,90,90,91,91,92,92,93,93,93,94,97,97,100,103,105,105,107,107,107,107,108,108,110,111,114,115,115,116,116,116,117,119,119,120,121,123,123,124,124,126,126,127,127,128,129,130,130,130,131,132,134,135,137,140,140,140,145,147,147,148,150,151,154,155,156,157,158,158,159,160,160,160,161,169,169,169,170,170,170,171,172,173,173,175,176,176,176,178,178,179,181,181,181,183,184,185,186,188,188,190,190,190,192,192,192,192,193,193,193,193,194,195,198,200,201,204,204,205,206,206,206,206,207,207,210,212,213,214,214,215,215,216,216,217,218,221,221,222,222,224,224,225,226,230,230,232,233,235,235,237,237,238,238,239,240,241,242,243,243,246,247,247,249,251,251,251,253,256,257,257,258,259,259,260,264,265,265,267,269,270,272,273,274,275,275,278,278,278,279,282,282,282,282,282,282,285,286,288,288,290,291,293,295,296,299,299,301,302,302,302,302,303,304,305,306,307,308,308,309,309,310,310,310,312,313,316,318,318,319,323,324,324,324,326,326,329,332,334,334,335,335,335,336,336,339,341,343,345,347,347,347,348,349,349,350,350,353,353,355,356,356,356,357,357,364,364,365,367,369,369,370,371,371,372,372,372,375,376,376,379,380,380,380,381,383,383,387,387,387,388,388,390,390,391,392,392,394,396,396,397,397,398,402,403,403,403,403,404,404,404,405,405,409,410,410,411,411,412,413,414,415,415,416,416,416,417,417,418,419,419,420,420,421,421,422,422,423,424,425,426,426,427,428,429,429,430,431,432,435,436,437,440,441,442,442,443,444,449,450,450,454,454,456,458,459,459,460,461,461,461,463,464,465,465,465,466,467,467,467,470,471,472,474,474,476,476,477,478,478,479,479,481,483,483,484,484,485,485,486,486,487,488,490,490,493,495,497,498,498,500
花費時間: 3 毫秒

相關資源