function Graph() {
var vertices = [];
var adjList = new Dictionary();
this.addVertex = addVertex;
this.addEdge = addEdge;
this.toString = toString;
this.bfs = bfs;
this.dfs = dfs;
this.bfsVisit = bfsVisit;
this.dfsVisit = dfsVisit;
this.initializeColor = initializeColor;
function initializeColor() {
var color = [];
for (var i = 0; i < vertices.length; i++) {
color[vertices[i]] = 'white';
}
return color;
}
function bfs(v, callback) {
var color = initializeColor(),
queue = new Queue();
queue.enqueue(v);
while (!queue.isEmpty()) {
var u = queue.dequeue(),
neighbors = adjList.get(u);
color[u] = 'grey';
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === 'white') {
color[w] = 'grey';
queue.enqueue(w);
}
}
color[u] = 'black';
if (callback) {
callback(u);
}
}
}
function dfs(callback) {
var color = initializeColor();
for (var i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === 'white') {
dfsVisit(vertices[i], color, callback);
}
}
}
function dfsVisit(u, color, callback) {
color[u] = 'grey';
if (callback) {
callback(u);
}
var neighbors = 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';
}
function bfsVisit(u, color, callback) {
color[u] = 'grey';
var queue = new Queue();
queue.enqueue(u);
while (!queue.isEmpty()) {
var u = queue.dequeue(),
neighbors = adjList.get(u);
color[u] = 'grey';
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === 'white') {
color[w] = 'grey';
queue.enqueue(w);
}
}
color[u] = 'black';
if (callback) {
callback(u);
}
}
}
function addVertex(v) {
vertices.push(v);
adjList.set(v, []);
}
function addEdge(v, w) {
adjList.get(v).push(w);
adjList.get(w).push(v);
}
function toString() {
var s = '';
for (var i = 0; i < vertices.length; i++) {
s += vertices[i] + ' -> ';
var neighbors = adjList.get(vertices[i]);
for (var j = 0; j < neighbors.length; j++) {
s += neighbors[j] + ' ';
}
s += '\n';
}
return s;
}
}
var graph = new Graph();
var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
for (var i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('
没有回复内容