图由边的集合及顶点的集合组成。
如果一个图的顶点对是有序的，则可以称之为有向图，反之无序图
function Graph(v) {
this.vertices = v; //顶点
this.edges = 0; // 边的数量
//使用一个长度与图的顶点数相同的数组来记录顶点的数量
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;
// 用一个数组存放所有顶点，boolean值来表示是否访问过
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
// 广度优先搜索需要数组来保存从一个顶点到下一个顶点的所有边
this.edgeTo = [];
}
//当调用这个函数并传入顶点 A 和 B 时，函数会先查找顶点 A 的邻接表，将顶点 B 添加到列表中，然后再查找顶点 B 的邻接表，将顶点 A 加入列表。最后，这个函数会将边数加 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();
}
}
深度优先搜索算法比较简单：访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。
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() 函数的程序
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);
以上程序的输出结果为：
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
广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点。本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层
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);
}
}
}
}
以上程序的输出结果为：
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
