图
图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。
基本概念：一个图 G = (V, E)由以下元素组成。
- V：一组顶点
- E：一组边，连接 V 中的顶点
术语
- 由一条边连接在一起的顶点称为相邻顶点
- 一个顶点的度是其相邻顶点的数量
路径是顶点 v1, v2, …, vk的一个连续序列，其中 vi和 vi+1是相邻的
- 简单路径要求不包含重复的顶点
- 如果图中不存在环，则称该图是无环的
- 如果图中每两个顶点间都存在路径，则该图是连通的
图可以是无向的（边没有方向）或是有向的（有向图）
- 如果图中每两个顶点间在双向上都存在路径，则该图是强连通的
- 图还可以是未加权的（目前为止我们看到的图都是未加权的）或是加权的
图的表示
- 邻接矩阵
- 邻接表
- 关联矩阵
class Graph {
constructor(isDirected = false) {
this.isDirected = isDirected; // 是否有向
this.vertices = []; // 顶点
this.adjList = new Dictionary(); // 顶点名为键，邻接顶点列表为值
}
addVertex(v) {
if (!this.vertices.includes(v)) {
this.vertices.push(v);
this.adjList.set(v, []);
}
}
addEdge(v, w) {
if (!this.adjList.get(v)) {
this.addVertex(v);
}
if (!this.adjList.get(w)) {
this.addVertex(w);
}
this.adjList.get(v).push(w);
if (!this.isDirected) {
this.adjList.get(w).push(v);
}
}
getVertices() {
return this.vertices;
}
getAdjList() {
return this.adjList;
}
toString() {
let s = '';
for(let i = 0; i < this.vertices.length; i++) {
s += `${this.vertices[i]} -> `;
const neighbors = this.adjList.get(this.vertices[i]);
for(let j = 0; j < neighbors.length; j++) {
s += `${neighbors[j]}`;
}
s += '\n';
}
return s;
}
}图的遍历
图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。
广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构
| 算法 | 数据结构 | 描述 |
|---|---|---|
| 深度优先搜索 | 栈 | 将顶点存入栈，顶点是沿着路径被探索的，存在新的相邻顶点就去访问 |
| 广度优先搜索 | 队列 | 将顶点存入队列，最先入队列的顶点先被探索 |
const Colors = {
WHITE: 0, // 没有被访问过
GREY: 1, // 被访问过但未被探索过
BLACK: 2 // 被访问过且被探索过
}
const initializeColor = vertices => {
const color = {};
for (let i = 0; i < vertices.length; i++) {
color[vertices[i]] = Colors.WHITE;
}
return color;
};
const breadthFirstSearch = (graph, startVertex, cb) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
const queue = new Queue();
queue.enqueue(startVertex);
while(!queue.isEmpty()) {
const u = queue.dequeue();
const neighbors = adjList.get(u);
color[u] = Colors.GREY;
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
color[w] = Colors.GREY;
queue.enqueue(w);
}
}
color[u] = Colors.BLACK;
if (cb) {
cb(u);
}
}
};
const depthFirstSearch = (graph, cb) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
for (let i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === Colors.WHITE) {
depthFirstSearchVisit(vertices[i], color, adjList, cb);
}
}
};
const depthFirstSearchVisit = (u, color, adjList, cb) => {
color[u] = Colors.GREY;
if (cb) {
cb(u);
}
const neighbors = adjList.get(u);
for(let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
depthFirstSearchVisit(w, color, adjList, cb);
}
}
color[u] = Colors.BLACK;
};- 使用BFS寻找最短路径
const BFS = (graph, startVertex) => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
const queue = new Queue();
const distances = {}; // 从v到u的距离distances[u]
const predecessors = {}; // 前溯点predecessors[u]，用来推导从v到其他每个顶点u的最短距离
queue.enqueue(startVertex);
for (let i = 0; i < vertices.length; i++) {
distances[vertices[i]] = 0;
predecessors[vertices[i]] = null;
}
while (!queue.isEmpty()) {
const u = queue.dequeue();
const neighbors = adjList.get(u);
color[u] = Colors.GREY;
for (let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
color[w] = Colors.GREY;
distances[w] = distances[w] + 1;
predecessors[w] = u;
}
}
color[u] = Colors.BLACK;
}
return {
distances,
predecessors
};
};- 改进的DFS
const DFS = graph => {
const vertices = graph.getVertices();
const adjList = graph.getAdjList();
const color = initializeColor(vertices);
const d = {}; // 顶点u的发现时间d[u]
const f = {}; // 当顶点u被标注为黑色时，u的完成探索时间f[u]
const p = {}; // 顶点u的前溯点p[u]
const time = { count: 0 };
for (let i = 0; i < vertices.length; i++) {
f[vertices[i]] = 0;
d[vertices[i]] = 0;
p[vertices[i]] = null;
}
for (let i = 0; i < vertices.length; i++) {
if (color[vertices[i]] === Colors.WHITE) {
DFSVisit(vertices[i], color, d, f, p, time, adjList);
}
}
return {
discovery: d,
finished: f,
predecessors: p,
};
};
const DFSVisit = (u, color, d, f, p, time, adjList) => {
color[u] = Colors.GREY;
d[u] = ++time.count;
const neighbors = adjList.get(u);
for(let i = 0; i < neighbors.length; i++) {
const w = neighbors[i];
if (color[w] === Colors.WHITE) {
p[w] = u;
DFSVisit(w, color, d, f, p, time, adjList);
}
}
color[u] = Colors.BLACK;
f[u] = ++time.count;
};最短路径算法
- Dijkstra算法
Dijkstra 算法是一种计算从单个源到所有其他源的最短路径的贪心算法
const graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 2, 4, 2, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 2],
[0, 0, 0, 3, 0, 2],
[0, 0, 0, 0, 0, 0]
];
const INF = Number.MAX_SAFE_INTEGER; // 无穷大
const minDistance = (dist, visited) => {
let min = INF;
let minIndex = -1;
for (let v = 0; v < dist.length; v++) {
if (visited[v] === false && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
};
const dijkstra = (graph, src) => {
const dist = [];
const visited = [];
const { length } = graph;
for (let i = 0; i < length; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[src] = 0;
for (let i = 0; i < length - 1; i++) {
const u = minDistance(dist, visited);
visited[u] = true;
for(let v = 0; v < length; v++) {
if (!visited[v] &&
graph[u][v] !== 0 &&
dist[u] !== INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
};- Floyd-Warshell
const floydWarshell = graph => {
const dist = [];
const { length } = graph;
for (let i = 0; i < length; i++) {
dist[i] = [];
for (let j = 0; j < length; j++) {
if (i === j) {
dist[i][j] = 0;
} else if (!isFinite(graph[i][j])) {
dist[i][j] = Infinity;
} else {
dist[i][j] = graph[i][j];
}
}
}
for (let k = 0; k < length; k++) {
for (let i = 0; i < length; i++) {
for (let j = 0; j < length; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}