//定义类
class Graph {
constructor() {
this.vertices = new Set();
this.edges = new Map();
}
addVertex(v) {
if (this.vertices.has(v)) return;
this.vertices.add(v);
this.edges.set(v, new Set());
}
addEdge(v1, v2) {
if (!this.vertices.has(v1)) return;
if (!this.vertices.has(v2)) return;
const v1s = this.edges.get(v1);
const v2s = this.edges.get(v2);
v1s.add(v2);
v2s.add(v1);
}
toString() {
let s = "";
for (let v of this.vertices) {
s += `${v}->[${[...this.edges.get(v)].join()}]\n`;
}
return s;
}
/*
深度优先遍历（DFS）
深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。
简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。
DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。
注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。
*/
dfs() {
const marked = {};
const dfsVisit = (v) => {
console.log(v);
marked[v] = true;
const edge = this.edges.get(v);
for (let nv of edge) {
if (!marked[nv]) dfsVisit(nv);
}
};
for (let v of this.vertices) {
if (!marked[v]) dfsVisit(v);
}
}
/*
广度优先遍历（BFS）
广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS
BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层
*/
bfs(root) {
const marked = {};
const queue = [];
marked[root] = true;
queue.push(root);
while (queue.length) {
const c = queue.shift();
console.log(c);
const edge = this.edges.get(c);
for (let nv of edge) {
if (!marked[nv]) {
marked[nv] = true;
queue.push(nv);
}
}
}
}
}
//测试
var graph = new Graph();
var vertices = [1, 2, 3, 4, 5];
for (var i = 0; i < vertices.length; i++) {
graph.addVertex(vertices[i]);
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
console.log(graph.toString());
/*
1->[4,3]
2->[3,5]
3->[1,2]
4->[1]
5->[2]
*/
console.log("dfs:");
graph.dfs();
/*
dfs:
1
4
3
2
5
*/
console.log("bfs:");
graph.bfs(1);
/*
bfs:
1
4
3
2
5
*/
//测试2
var graph2 = new Graph();
var vertices = [1, 2, 3, 4, 5, 6, 7, 8];
for (var i = 0; i < vertices.length; i++) {
graph2.addVertex(vertices[i]);
}
graph2.addEdge(1, 2); //增加边
graph2.addEdge(2, 4);
graph2.addEdge(2, 5);
graph2.addEdge(4, 8);
graph2.addEdge(5, 8);
graph2.addEdge(1, 3);
graph2.addEdge(3, 6);
graph2.addEdge(3, 7);
graph2.addEdge(6, 7);
console.log(graph2.toString());
/*
1->[2,3]
2->[1,4,5]
3->[1,6,7]
4->[2,8]
5->[2,8]
6->[3,7]
7->[3,6]
8->[4,5]
*/
console.log("dfs:");
graph2.dfs();
/*
dfs:
1
2
4
8
5
3
6
7
*/
console.log("bfs:");
graph2.bfs(1);
/*
bfs:
1
2
3
4
5
6
7
8
*/
网友评论