graph 图算法¶
统计信息：字数 3478 阅读7分钟
图在当前开发中使用不多（主要问题是桥问题，地图问题等）。图可以理解为一个复杂的树结构。不同的叶节点互相有联系。
遍历图：深度优先遍历和广度优先遍历
**深度优先搜索法**是树的先序遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。
图的**广度优先搜索**是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。
// 图的组成单位（顶点）属性是：标签，是否访问过
class Vertex() {
constructor(label, isVisited) {
this.label = label;
this.isVisited = isVisited;
}
}
// 初始化图（v顶点数）
class Graph(v) {
constructor() {
this.vertices = v;
this.edges = 0; // 边的数量
this.adj = []; // 邻接关系
this.marked = []; // 某个节点是否遍历过
// 使用三个属性存放图各个顶点的关系
for(let i = 0; i < v; ++i) {
this.adj[i] = [];
this.adj[i].push('');
this.marked[i] = false;
}
}
// 增加边（两个顶点增加边），那么设置两个 adj 相邻数组增加，同时增加边的数量
// 严格：应该先判断两个点是否有边，避免重复边出现
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
// 显示图路径（双重遍历节点）
showGrap() {
for (let i = 0; i < this.vertices; i++) {
console.log(i + '->');
for (let j = 0; j < this.vertices; ++j) {
// 如果两个点之间有连接，打印这个连接
if (this.adj[i][j] != undefined) {
console.log(this.adj[i][j] + ' ');
}
}
}
}
// 遍历图节点（深度优先遍历，从某个节点开始）
// 设置当前的节点已标记，然后遍历标记相邻的节点，递归处理
dfs(v) {
this.marked[v] = true;
// 如果当前节点的相邻节点不是空
if (this.adj[v] != undefined) {
// 递归遍历节点的相邻未经过的节点
for(let j in this.adj[v]) {
if(!this.marked[j]) {
this.dfs(w);
}
}
}
}
// 遍历图节点（广度优先遍历）
bfs(s) {
let q = [];
this.marked[s] = true;
q.push(s);
while(q.length>0) {
let v = q.shift();
if (this.adj[v] != undefined) {
//
}
for(let j in this.adj[v]) {
if(!this.marked[j]) {
this.marked[j] = true;
q.push(j);
}
}
}
}
}
Last update:
November 9, 2024