定义
相关概念和术语
数据结构
class Node {
index;
value;
visited;
inDegree; // 入度
outDegree;
etv;
ltv;
...
}
class Edge {
from,
to,
visited;
weight;
value;
ete;
vte
...
}
class G {
nodes;
edges;
adjList; // 邻接表
matrix; // 邻接矩阵
topoArray;
constructor(nodes, edges) {
this.nodes = nodes;
this.edges = edges;
// 初始化存储结构
// ...
}
traverseByDFS(visitFn) {
// visitFn(node)
}
traverseByBFS(visitFn) {
}
getTopoArray() {
}
// min spanning tree
prim() {
}
}
邻接表
邻接矩阵
创建和遍历
DFS
BFS
最小生成树
最短路径
拓扑排序
关键路径
最大团
常见算法
无向（无环）图中的最长路径
以任意一点为起点寻找最长路径，得到终点 P，再以 P 为起点寻找最长路径，该路径就是无向图中的最长路径。
以任一点开始寻找最长路径时，就相当于在树中求树的高度，使用 DFS + stack 就能求出。
有向图中的关键路径（最长路径）
- etv (earliest time of vertex): 找拓扑排序的过程
- ltv (latest time of vertex): 找拓扑排序的过程
- ete (earliest time of edge): ete(e(i, j)) = etv(j) - e(i, j).cost
- lte (latest time of edge): lte(e(i, j)) = ltv(j) - e(i, j).cost
ete === lte 表示该路径是关键路径
