JavaScript实现图的深度广度优先遍历
function Graph(v) {
this.vertices = v;
//初始化顶点
this.edges = 0;
//边数先设置为0
this.adj = [];
//为每一个顶点准备一个链表,表示它和所有节点的关系
for (var i = 0; i < this.vertices.length; i++) {
this.adj[i] = [];
this.adj[i].push("");
}
this.addEdge = addEdge;
this.toString = toString;
}
function addEdge(v, w) {
//两个顶点组成一条边
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
function Graph(v) {
this.vertices = v;
//初始化顶点
this.edges = 0;
//边数先设置为0
this.adj = [];
//为每一个顶点准备一个链表,表示它和所有节点的关系
for (var i = 0; i < this.vertices.length; i++) {
this.adj[i] = [];
this.adj[i].push("");
}
this.addEdge = addEdge;
this.toString = toString;
}
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++) {
print(i + "=>");
for (var j = 0; j < this.vertices; ++j) {
if (this.adj[i][j] != "undefined") {
print(this.adj[i][j]);
}
}
}
}
function dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
print(v);
}
for (var key in adj[v]) {
if (!this.marked[w]) {
this.dfs(w);
}
}
}
function bfs(node) {
var queue = [];
this.marked[node] = true;
queue.push(node);
while (queue.length > 0) {
var v = queue.shift();//移出队列
if (v == undefined) {
print(v);
}
for (var w in this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo(w) = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}