7-图

图（Graph）是一种非线性的数据结构，用于表示物体之间的关系。图由一组节点（Vertex）和一组边（Edge）组成，其中边连接着图中的两个节点。图在现实生活中有很多应用，比如社交网络、交通系统、互联网拓扑结构等。

图是网络结构的抽象模型，是一组由边连接的节点。图可以表示任何二元关系，比如道路、航班。JS中没有图，但是可以用Object和Array构建图。图的表示法：邻接矩阵、邻接表、关联矩阵。

基本概念

• 节点（Vertex）：图中的基本元素，表示物体或者状态。
• 边（Edge）：连接图中两个节点的线，表示节点之间的关系或联系。边有两种类型：
  • 有向边（Directed Edge）：边有方向，从一个节点指向另一个节点。
  • 无向边（Undirected Edge）：边没有方向，连接的两个节点是对等的。
• 邻接（Adjacency）：两个节点之间如果有边连接，称这两个节点是邻接的。
• 度（Degree）：一个节点的度是与它相连接的边的数目。
  • 入度（Indegree）：指向该节点的边的数量（仅适用于有向图）。
  • 出度（Outdegree）：从该节点指向其他节点的边的数量（仅适用于有向图）。

表示

// 邻接表表示图结构
const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

// 深度优先遍历
const visited = new Set()
function dfs(n, visited) { // n 表示开始访问的根节点
    console.log(n)
    visited.add(n)
    graph[n].forEach((item) => {
        if (!visited.has(item)) dfs(item, visited) 
    })
}
dfs(2, visited) // 2 0 1 3
console.log(visited) // {2, 0, 1, 3}

// 广度优先遍历
function bfs(n) { // n 表示开始访问的根节点
    const visited = new Set()
    visited.add(n)
    const queue = [n]
    while (queue.length) {
        const shiftVal = queue.shift()
        graph[shiftVal].forEach((item) => {
            if (!visited.has(item)) {
                queue.push(item)
                visited.add(item)
            } 
        })
    }
    console.log(visited) // {2, 0, 3, 1}
}
bfs(2)

使用场景

• 场景一：道路
• 场景二：航班

LeetCode题目

● 65 有效数字
● 417 太平洋大西洋水流问题
● 133 克隆图

分类

图可以根据不同的特征进行分类：

2.1 根据边的方向

• 有向图（Directed Graph, Digraph）：每条边都有一个方向，边从一个节点指向另一个节点。比如社交网络中“关注”关系可以用有向图表示。
• 无向图（Undirected Graph）：边没有方向，两个节点之间的边没有特定的起始点或终点。比如道路网络、社交网络中的“朋友”关系可以用无向图表示。

2.2 根据边的数量

• 简单图（Simple Graph）：没有自环（一个节点不能通过一条边指向自己）和重复的边。
• 多重图（Multigraph）：允许多条边连接同一对节点。
• 带权图（Weighted Graph）：每条边都有一个权重，表示节点之间的距离或成本。常见于网络流、地图导航等应用中。

2.3 根据图的连通性

• 连通图（Connected Graph）：图中的任意两个节点都有路径相连。
  • 对于无向图，连通图指的是图中的任意两点之间都存在路径。
  • 对于有向图，强连通图指的是任意两个节点之间都可以互相到达。
• 非连通图（Disconnected Graph）：图中存在至少一对节点之间没有路径连接。

2.4 根据图的结构

• 树（Tree）：一种特殊的图，没有环（循环），是一个连通无环的有向图或无向图。
• 有向无环图（Directed Acyclic Graph, DAG）：有向图且没有环，常用于表示依赖关系，比如任务调度、版本控制等。

图的表示方法

图可以通过以下几种方式进行表示：

3.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个二维数组，其中矩阵的行和列都表示图中的节点。如果节点 i_i_ 和节点 j_j_ 之间有边，则矩阵元素 A[i][j]=1_A_[i][j]=1（对于无权图）或 A[i][j]=边的权重_A_[i][j]=边的权重（对于带权图）；如果没有边，则为 0。

• 优点：方便进行图的操作（如查找某两节点之间是否有边），但空间复杂度较高。
• 缺点：存储空间复杂度为 O(V2)O(V_2)，其中 V_V 为节点数。对于稀疏图，效率较低。

pythonCopy Code# 邻接矩阵表示图
graph = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]

3.2 邻接表（Adjacency List）

邻接表是一种更节省空间的表示方法。它使用一个数组或链表来存储每个节点的所有邻接节点。每个节点都有一个链表，链表中的元素表示该节点与其他节点的边。

• 优点：空间复杂度较低，适用于稀疏图。
• 缺点：查找两个节点之间是否有边较慢。

pythonCopy Code# 邻接表表示图
graph = {
    0: [1],
    1: [0, 2, 3],
    2: [1],
    3: [1]
}

3.3 边列表（Edge List）

边列表是通过一个边的集合来表示图，每一条边表示为一个二元组或三元组（带权边）。这种表示方式常用于存储图的数据结构，特别适合于边的遍历。

• 优点：表示方式简洁，适合边的处理。
• 缺点：对于图的其他操作（如查找节点的邻居）较为不便。

pythonCopy Code# 边列表表示图
graph = [(0, 1), (1, 2), (1, 3)]

常见操作

4.1 遍历图

• 深度优先搜索（DFS）：从一个节点开始，尽可能深地遍历图，直到无法继续，再回溯到上一个节点。适合用栈实现。

pythonCopy Codedef dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

• 广度优先搜索（BFS）：从一个节点开始，先访问所有邻居节点，再逐层访问更远的节点，适合用队列实现。

pythonCopy Codefrom collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

4.2 查找最短路径

• Dijkstra算法：用于找出从起始节点到其他所有节点的最短路径，适用于带权图。
• Bellman-Ford算法：可以处理带负权边的图，能够检测负权环。

4.3 拓扑排序

拓扑排序是有向无环图（DAG）中的一种排序方式，按照边的依赖关系将图的节点进行排序。常用于任务调度、编译顺序等。

应用场景

• 社交网络：图用于表示人与人之间的关系，节点是人，边是社交联系。
• 互联网：图表示网页与网页之间的链接关系，节点是网页，边是超链接。
• 地图与导航：图可以表示交通网络，节点是交叉口或地点，边是道路或路线。
• 任务调度与依赖关系：图用于表示任务间的依赖关系，拓扑排序可以帮助确定任务的执行顺序。
• 计算机网络：图用于表示计算机网络中的路由和数据流。