图
大约 11 分钟
图
在生命旅途中，我们就像是一个个节点，被无数看不见的边相连。每一次的相识与相遇，都在这张巨大的网络途中留下独特的印记。
图
图(graph)是一种非线性数据结构，由 顶点(vertex) 和 边(edge) 组成，我们可以将图 G 抽象地表示为一组由顶点 V 和边 E 组成的集合。
V={1,2,3,4,5}
E={(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5)}
G={V,E}
若将顶点看作节点，将边看作连接各个节点的引用，我们也可以将图看作一种从链表扩展而来的数据结构。相对于线性关系（链表）和分治关系（树）来说，网络关系（图）的自由度更高，也更加复杂。
图的常见类型与术语
根据边是否具有方向，分为 无向图 和 有向图，具体区别如下：
- 在无向图中，边表示两顶点之间的“双向”连接关系。
- 在有向图中，边具有方向性，即 A->B 和 A<-B 两个方向的边是相互独立的。
根据所有顶点是否相通，分为 连通图 和 非连通图，区别如下：
- 对于连通图，从某个顶点出发，可以到达任意一个顶点。
- 对于非连通图，从某个顶点出发，至少有一个顶点无法到达。
还可对边进行加权
图数据结构包含以下常用术语：
- 邻接：当两顶点之间存在边相连时，称这两顶点“邻接”。
- 路径：从顶点A到顶点B所经过的边构成的序列被称为从A到B的“路径”。
- 度：一个顶点拥有的边数。对于有向图，入度 表示有多少条边指向该顶点，出度表示有多少条边从该顶点指出。
图的表示
图的常用表示方式包括“邻接矩阵”和“邻接表”
1. 邻接矩阵
设图的顶点数量为n，邻接矩阵使用一个n*n大小的矩阵来表示图，每一行代表一个顶点，矩阵元素代表边，使用0和1表示两个顶点之间是否存在边。
假设邻接矩阵为M，顶点列表为V，那么矩阵元素M[i,j]=1，表示顶点V[i]和V[j]之间存在边。，反之m[i,j]=0代表两顶点之间不存在边。
邻接矩阵具有以下特性：
- 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
- 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
- 将邻接矩阵的元素从1和0替换为权重，则可表示有权图。
使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删改查效率很高，时间复杂度均为O(1)，但是空间复杂度为O(n^2)，内存占用较多。
2. 邻接表
邻接表使用n各链表来表示图，链表节点表示顶点。第i个链表对应顶点i，其中存储了该顶点的所有邻接顶点。
邻接表仅存储实际存在的表，而边的总数通常远小于n^2，因此它更加节省空间，但是由于是存储在链表中，它需要通过遍历链表来查找边，因此时间效率不如邻接矩阵。
图的基本操作
图的基本操作可分为对“边”的操作和对“顶点”的操作，在邻接矩阵和邻接表两种表示方法下，实现方式有所不同。
基于邻接矩阵的实现
给定一个顶点数量为n的无向图，对图的操作如下：
- 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用O(1)时间，由于是无向的，因此需要同时更新两个方向的边。
- 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填0即可，使用O(n)时间。
- 删除顶点：在邻接矩阵中删除一行一列，当删除首行首列时达到最差情况，需要将(n-1)2个元素“向左上移动”，使用O(n2)时间。
- 初始化：传入n个顶点，初始化长度为n的顶点列表vertices，使用O(n)的时间，初始化n x n大小的邻接矩阵adjMat，使用O(n^2)时间。
/**
* 基于邻接矩阵实现图的操作
*/
class Graph {
vertices; // 顶点列表
adjMat; // 邻接矩阵
constructor(vertices, edges) {
this.vertices = [];
this.adjMat = [];
// 添加顶点
for (const val of vertices) {
// 指向单个添加顶点
this.addVertex(val);
}
// 添加边，edges内含相互有边的顶点，将0改为1
for (const e of edges) {
this.addEdge(e[0], e[1]);
}
}
// 获取大小
size() {
return this.vertices.length;
}
// 添加顶点：添加一行一列，全部填0
addVertex(val) {
let n = this.size();
// 先将值推入顶点列表中
this.vertices.push(val);
// 在邻接矩阵中添加一行
const newRow = [];
for (let j = 0; j < n; j++) {
newRow.push(0);
}
this.adjMat.push(newRow);
// 在邻接矩阵中添加一列
for (const row of this.adjMat) {
row.push(0);
}
}
/* 删除顶点 */
removeVertex(index) {
if (index >= this.size()) {
throw new RangeError("Index Out Of Bounds Exception");
}
// 在顶点列表中移除索引 index 的顶点
this.vertices.splice(index, 1);
// 在邻接矩阵中删除索引 index 的行
this.adjMat.splice(index, 1);
// 在邻接矩阵中删除索引 index 的列
for (const row of this.adjMat) {
row.splice(index, 1);
}
}
/* 添加边 */
// 参数 i, j 对应 vertices 元素索引
addEdge(i, j) {
// 索引越界与相等处理
if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
throw new RangeError("Index Out Of Bounds Exception");
}
// 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) === (j, i)
this.adjMat[i][j] = 1;
this.adjMat[j][i] = 1;
}
/* 删除边 */
// 参数 i, j 对应 vertices 元素索引
removeEdge(i, j) {
// 索引越界与相等处理
if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
throw new RangeError("Index Out Of Bounds Exception");
}
this.adjMat[i][j] = 0;
this.adjMat[j][i] = 0;
}
/* 打印邻接矩阵 */
print() {
console.log("顶点列表 = ", this.vertices);
console.log("邻接矩阵 =", this.adjMat);
}
}
const gragp = new Graph(
[1, 2, 3, 4],
[
[0, 1],
[0, 2],
[2, 3],
]
);
gragp.print();
基于邻接表的实现
设无向图的顶点总数为n，边总数为m，则图的各项操作如下：
- 初始化：在邻接表中创建n个顶点和2m条边，使用O(n+2m)的时间。
- 添加边：在顶点对应链表的末尾添加边即可，使用O(1)的时间，由于是无向图，所有需要同时添加两个方向的边。
- 删除边：在顶点对应链表中查找并删除指定的边，使用O(m)的时间，在无向图中，需要同时删除两个方向的边。
- 添加顶点：在邻接表中添加一个链表，并将新增的顶点作为链表头节点，使用O(1)的时间。
- 删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用O(n+m)的时间。
、
/**
* 基于邻接表来实现图的操作
*/
class Graph {
adjList;
// 边
constructor(edges = []) {
this.adjList = new Map();
for (const edge of edges) {
// 添加顶点
this.addVertex(edge[0]);
this.addVertex(edge[1]);
// 添加边
this.addEdge(edge[0], edge[1]);
}
}
// 添加顶点
addVertex(v) {
if (this.adjList.has(v)) return;
this.adjList.set(v, []);
}
/* 删除顶点 */
removeVertex(vet) {
if (!this.adjList.has(vet)) {
throw new Error("Illegal Argument Exception");
}
// 在邻接表中删除顶点 vet 对应的链表
this.adjList.delete(vet);
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (const set of this.adjList.values()) {
const index = set.indexOf(vet);
if (index > -1) {
set.splice(index, 1);
}
}
}
// 添加边
addEdge(vet1, vet2) {
if (
!this.adjList.has(vet1) ||
!this.adjList.has(vet2) ||
vet1 === vet2
) {
throw new Error("Illegal Argument Exception");
}
// 添加边 vet1 - vet2
this.adjList.get(vet1).push(vet2);
this.adjList.get(vet2).push(vet1);
}
// 删除边
removeEdge(vet1, vet2) {
if (
!this.adjList.has(vet1) ||
!this.adjList.has(vet2) ||
vet1 === vet2
) {
throw new Error("Illegal Argument Exception");
}
// 删除边 vet1 - vet2
this.adjList.get(vet1).splice(this.adjList.get(vet1).indexOf(vet2), 1);
this.adjList.get(vet2).splice(this.adjList.get(vet2).indexOf(vet1), 1);
}
/* 打印邻接表 */
print() {
console.log("邻接表 =");
console.log(this.adjList);
for (const [key, value] of this.adjList) {
console.log(key, value);
const tmp = [];
for (const vertex of value) {
tmp.push(vertex);
}
console.log(key + ": " + tmp.join());
}
}
/* 获取顶点数量 */
size() {
return this.adjList.size;
}
}
let gragp = new Graph([
["A", "B"],
["A", "C"],
["A", "D"],
["B", "E"],
["B", "F"],
["C", "G"],
["D", "H"],
["E", "I"],
["F", "J"],
["G", "K"],
["H", "L"],
]);
gragp.print()
邻接矩阵体现出的是以空间换时间，邻接表则体现了以时间换空间。
图的遍历
数代表的是一对多关系，而图则有更高的自由度，可以表示任意的多对多关系，因此可以将树看作为图的特例。
图和树都需要应用搜索算法来实现遍历操作，图的遍历方式也可以分为两种：广度优先遍历和深度优先遍历。
广度优先遍历
广度优先遍历是一种由近及远的遍历方式，从某个节点触发，始终优先访问距离最近的顶点，并一层层向外扩张。
/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
function graphBFS(graph, startVet) {
// 顶点遍历序列
const res = [];
// 哈希集合，用于记录已被访问过的顶点
const visited = new Set();
visited.add(startVet);
// 队列用于实现 BFS
const que = [startVet];
// 以顶点 vet 为起点，循环直至访问完所有顶点
while (que.length) {
const vet = que.shift(); // 队首顶点出队
res.push(vet); // 记录访问顶点
// 遍历该顶点的所有邻接顶点
for (const adjVet of graph.adjList.get(vet) ?? []) {
if (visited.has(adjVet)) {
continue; // 跳过已被访问的顶点
}
que.push(adjVet); // 只入队未访问的顶点
visited.add(adjVet); // 标记该顶点已被访问
}
}
// 返回顶点遍历序列
return res;
}
复杂度分析：
- xxxxxxxxxx /** * Top-k问题 /let nums = [1, 7, 6, 3, 2];let k = 3; // 获取数组中最大的k个元素// 方法一：k轮遍历function topKMap(nums, k) { let result = []; let copy = JSON.parse(JSON.stringify(nums)); for (let i = 0; i < k; i++) { // 将数组中最大push进去, 并在数组中删除 result.push(Math.max(...copy)); copy.splice(copy.indexOf(Math.max(...copy)), 1); } console.log(result); return result;}topKMap(nums, k);// 方法二：排序function topKSort(nums, k) { let result = []; let copy = JSON.parse(JSON.stringify(nums)); // 从大到小排序 copy.sort((a, b) => b - a); // 取0~k索引位置元素 result = copy.slice(0, k); console.log(result); return result;}topKSort(nums, k);// 方法三：堆class MaxHeap { heap; constructor(heap) { this.heap = heap || []; // 初始化堆 } / 获取左子节点索引 / getLeftIndex = (i) => i * 2 + 1; / 获取右子节点索引 / getRightIndex = (i) => i * 2 + 2; / 获取父节点索引 / getParentIndex = (i) => Math.floor((i - 1) / 2); / 获取堆顶元素 / peek = () => this.heap[0]; / 获取大小 / size = () => this.heap.length; / 堆化 / shiftUp = (i) => { while (true) { // 当前节点小于父节点，则交换 if (this.heap[i] <= this.heap[this.getParentIndex(i)]) { // 交换 this.swap(i, this.getParentIndex(i)); // 继续向上堆化 i = this.getParentIndex(i); } else { break; } } }; / 元素入堆 / push = (val) => { this.heap.push(val); // 开始堆化 this.shiftUp(this.size() - 1); }; / 交换元素 */ swap = (i, p) => { [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]]; }; // 堆顶出堆 pop = () => { if (this.heap.length === 0) return "堆为空"; // 交换堆顶与堆底元素 this.swap(0, this.size() - 1); // 删除堆底元素（原堆顶元素） this.heap.pop(); };}function topKHeap(nums, k) { let heap = new MaxHeap([]); // 将前k项入堆 for (let i = 0; i < k; i++) { // 1 7 6 建堆 heap.push(nums[i]); } // 从k+1项开始，若当前元素大于堆顶元素，则堆顶元素出堆，该元素入堆 for (let j = k; j < nums.length; j++) { if (nums[j] > heap.peek()) { // 堆顶出堆 heap.pop(); // 该元素入堆 heap.push(nums[j]); } } console.log(heap.heap);}topKHeap(nums, k);javascript
- 空间复杂度：列表res，哈希表visited，队列que中顶点数量最多为|V|，使用O(|V|)空间。
深度优先遍历
深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。
/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
function dfs(graph, visited, res, vet) {
res.push(vet); // 记录访问顶点
visited.add(vet); // 标记该顶点已被访问
// 遍历该顶点的所有邻接顶点
for (const adjVet of graph.adjList.get(vet)) {
if (visited.has(adjVet)) {
continue; // 跳过已被访问的顶点
}
// 递归访问邻接顶点
dfs(graph, visited, res, adjVet);
}
}
/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
function graphDFS(graph, startVet) {
// 顶点遍历序列
const res = [];
// 哈希集合，用于记录已被访问过的顶点
const visited = new Set();
dfs(graph, visited, res, startVet);
return res;
}
复杂度分析：
- 时间复杂度：所有顶点都会入队并出队一次，使用O(|V|)时间，在遍历邻接节点时，由于是无向图，因此所有边都会被访问2次，使用O(2|E|)时间，因此总时间复杂度为O(|V|+|E|)。
- 空间复杂度：列表res，哈希表visited，队列que中顶点数量最多为|V|，使用O(|V|)空间。
Loading...