跳到主要内容

图

简介​

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂。

分类及相关术语​

根据边是否有方向可分为

  • 无向图（undirected graph）
  • 有向图（directed graph）

根据所有顶点是否连通

  • 连通图：从某个顶点出发，可以到达其余任意顶点
  • 非连通图：从某个顶点出发，至少有一个顶点无法到达

有权图：边有权重。

常用术语：

  • 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。
  • 路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。
  • 度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。

图的表示​

图的常用表示方式包括“邻接矩阵”和“邻接表”。

邻接矩阵​

设图的顶点数量为 n ，邻接矩阵（adjacency matrix）使用一个 n×nn×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为 O(n2)O(n^2) ，内存占用较多。

邻接表​

邻接表（adjacency list）使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。

邻接表仅存储实际存在的边，而边的总数通常远小于 n2n^2 ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

图的基本操作​

基于邻接矩阵​

class GraphAdjMat:
    """基于邻接矩阵实现的无向图类"""

    def __init__(self, vertices: list[int], edges: list[list[int]]):
        """构造方法"""
        self.vertices: list[int] = []
        self.adj_mat: list[list[int]] = []
        # 添加顶点
        for val in vertices:
            self.add_vertex(val)
        # 添加边
        for e in edges:
            self.add_edge(e[0], e[1])

    def size(self) -> int:
        """获取顶点数量"""
        return len(self.vertices)

    def add_vertex(self, val: int):
        """添加顶点"""
        n = self.size()
        # 向顶点列表中添加新顶点的值
        self.vertices.append(val)
        # 在邻接矩阵中添加一行
        new_row = [0] * n
        self.adj_mat.append(new_row)
        # 在邻接矩阵中添加一列
        for row in self.adj_mat:
            row.append(0)

    def remove_vertex(self, index: int):
        """删除顶点"""
        if index >= self.size():
            raise IndexError()
        # 在顶点列表中移除索引 index 的顶点
        self.vertices.pop(index)
        # 在邻接矩阵中删除索引 index 的行
        self.adj_mat.pop(index)
        # 在邻接矩阵中删除索引 index 的列
        for row in self.adj_mat:
            row.pop(index)

    def add_edge(self, i: int, j: int):
        """添加边"""
        # 索引越界与相等处理
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1

    def remove_edge(self, i: int, j: int):
        """删除边"""
        # 索引越界与相等处理
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0


"""Driver Code"""
if __name__ == "__main__":
    # 初始化无向图
    vertices = [1, 3, 2, 5, 4]
    edges = [[0, 1], [0, 3], [1, 2], [2, 3], [2, 4], [3, 4]]
    graph = GraphAdjMat(vertices, edges)

    # 添加边
    # 顶点 1, 2 的索引分别为 0, 2
    graph.add_edge(0, 2)

    # 删除边
    # 顶点 1, 3 的索引分别为 0, 1
    graph.remove_edge(0, 1)

    # 添加顶点
    graph.add_vertex(6)

    # 删除顶点
    # 顶点 3 的索引为 1
    graph.remove_vertex(1)

基于邻接表​

class Vertex:
    """顶点类"""
    def __init__(self, val: int):
        self.val = val

def vals_to_vets(vals: list[int]) -> list["Vertex"]:
    """输入值列表 vals ，返回顶点列表 vets"""
    return [Vertex(val) for val in vals]


class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        self.adj_list = dict[Vertex, list[Vertex]]()
        # 添加所有顶点和边
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def size(self) -> int:
        """获取顶点数量"""
        return len(self.adj_list)

    def add_edge(self, vet1: Vertex, vet2: Vertex):
        """添加边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        # 添加边 vet1 - vet2
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def remove_edge(self, vet1: Vertex, vet2: Vertex):
        """删除边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        # 删除边 vet1 - vet2
        self.adj_list[vet1].remove(vet2)
        self.adj_list[vet2].remove(vet1)

    def add_vertex(self, vet: Vertex):
        """添加顶点"""
        if vet in self.adj_list:
            return
        # 在邻接表中添加一个新链表
        self.adj_list[vet] = []

    def remove_vertex(self, vet: Vertex):
        """删除顶点"""
        if vet not in self.adj_list:
            raise ValueError()
        # 在邻接表中删除顶点 vet 对应的链表
        self.adj_list.pop(vet)
        # 遍历其他顶点的链表，删除所有包含 vet 的边
        for vertex in self.adj_list:
            if vet in self.adj_list[vertex]:
                self.adj_list[vertex].remove(vet)


"""Driver Code"""
if __name__ == "__main__":
    # 初始化无向图
    v = vals_to_vets([1, 3, 2, 5, 4])
    edges = [
        [v[0], v[1]],
        [v[0], v[3]],
        [v[1], v[2]],
        [v[2], v[3]],
        [v[2], v[4]],
        [v[3], v[4]],
    ]
    graph = GraphAdjList(edges)
    del edges

    # 添加边
    graph.add_edge(v[0], v[2])

    # 删除边
    graph.remove_edge(v[0], v[1])

    # 添加顶点
    v5 = Vertex(6)
    graph.add_vertex(v5)

    # 删除顶点
    graph.remove_vertex(v[1])

图的遍历​

图的遍历方式可分为两种：广度优先遍历和深度优先遍历。

广度优先遍历​

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。

BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。

from collections import deque

class Vertex:
    """顶点类"""
    def __init__(self, val: int):
        self.val = val

def vals_to_vets(vals: list[int]) -> list["Vertex"]:
    """输入值列表 vals ，返回顶点列表 vets"""
    return [Vertex(val) for val in vals]

class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        self.adj_list = dict[Vertex, list[Vertex]]()
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def add_edge(self, vet1: Vertex, vet2: Vertex):
        """添加边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def add_vertex(self, vet: Vertex):
        """添加顶点"""
        if vet in self.adj_list:
            return
        self.adj_list[vet] = []


def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历"""
    # 顶点遍历序列
    res = []
    # 哈希表，用于记录已被访问过的顶点
    visited = set[Vertex]([start_vet])
    # 队列用于实现 BFS
    que = deque[Vertex]([start_vet])
    # 以顶点 vet 为起点，循环直至访问完所有顶点
    while len(que) > 0:
        vet = que.popleft()  # 队首顶点出队
        res.append(vet)  # 记录访问顶点
        # 遍历该顶点的所有邻接顶点
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue  # 跳过已被访问的顶点
            que.append(adj_vet)  # 只入队未访问的顶点
            visited.add(adj_vet)  # 标记该顶点已被访问
    # 返回顶点遍历序列
    return res

"""Driver Code"""
if __name__ == "__main__":
    # 初始化无向图
    v = vals_to_vets([0, 1, 2, 3, 4])
    edges = [
        [v[0], v[1]],
        [v[0], v[3]],
        [v[1], v[2]],
        [v[1], v[4]],
        [v[3], v[4]],
    ]
    graph = GraphAdjList(edges)
    del edges

    # 广度优先遍历
    res = graph_bfs(graph, v[0])

深度优先遍历​

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。

class Vertex:
    """顶点类"""
    def __init__(self, val: int):
        self.val = val

def vals_to_vets(vals: list[int]) -> list["Vertex"]:
    """输入值列表 vals ，返回顶点列表 vets"""
    return [Vertex(val) for val in vals]

class GraphAdjList:
    """基于邻接表实现的无向图类"""

    def __init__(self, edges: list[list[Vertex]]):
        """构造方法"""
        self.adj_list = dict[Vertex, list[Vertex]]()
        for edge in edges:
            self.add_vertex(edge[0])
            self.add_vertex(edge[1])
            self.add_edge(edge[0], edge[1])

    def add_edge(self, vet1: Vertex, vet2: Vertex):
        """添加边"""
        if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
            raise ValueError()
        self.adj_list[vet1].append(vet2)
        self.adj_list[vet2].append(vet1)

    def add_vertex(self, vet: Vertex):
        """添加顶点"""
        if vet in self.adj_list:
            return
        self.adj_list[vet] = []


def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)  # 记录访问顶点
    visited.add(vet)  # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue  # 跳过已被访问的顶点
        # 递归访问邻接顶点
        dfs(graph, visited, res, adjVet)


def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    # 顶点遍历序列
    res = []
    # 哈希表，用于记录已被访问过的顶点
    visited = set[Vertex]()
    dfs(graph, visited, res, start_vet)
    return res


"""Driver Code"""
if __name__ == "__main__":
    # 初始化无向图
    v = vals_to_vets([0, 1, 2, 3, 4])
    edges = [
        [v[0], v[1]],
        [v[0], v[3]],
        [v[1], v[2]],
        [v[1], v[4]],
        [v[3], v[4]],
    ]
    graph = GraphAdjList(edges)

    # 深度优先遍历
    res = graph_dfs(graph, v[0])

Dijkstra算法​

Dijkstra算法用于在加权图中找到最短路径

import heapq

def dijkstra(graph, start):
    # 初始化最短路径字典，所有节点的距离初始化为无穷大
    shortest_paths = {node: float('inf') for node in graph}
    shortest_paths[start] = 0  # 起始节点到自身的距离为 0
    
    # 优先队列（最小堆），存储 (当前距离, 当前节点)
    priority_queue = [(0, start)]
    
    while priority_queue:
        # heapq.heappop() 用于从最小堆（优先队列）中弹出最小值
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # 如果当前节点的距离比已知的最短距离更大，则跳过
        if current_distance > shortest_paths[current_node]:
            continue
        
        # 遍历当前节点的邻居
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # 如果找到更短的路径，则更新
            if distance < shortest_paths[neighbor]:
                shortest_paths[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return shortest_paths

# 示例图的邻接表表示
example_graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 运行 Dijkstra 算法
start_node = 'A'
shortest_paths = dijkstra(example_graph, start_node)
print(shortest_paths)

用Go实现

package main

import (
	"container/heap"
	"fmt"
	"math"
)

// Edge 结构表示图中的一条边
// dest: 目标节点, weight: 边的权重
type Edge struct {
	dest   string
	weight int
}

// Graph 采用邻接表表示，即一个节点到多个邻居的映射
type Graph map[string][]Edge

// Item 结构用于优先队列存储节点及其当前最短距离
type Item struct {
	node     string
	distance int
}

// PriorityQueue 实现最小堆，存储 (节点, 最短路径)
type PriorityQueue []Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

// Push 将新元素添加到优先队列
func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

// Pop 移除并返回优先队列中的最小元素
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

// Dijkstra 计算起始节点到所有其他节点的最短路径
type Dijkstra(graph Graph, start string) map[string]int {
	// 初始化最短路径字典，所有节点的距离设为无穷大
	shortestPaths := make(map[string]int)
	for node := range graph {
		shortestPaths[node] = math.MaxInt32
	}
	shortestPaths[start] = 0

	// 使用优先队列进行最短路径计算
	pq := &PriorityQueue{{node: start, distance: 0}}
	heap.Init(pq)

	for pq.Len() > 0 {
		// 取出当前距离最小的节点
		current := heap.Pop(pq).(Item)

		// 如果当前距离大于已存最短距离，跳过
		if current.distance > shortestPaths[current.node] {
			continue
		}

		// 遍历当前节点的邻居
		for _, edge := range graph[current.node] {
			distance := current.distance + edge.weight
			// 如果找到更短路径，更新最短路径字典
			if distance < shortestPaths[edge.dest] {
				shortestPaths[edge.dest] = distance
				heap.Push(pq, Item{node: edge.dest, distance: distance})
			}
		}
	}

	return shortestPaths
}

func main() {
	// 定义图的邻接表表示
	graph := Graph{
		"A": {{"B", 1}, {"C", 4}},
		"B": {{"A", 1}, {"C", 2}, {"D", 5}},
		"C": {{"A", 4}, {"B", 2}, {"D", 1}},
		"D": {{"B", 5}, {"C", 1}},
	}

	// 设置起始节点
	startNode := "A"
	// 运行 Dijkstra 算法
	shortestPaths := Dijkstra(graph, startNode)

	// 输出结果
	for node, distance := range shortestPaths {
		fmt.Printf("Shortest path from %s to %s: %d\n", startNode, node, distance)
	}
}