資訊專欄INFORMATION COLUMN
摘要：存在好幾種方式來(lái)表示這種數(shù)據(jù)結(jié)構(gòu)。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。在關(guān)聯(lián)矩陣中矩陣的行表示頂點(diǎn)列表示邊。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的只有一點(diǎn)不同那就是待訪問頂點(diǎn)列表的數(shù)據(jù)結(jié)構(gòu)。
1 樹
一個(gè)樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)(除了頂部的第一個(gè)節(jié)點(diǎn))以及零個(gè)或多個(gè)子節(jié)點(diǎn)。位于樹頂部的節(jié)點(diǎn)叫作根節(jié)點(diǎn)(11)。它沒有父節(jié)點(diǎn)。樹中的每個(gè)元素都叫作節(jié)點(diǎn),節(jié)點(diǎn)分 為內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)。至少有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)。沒有子元素的節(jié)點(diǎn)稱為外部節(jié)點(diǎn)或葉節(jié)點(diǎn)。節(jié)點(diǎn)的一個(gè)屬性是深度,節(jié)點(diǎn)的深度取決于它的祖先節(jié)點(diǎn)的數(shù)量。樹的高度取決于所有節(jié)點(diǎn)深度的最大值。一棵樹也可以被分解成層級(jí)。根節(jié)點(diǎn)在第0層,它 的子節(jié)點(diǎn)在第1層,以此類推。
1.1 二叉樹和二叉搜索樹二叉樹中的節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn):一個(gè)是左側(cè)子節(jié)點(diǎn),另一個(gè)是右側(cè)子節(jié)點(diǎn)。這些定義有助于我們寫出更高效的向樹中插入、查找和刪除節(jié)點(diǎn)的算法。
對(duì)于二叉搜索樹，我們一般需要實(shí)現(xiàn)如下方法：
insert(key): 向書中插入一個(gè)新的鍵。
search(key): 在樹中查找一個(gè)鍵，如果節(jié)點(diǎn)存在，則返回true，否則返回false。
inOrderTraverse: 通過中序遍歷方式遍歷所有節(jié)點(diǎn)。
preOrderTraverse: 通過先序遍歷方式遍歷所有節(jié)點(diǎn)。
postOrderTraverse: 通過后序遍歷方式遍歷所有節(jié)點(diǎn)。
min: 返回樹中最小的鍵/值。
max: 返回樹中最大的健/值。
remove(key): 從樹中移除某個(gè)鍵。
1.1.1 二叉搜索樹的遍歷二叉搜索樹(BST)是二叉樹的一種,但是它只允許你在左側(cè)節(jié)點(diǎn)存儲(chǔ)(比父節(jié)點(diǎn))小的值, 在右側(cè)節(jié)點(diǎn)存儲(chǔ)(比父節(jié)點(diǎn))大(或者等于)的值。
中序遍歷是一種以上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式,也就是以從最小到最大的順序訪問所有節(jié)點(diǎn)。中序遍歷的一種應(yīng)用就是對(duì)樹進(jìn)行排序操作。
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)的。先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔。先序遍歷和中序遍歷的不同點(diǎn)是,先序遍歷會(huì)先訪問節(jié)點(diǎn)本身,然后再訪問它的左側(cè)子節(jié)點(diǎn)，最后是右側(cè)子節(jié)點(diǎn)。
后序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn),再訪問節(jié)點(diǎn)本身。后序遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄和它的子目錄中所有文件所占空間的大小。
樹中有三種經(jīng)常執(zhí)行的搜索類型，最小值，最大值，搜索特定的值。
1.1.2 二叉搜索樹的實(shí)現(xiàn)與基本使用下面的minNode方法允許我們從樹中任意一個(gè)節(jié)點(diǎn)開始尋找最小的鍵。我們可以使用它來(lái)找到一棵 樹或它的子樹中最小的鍵。因此,我們?cè)谡{(diào)用minNode方法的時(shí)候傳入樹的根節(jié)點(diǎn)(行{1}), 因?yàn)槲覀兿胍业秸脴涞淖钚℃I。
可以把代碼中的幾個(gè)內(nèi)部方法也寫成二叉樹結(jié)構(gòu)的屬性，這樣可以靈活引用。這里我們就不具體修改了。
function BinarySearchTree() {
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
this.root = null;
if ((typeof this.insert !== "function") && (typeof this.insert !== "string")) {
//內(nèi)部私有方法，用于插入節(jié)點(diǎn)
function insertNode(node, newNode) {
if (node.key > newNode.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
}
BinarySearchTree.prototype.insert = function(key) {
var newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
insertNode(this.root, newNode);
}
};
BinarySearchTree.prototype.inOrderTraverse = function(callback) {
//中序遍歷的私有方法,從小到大遍歷
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
inOrderTraverseNode(this.root, printNode);
};
BinarySearchTree.prototype.preOrderTraverse = function(callback){
function preOrderTraverseNode(node,callback){
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
preOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.postOrderTraverse = function(callback){
function postOrderTraverseNode(node,callback){
if (node !== null) {
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
postOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.min = function(){
function minNode(node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
//調(diào)用內(nèi)部方法
return minNode(this.root);
};
BinarySearchTree.prototype.max = function(){
function maxNode(node){
if (node) {
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
//調(diào)用內(nèi)部方法
return maxNode(this.root);
};
BinarySearchTree.prototype.search = function(key){
function searchNode(node,key){
if (node === null) {
return false;
}
if (node.key < key) {
return searchNode(node.right,key);
}else if(node.key > key){
return searchNode(node.left,key);
}else{
return true;
}
}
return searchNode(this.root,key);
};
BinarySearchTree.prototype.remove = function(key){
function findMinNode(node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node;
}
return null;
}
function removeNode(node,key){
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left,key);
return node;
}else if(key > node.key){
node.right = removeNode(node.right,key);
return node;
}else{//鍵等于node.key
//第一種情況，一個(gè)葉節(jié)點(diǎn)
if (node.left === null && node.right === null) {
node = null;
return node;
}
//第二種情況 一個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
if (node.left === null) {
node = node.right;
return node;
}else if (node.right === null){
node = node.left;
return node;
}
//第三種情況 一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right,aux.key);
return node;
}
}
this.root = removeNode(this.root,key);
};
}
}
二叉樹基本使用：
//遍歷節(jié)點(diǎn)操作
function printNode(value) {
console.log(value);
}
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
//中序遍歷
tree.inOrderTraverse(printNode);//3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//先序遍歷
tree.preOrderTraverse(printNode);//11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
//后序遍歷
tree.postOrderTraverse(printNode);//3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
console.log(tree.min());
console.log(tree.max());
//搜索
console.log(tree.search(1) ? "Key 1 found." : "Key 1 not found.");//Key 1 not found.
console.log(tree.search(8) ? "Key 8 found." : "Key 8 not found.");//Key 8 found.
//移除節(jié)點(diǎn)
tree.remove(15);
tree.inOrderTraverse(printNode);////3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//console.log(tree.remove(100));
2 圖
2.1 圖的相關(guān)概念
由一條邊連接在一起的頂點(diǎn)稱為相鄰頂點(diǎn)。一個(gè)頂點(diǎn)的度是其相鄰頂點(diǎn)的數(shù)量。如果圖中不存在環(huán),則稱該圖是無(wú)環(huán)的。
如果圖中每?jī)蓚€(gè)頂點(diǎn)間都存在路徑,則該圖是連通的。
圖可以是無(wú)向的(邊沒有方向)或是有向的(有向圖)。
圖還可以是未加權(quán)的或是加權(quán)的。
圖最常見的實(shí)現(xiàn)是鄰接矩陣。每個(gè)節(jié)點(diǎn)都和一個(gè)整數(shù)相關(guān)聯(lián),該整數(shù)將作為數(shù)組的索引。我 們用一個(gè)二維數(shù)組來(lái)表示頂點(diǎn)之間的連接。如果索引為i的節(jié)點(diǎn)和索引為j的節(jié)點(diǎn)相鄰,則arrayi === 1,否則arrayi === 0,鄰接矩陣如下圖所示:
我們也可以使用一種叫作鄰接表的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)表示圖。鄰接表由圖中每個(gè)頂點(diǎn)的相鄰頂點(diǎn)列表所組成。存在好幾種方式來(lái)表示這種數(shù)據(jù)結(jié)構(gòu)。我們可以用列表(數(shù)組)、鏈表,甚至是 散列表或是字典來(lái)表示相鄰頂點(diǎn)列表。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。
我們還可以用關(guān)聯(lián)矩陣來(lái)表示圖。在關(guān)聯(lián)矩陣中,矩陣的行表示頂點(diǎn),列表示邊。如下圖所示,我們使用二維數(shù)組來(lái)表示兩者之間的連通性,如果頂點(diǎn)v是邊e的入射點(diǎn),則arrayv === 1; 否則,arrayv===0。關(guān)聯(lián)矩陣通常用于邊的數(shù)量比頂點(diǎn)多的情況下,以節(jié)省空間和內(nèi)存。
盡管鄰接表可能對(duì)大多數(shù)問題來(lái)說(shuō)都是更好的選擇,但以上兩種表示法都很有用,且它們有 著不同的性質(zhì)(例如,要找出頂點(diǎn)v和w是否相鄰,使用鄰接矩陣會(huì)比較快)。在后面示例中, 我們將會(huì)使用鄰接表表示法。
2.2 圖的遍歷和樹數(shù)據(jù)結(jié)構(gòu)類似,我們可以訪問圖的所有節(jié)點(diǎn)。有兩種算法可以對(duì)圖進(jìn)行遍歷:廣度優(yōu)先 搜索(Breadth-First Search,BFS)和深度優(yōu)先搜索(Depth-First Search,DFS)。圖遍歷可以用來(lái)尋找特定的頂點(diǎn)或?qū)ふ覂蓚€(gè)頂點(diǎn)之間的路徑,檢查圖是否連通,檢查圖是否含有環(huán)等。
圖遍歷算法的思想是必須追蹤每個(gè)第一次訪問的節(jié)點(diǎn),并且追蹤有哪些節(jié)點(diǎn)還沒有被完全探索。對(duì)于兩種圖遍歷算法,都需要明確指出第一個(gè)被訪問的頂點(diǎn)。
完全探索一個(gè)頂點(diǎn)要求我們查看該頂點(diǎn)的每一條邊。對(duì)于每一條邊所連接的沒有被訪問過的頂點(diǎn),將其標(biāo)注為被發(fā)現(xiàn)的,并將其加進(jìn)待訪問頂點(diǎn)列表中。
為了保證算法的效率,務(wù)必訪問每個(gè)頂點(diǎn)至多兩次。連通圖中每條邊和頂點(diǎn)都會(huì)被訪問到。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的,只有一點(diǎn)不同,那就是待訪問頂點(diǎn) 列表的數(shù)據(jù)結(jié)構(gòu)。
2.3 廣度優(yōu)先搜索廣度優(yōu)先搜索算法會(huì)從指定的第一個(gè)頂點(diǎn)開始遍歷圖,先訪問其所有的相鄰點(diǎn),就像一次訪問圖的一層。換句話說(shuō),就是先寬后深地訪問頂點(diǎn)。
廣度優(yōu)先搜索和深度優(yōu)先搜索都需要標(biāo)注被訪問過的頂點(diǎn)。為此,我們將使用一個(gè)輔助數(shù)組color。由于當(dāng)算法開始執(zhí)行時(shí),所有的頂點(diǎn)顏色都是白色(行{1}),所以我們可以創(chuàng)建一個(gè)輔 助函數(shù)initializeColor,為這兩個(gè)算法執(zhí)行此初始化操作。
我們會(huì)用到一個(gè)隊(duì)列結(jié)構(gòu)。隊(duì)列的實(shí)現(xiàn).html)。
2.3.1廣度優(yōu)先搜索的基本實(shí)現(xiàn)//廣度優(yōu)先搜索算法 v表示初始節(jié)點(diǎn)，callback表示回調(diào)。
Graph.prototype.bfs = function(v, callback){
var color = initializeColor(this.vertices);
var queue = new Queue();//存儲(chǔ)待訪問和待探索的節(jié)點(diǎn)
queue.enqueue(v);
while(!queue.isEmpty()){
var u = queue.dequeue();
//獲取u的相鄰節(jié)點(diǎn)列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
//如果從沒有標(biāo)記過，則標(biāo)記為grey，加入隊(duì)列
if (color[w] === "white") {
color[w] = "grey";
queue.enqueue(w);
}
}
//所有相鄰節(jié)點(diǎn)都被標(biāo)記了，所以改為黑色
color[u] = "black";
//如果對(duì)于標(biāo)記過得節(jié)點(diǎn)有操作，通過callback操作
if (callback) {
callback(u);
}
}
};
2.3.2 廣度優(yōu)先實(shí)現(xiàn)最短路徑查找
給定一個(gè)圖G和源頂點(diǎn)v,找出對(duì)每個(gè)頂點(diǎn)u,u和v之間最短路徑的距離。
//用BFS實(shí)現(xiàn)最短路徑
Graph.prototype.BFS = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲(chǔ)待訪問和待探索的節(jié)點(diǎn)
var d = [];
var pred = [];
queue.enqueue(v);
for (var i = 0; i < this.vertices.length; i++) {
d[this.vertices[i]] = 0;
pred[this.vertices[i]] = null;
}
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節(jié)點(diǎn)列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標(biāo)記過，則標(biāo)記為grey，加入隊(duì)列
if (color[w] === "white") {
color[w] = "grey";
d[w] = d[u] + 1;
pred[w] = u;
queue.enqueue(w);
}
}
//所有相鄰節(jié)點(diǎn)都被標(biāo)記了，所以改為黑色
color[u] = "black";
//如果對(duì)于標(biāo)記過得節(jié)點(diǎn)有操作，通過callback操作
if (callback) {
callback(u);
}
}
return {
distances: d,
predecessors: pred
}
};
2.3.3 深度優(yōu)先搜索基本實(shí)現(xiàn)
//深度優(yōu)先基本實(shí)現(xiàn)
Graph.prototype.dfs = function(callback) {
var self = this;
function dfsVisit(u, color, callback) {
color[u] = "grey";
if (callback) {
callback(u);
}
var neighbors = self.adjList.get(u);
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === "white") {
dfsVisit(w, color, callback);
}
}
color[u] = "black";
}
var color = initializeColor(this.vertices);
for (var i = 0; i < this.vertices.length; i++) {
if (color[this.vertices[i]] === "white") {
dfsVisit(this.vertices[i], color, callback);
}
}
};
2.3.4 深度優(yōu)先搜索實(shí)現(xiàn)拓?fù)渑判?/b>
當(dāng)我們需要編排一些任務(wù)或步驟的執(zhí)行順序時(shí),這稱為拓?fù)渑判颉?/p>
//DFS可以實(shí)現(xiàn)輸出被訪問頂點(diǎn)的順序，可以用于拓?fù)渑判驅(qū)崿F(xiàn)。
Graph.prototype.DFS = function(){
var time = 0;
var self = this;
function DFSVisit(u,color,d,f,p){
//console.log("discovered " + u);
color[u] = "grey";
d[u] = ++time;
var neighbors = self.adjList.get(u);
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
if (color[w] === "white") {
p[w] = u;
DFSVisit(w,color,d,f,p);
}
}
color[u] = "black";
f[u] = ++time;
//console.log("explored " + u);
}
var color = initializeColor(this.vertices);
var d = [];
var f = [];
var p = [];
var time = 0;
for(var i = 0; i < this.vertices.length; i++){
f[this.vertices[i]] = 0;
d[this.vertices[i]] = 0;
p[this.vertices[i]] = null;
}
for(var i = 0; i< this.vertices.length; i++){
if (color[this.vertices[i]] === "white") {
DFSVisit(this.vertices[i], color, d, f, p);
}
}
return {
discovery:d,
finished:f,
predecessors:p
}
};
2.4 圖的實(shí)現(xiàn)
我們會(huì)實(shí)現(xiàn)一個(gè)鄰接表的圖結(jié)構(gòu)。我們使用一個(gè)數(shù)組來(lái)存儲(chǔ)圖中所有頂點(diǎn)的名字,以及一個(gè)字典 字典實(shí)現(xiàn).html)來(lái)存儲(chǔ)鄰接表字典將會(huì)使用頂點(diǎn)的名字作為鍵,鄰接頂點(diǎn)列表作為值。vertices數(shù)組和adjList字典兩者都是我們Graph類的私有屬性。
function Graph() {
this.vertices = []; //點(diǎn)數(shù)組
this.adjList = new Dictionary();
if ((typeof this.addVertex !== "function") && (typeof this.addVertex !== "string")) {
//私有方法，標(biāo)記節(jié)點(diǎn)顏色 未被訪問過是white 被發(fā)現(xiàn)是grey 已被探索black。
function initializeColor(vertices) {
var color = [];
for (var i = 0; i < vertices.length; i++) {
color[vertices[i]] = "white";
}
return color;
}
//添加節(jié)點(diǎn)
Graph.prototype.addVertex = function(v) {
this.vertices.push(v);
this.adjList.set(v, []); //給節(jié)點(diǎn)v設(shè)置一個(gè)空數(shù)組作為值。
};
//添加邊
Graph.prototype.addEdge = function(v, w) {
this.adjList.get(v).push(w); //先獲取v節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組，然后把w推入數(shù)組中，這樣就表示一條v到w的線
this.adjList.get(w).push(v);
};
//廣度優(yōu)先d
//搜索算法 v表示初始節(jié)點(diǎn)，callback表示回調(diào)。
Graph.prototype.bfs = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲(chǔ)待訪問和待探索的節(jié)點(diǎn)
queue.enqueue(v);
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節(jié)點(diǎn)列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標(biāo)記過，則標(biāo)記為grey，加入隊(duì)列
if (color[w] === "white") {
color[w] = "grey";
queue.enqueue(w);
}
}
//所有相鄰節(jié)點(diǎn)都被標(biāo)記了，所以改為黑色
color[u] = "black";
//如果對(duì)于標(biāo)記過得節(jié)點(diǎn)有操作，通過callback操作
if (callback) {
callback(u);
}
}
};
//用BFS實(shí)現(xiàn)最短路徑
Graph.prototype.BFS = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲(chǔ)待訪問和待探索的節(jié)點(diǎn)
var d = [];
var pred = [];
queue.enqueue(v);
for (var i = 0; i < this.vertices.length; i++) {
d[this.vertices[i]] = 0;
pred[this.vertices[i]] = null;
}
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節(jié)點(diǎn)列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標(biāo)記過，則標(biāo)記為grey，加入隊(duì)列
if (color[w] === "white") {
color[w] = "grey";
d[w] = d[u] + 1;
pred[w] = u;
queue.enqueue(w);
}
}
//所有相鄰節(jié)點(diǎn)都被標(biāo)記了，所以改為黑色
color[u] = "black";
//如果對(duì)于標(biāo)記過得節(jié)點(diǎn)有操作，通過callback操作
if (callback) {
callback(u);
}
}
return {
distances: d,
predecessors: pred
}
};
//深度優(yōu)先基本實(shí)現(xiàn)
Graph.prototype.dfs = function(callback) {
var self = this;
function dfsVisit(u, color, callback) {
color[u] = "grey";
if (callback) {
callback(u);
}
var neighbors = self.adjList.get(u);
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === "white") {
dfsVisit(w, color, callback);
}
}
color[u] = "black";
}
var color = initializeColor(this.vertices);
for (var i = 0; i < this.vertices.length; i++) {
if (color[this.vertices[i]] === "white") {
dfsVisit(this.vertices[i], color, callback);
}
}
};
//DFS可以實(shí)現(xiàn)輸出被訪問頂點(diǎn)的順序
Graph.prototype.DFS = function(){
var time = 0;
var self = this;
function DFSVisit(u,color,d,f,p){
//console.log("discovered " + u);
color[u] = "grey";
d[u] = ++time;
var neighbors = self.adjList.get(u);
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
if (color[w] === "white") {
p[w] = u;
DFSVisit(w,color,d,f,p);
}
}
color[u] = "black";
f[u] = ++time;
//console.log("explored " + u);
}
var color = initializeColor(this.vertices);
var d = [];
var f = [];
var p = [];
var time = 0;
for(var i = 0; i < this.vertices.length; i++){
f[this.vertices[i]] = 0;
d[this.vertices[i]] = 0;
p[this.vertices[i]] = null;
}
for(var i = 0; i< this.vertices.length; i++){
if (color[this.vertices[i]] === "white") {
DFSVisit(this.vertices[i], color, d, f, p);
}
}
return {
discovery:d,
finished:f,
predecessors:p
}
};
Graph.prototype.toString = function() {
var s = "";
for (var i = 0; i < this.vertices.length; i++) {
s += this.vertices[i] + " -> ";
var neighbors = this.adjList.get(this.vertices[i]);
for (var j = 0; j < neighbors.length; j++) {
s += neighbors[j] + " ";
}
s += ",";
}
return s;
};
}
}
2.5 圖的基本使用
var graph = new Graph();
var myVertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
//添加點(diǎn)
for (var i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
//添加點(diǎn)之間的關(guān)系
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
function printNode(value) {
console.log("Visited vertex: " + value);
}
//廣度搜索算法
//graph.bfs(myVertices[0],printNode);
//上行輸出結(jié)果，節(jié)點(diǎn)的訪問順序
// 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
//廣度優(yōu)先搜索的使用:最短路徑算法
var shortestPathA = graph.BFS(myVertices[0]);
//console.log(shortestPathA);
//上行輸出結(jié)果：
// { 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" ]
//深入優(yōu)先搜索算法
//graph.dfs(printNode);
//上一行運(yùn)行結(jié)果，節(jié)點(diǎn)的訪問順序
// 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
//深度優(yōu)先搜索查找訪問過程：
graph = new Graph();
myVertices = ["A","B","C","D","E","F"];
for (i=0; i
源碼地址
Javascript的數(shù)據(jù)結(jié)構(gòu)與算法(三)源碼
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/86658.html
摘要：技巧使你的更加專業(yè)這是上關(guān)于技巧的一篇譯文，另外你也可以在本項(xiàng)目看到原文。列舉了一些很實(shí)用的技巧，比如給空內(nèi)容的標(biāo)簽添加內(nèi)容，逗號(hào)分隔列表等等。排序算法看源碼，把它背下來(lái)吧排序算法的封裝。主要幫助初學(xué)者更好的掌握排序算法的實(shí)現(xiàn)。 成為專業(yè)程序員路上用到的各種優(yōu)秀資料、神器及框架 成為一名專業(yè)程序員的道路上，需要堅(jiān)持練習(xí)、學(xué)習(xí)與積累，技術(shù)方面既要有一定的廣度，更要有自己的深度。 Java...
摘要：技巧使你的更加專業(yè)這是上關(guān)于技巧的一篇譯文，另外你也可以在本項(xiàng)目看到原文。列舉了一些很實(shí)用的技巧，比如給空內(nèi)容的標(biāo)簽添加內(nèi)容，逗號(hào)分隔列表等等。排序算法看源碼，把它背下來(lái)吧排序算法的封裝。主要幫助初學(xué)者更好的掌握排序算法的實(shí)現(xiàn)。 成為專業(yè)程序員路上用到的各種優(yōu)秀資料、神器及框架 成為一名專業(yè)程序員的道路上，需要堅(jiān)持練習(xí)、學(xué)習(xí)與積累，技術(shù)方面既要有一定的廣度，更要有自己的深度。 Java...
摘要：至于這三個(gè)的具體概念，可以看圖中集合的實(shí)現(xiàn)首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法三集合 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與...
摘要：保護(hù)數(shù)據(jù)結(jié)構(gòu)內(nèi)部元素下劃線命名約定這只是一種約定，只能依賴于開發(fā)人員具備的常識(shí)用的限定作用于實(shí)現(xiàn)類實(shí)現(xiàn)了假的私有屬性，雖然基本類型不可變，但由于新增的方法仍然能取到所有屬性，而且是數(shù)組的形式，但我們操作的是棧，不應(yīng)該出現(xiàn)這種行為。 棧是一種遵循后進(jìn)先出（ILFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一段，稱為棧頂，另一端就叫棧底?，F(xiàn)實(shí)中很多例子采用了這種數(shù)據(jù)結(jié)構(gòu)，比如一摞...
摘要：筆者作為一位，將工作以來(lái)用到的各種優(yōu)秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識(shí)點(diǎn)大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計(jì)算數(shù)組的極值技巧使你的更加專業(yè)前端掘金一個(gè)幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經(jīng)常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會(huì)用到。會(huì)持續(xù)更新… 一、...
摘要：筆者作為一位，將工作以來(lái)用到的各種優(yōu)秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識(shí)點(diǎn)大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計(jì)算數(shù)組的極值技巧使你的更加專業(yè)前端掘金一個(gè)幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經(jīng)常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會(huì)用到。會(huì)持續(xù)更新… 一、...
閱讀 2050·2021-11-08 13:22
閱讀 2510·2021-09-04 16:40
閱讀 1155·2021-09-03 10:29
閱讀 1723·2019-08-30 15:44
閱讀 2127·2019-08-30 11:13
閱讀 2795·2019-08-29 17:07
閱讀 1972·2019-08-29 14:22
閱讀 1252·2019-08-26 14:00
