圖由邊的集合及頂點的集合組成岗仑。
如果一個圖的頂點對是有序的薪缆，則可以稱之為有向圖漾唉，反之無序圖
function Graph(v) {
this.vertices = v; //頂點
this.edges = 0; // 邊的數(shù)量
//使用一個長度與圖的頂點數(shù)相同的數(shù)組來記錄頂點的數(shù)量
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
this.adj[i].push("");
}
//增加邊的方法
this.addEdge = addEdge;
// 打印所有頂點及其相鄰頂點列表的方式來顯示圖
this.showGraph = showGraph;
//搜索某一個頂點的所有路徑
this.dfs = dfs;
// 用一個數(shù)組存放所有頂點挽绩，boolean值來表示是否訪問過
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
// 廣度優(yōu)先搜索需要數(shù)組來保存從一個頂點到下一個頂點的所有邊
this.edgeTo = [];
}
//當調(diào)用這個函數(shù)并傳入頂點 A 和 B 時膛壹，函數(shù)會先查找頂點 A 的鄰接表，將頂點 B 添加到列表中唉堪，然后再查找頂點 B 的鄰接表模聋，將頂點 A 加入列表。最后唠亚，這個函數(shù)會將邊數(shù)加 1链方。
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
// 遍歷所有頂點
function showGraph() {
for (var i = 0; i < this.vertices; ++i) {
putstr(i + " -> ");
for (var j = 0; j< this.vertices; ++j) {
if (this.adj[i][j] != undefined)
putstr(this.add[i][j] + ' ');
}
print();
}
}
深度優(yōu)先搜索算法比較簡單：訪問一個沒有訪問過的頂點，將它標記為已訪問灶搜，再遞歸地去訪問在初始頂點的鄰接表中其他沒有訪問過的頂點祟蚀。
function dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
print("Visited vertex: " + v);
}
for each(var w in this.adj[v]) {
if (!this.marked[w]) {
this.dfs(w);
}
}
}
// 測試 dfs() 函數(shù)的程序
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);
以上程序的輸出結(jié)果為：
0 -> 1 2
1 -> 0 3
2 -> 0 4
3 -> 1
4 -> 2
Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 2
Visited vertex: 4
廣度優(yōu)先搜索從第一個頂點開始，嘗試訪問盡可能靠近它的頂點割卖。本質(zhì)上前酿，這種搜索在圖上是逐層移動的，首先檢查最靠近第一個頂點的層鹏溯，再逐漸向下移動到離起始頂點最遠的層
function bfs(s) {
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到隊尾
while (queue.length > 0) {
var v = queue.shift(); // 從隊首移除
if (v == undefined) {
print("Visisted vertex: " + v);
}
for each(var w in this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
以上程序的輸出結(jié)果為：
0 -> 1 2
1 -> 0 3
2 -> 0 4
3 -> 1
4 -> 2
Visited vertex: 0
Visited vertex: 1
Visited vertex: 2
Visited vertex: 3
Visited vertex: 4
