图
利用 字典
function Map() {
var items = {};
// has(key)方法
this.has = function (key) {
return items.hasOwnProperty(key);
};
// set(key, val)方法
this.set = function (key, val) {
items[key] = val;
};
// remove(key)方法
this.remove = function (key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
};
// get(key)方法
this.get = function (key) {
return this.has(key) ? items[key] : undefined;
};
// values()方法
this.values = function () {
return Object.values(items);
};
// keys()方法
this.keys = function () {
return Object.keys(items);
};
// clear()方法
this.clear = function () {
items = {};
};
// size()方法
this.size = function () {
return Object.keys(items).length;
};
// getItems()方法
this.getItems = function () {
return items;
};
}
// 利用 队列
function Queue() {
// 使用数据结构为数组来存储队列中的元素
var items = [];
this.enqueue = function (ele) {
items.push(ele);
};
this.dequeue = function () {
return items.shift();
};
this.front = function () {
return items[0];
};
this.isEmpty = function () {
return items.length === 0;
};
this.size = function () {
return items.length;
};
this.print = function () {
console.log(items.toString());
};
}
// 利用 栈
function Stack() {
var items = [];
// push方法
this.push = function(ele) {
items.push(ele);
};
// pop方法
this.pop = function() {
return items.pop();
};
// peek方法
this.peek = function() {
return items[items.length - 1];
};
// isEmpty方法
this.isEmpty = function() {
return items.length === 0;
};
// clear方法
this.clear = function() {
// items.length = 0; // 保留了数组其他属性
items = []; // 更高效
};
// size方法
this.size = function() {
return items.length;
};
// 最后实现一个辅助方法print打印栈的内容
this.print = function() {
console.log(items.toString());
};
}
创建图类
function Graph() {
var vertices = [];
var adjList = new Map();
this.addVertex = function (v) {
vertices.push(v);
adjList.set(v, []);
};
this.addEdge = function (v, w) {
adjList.get(v).push(w);
adjList.get(w).push(v);
};
// 输出
this.toString = function () {
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('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());
// 使用广度优先搜索
function printNode(val) {
console.log('访问顶点：' + val);
}
// graph.bfs(myVertices[0], printNode);
var shortestPathA = graph.BFS(myVertices[0]);
console.log(shortestPathA);
var fromVertex = myVertices[0];
for (var i = 1; i < myVertices.length; i++) {
var toVertex = myVertices[i],
path = new Stack();
for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
path.push(v);
}
path.push(fromVertex);
var s = path.pop();
while (!path.isEmpty()) {
s += ' - ' + path.pop();
}
console.log(s);
}
// 使用深度优先搜索
graph.dfs(printNode);
图的遍历
两种算法可以对图进行遍历：==广度优先搜索和深度优先搜索==
| 算法 | 数据结构 |
|---|---|
| 广度优先搜索 | 栈 |
| 深度优先搜索 | 队列 |
当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态
- 白色：表示该顶点还没有被访问。
- 灰色：表示该顶点被访问过，但没有被搜索过。
- 黑色：表示该顶点被访问过且被完全搜索过。
// 初始化为白色状态
var initColor = function () {
var color = [];
for (var i = 0; i < vertices.length; i++) {
color[vertices[i]] = 'white'; //1
}
return color;
};
// 广度优先搜索
this.bfs = function (v, callback) {
var color = initColor(), //2
queue = new Queue(); //3
queue.enqueue(v); //4
while (!queue.isEmpty()) {
var u = queue.dequeue(), //6
neighbors = adjList.get(u); //7
color[u] = 'grey'; //8
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i]; //10
if (color[w] === 'white') {
color[w] = 'grey'; //12
queue.enqueue(w); //13
}
}
color[u] = 'black'; //14
callback && callback(u); //15
}
};
this.BFS = function (v) {
var color = initColor(), queue = new Queue(), d = [], //1
pred = []; //2
queue.enqueue(v);
for (var i = 0; i < vertices.length; i++) {
d[vertices[i]] = 0; // 4
pred[vertices[i]] = null; //5
}
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';
d[w] = d[u] + 1; // 6
pred[w] = u;
queue.enqueue(w);
}
}
color[u] = 'black';
}
return {
distances: d,
predecessors: pred
};
};
// 深度优先搜索
this.dfs = function (callback) {
var color = initColor();
for (var i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === 'white') {
dfsVisit(vertices[i], color, callback);
}
}
};
var dfsVisit = function (u, color, cb) {
color[u] = 'grey';
cb && cb(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, cb);
}
}
color[u] = 'black';
};
// 改进版
var time = 0;
this.DFS = function () {
var color = initColor(),
d = [],
f = [],
p = [];
time = 0;
for (var i = 0; i < vertices.length; i++) {
f[vertices[i]] = 0;
d[vertices[i]] = 0;
p[vertices[i]] = null;
}
for (i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === 'white') {
DFSVisit(vertices[i], color, d, f, p);
}
}
return {
discovery: d,
finished: f,
predecessors: p
};
};
var DFSVisit = function (u, color, d, f, p) {
console.log('发现' + u);
color[u] = 'grey';
d[u] = ++time;
var neighbors = 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('探索' + u);
};
网友评论