14. 图-存储与遍历

概念

图（Graph） 由顶点集 V 和边集 E 组成，记为 G = (V, E)。图中的数据元素称为顶点（Vertex），顶点之间的关系称为边（Edge）。图比树更一般：树是一种特殊的图（连通且无环），而图中任意两个顶点之间都可以相连。

按边是否有方向，图分为两类：

无向图：边没有方向，用圆括号 (u, v) 表示，且 (u,v) 与 (v,u) 是同一条边。
有向图：边有方向，用尖括号 <u, v> 表示，代表从 u 指向 v 的弧，u 称为弧尾，v 称为弧头。

若边上带有数值（权值），则称为带权图，也叫网（Network）。权值常表示距离、花费、时间等。

顶点的度（Degree）：无向图中顶点的度是与它相连的边数；有向图中分为入度（指向该顶点的边数）和出度（从该顶点发出的边数）。

连通与连通分量：无向图中，若两个顶点之间存在路径则称它们连通；若任意两个顶点都连通，则该图为连通图。无向图的极大连通子图称为连通分量（连通图只有一个连通分量，即它本身）。有向图中，若任意两个顶点相互可达（双向都有路径），则称为强连通图，其极大强连通子图称为强连通分量。

两种存储结构

1. 邻接矩阵（Adjacency Matrix）

用二维数组 g[n][n] 存储：g[i][j] = 1 表示顶点 i 到 j 有边（无向图中对称，g[i][j] = g[j][i]）；带权图存权值、无边存无穷大 ∞、对角线存 0。

     0  1  2  3  4
 0 | 0  1  1  0  0
 1 | 1  0  0  1  1
 2 | 1  0  0  0  1
 3 | 0  1  0  0  0
 4 | 0  1  1  0  0

2. 邻接表（Adjacency List）

用一个顶点表数组，每个顶点挂一条单链表，链表中的每个结点存储一个邻接顶点的编号（无向图每条边出现两次，两个方向各一次；有向图通常只存出边）。

邻接矩阵 vs 邻接表对比：

对比项	邻接矩阵	邻接表
存储空间	O(n²)，与边数无关	O(n+e)，稀疏图省空间
判断两点是否相邻	O(1)	O(deg(v))，需扫描链表
找出某点的所有邻点	O(n)	O(deg(v))
求顶点的度	无向图 O(n)，有向图需统计行列	无向图 O(deg)，有向图还须另建入度表
适用场景	稠密图（边数接近 n²）	稀疏图（边数接近 n）

核心操作 / 算法

建立图：读入顶点和边。邻接矩阵直接填矩阵；邻接表把边的两个端点插入对方（或单向）的链表中。
BFS 广度优先遍历（Breadth-First Search）：借助队列。从起点出发先访问它，再将其所有未访问的邻点入队；随后依次出队并重复"访问 + 邻点入队"。特点：一层一层向外扩展（类似树的层次遍历），可求无权图的最短路径。
DFS 深度优先遍历（Depth-First Search）：借助递归（系统栈）或显式栈。从起点出发沿一条路径走到尽头，走不通就回退（回溯）换路再走。特点：一条路走到底再回头。
遍历的应用：判断连通性、求连通分量、检测环、求路径等。BFS 与 DFS 都要保证每个顶点只访问一次，用 visited 数组标记。

复杂度分析

操作	邻接矩阵	邻接表
判断两点是否相邻	O(1)	O(deg(v))
BFS 遍历	O(n²)	O(n+e)
DFS 遍历	O(n²)	O(n+e)
存储空间	O(n²)	O(n+e)

为什么：

邻接矩阵 BFS/DFS 中，每个顶点都要扫描一整行（n 个位置）来寻找邻点，n 个顶点共 O(n²)；即使边很少也必须查遍矩阵，空间恒为 O(n²)。
邻接表中，每个顶点恰好出队/入栈一次，共 O(n)；每条边恰好被扫描一次，共 O(e)，总计 O(n+e)。空间上每个顶点一个表头 O(n)，无向图每条边两个边结点 O(2e)，即 O(n+e)。

语言实现

下面 4 种语言的实现演示相同的操作：用邻接表存储同一个无向图（5 个顶点、5 条边），从顶点 0 出发分别做 BFS 和 DFS 并打印遍历序列。

C

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20

// 邻接表边结点：存储一个邻接顶点
typedef struct ArcNode {
    int adjvex;              // 邻接顶点的编号
    struct ArcNode *next;    // 指向下一条边的结点
} ArcNode;

// 顶点表结点
typedef struct VNode {
    int data;                // 顶点信息
    ArcNode *first;          // 指向第一条边
} VNode;

// 图结构：顶点表 + 顶点数
typedef struct {
    VNode vertices[MAX_VERTICES];
    int n;
} ALGraph;

// 初始化图：顶点编号 0..n-1 作为顶点数据
void initGraph(ALGraph *g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        g->vertices[i].data = i;
        g->vertices[i].first = NULL;
    }
}

// 向链表中尾部追加一个边结点（保持与其它语言 push_back 一致的顺序）
void appendArc(VNode *vnode, int v) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->next = NULL;
    if (vnode->first == NULL) {
        vnode->first = p;
        return;
    }
    ArcNode *t = vnode->first;
    while (t->next != NULL) t = t->next;
    t->next = p;
}

// 无向图加边 (u,v)：两个方向都要加
void addEdge(ALGraph *g, int u, int v) {
    appendArc(&g->vertices[u], v);
    appendArc(&g->vertices[v], u);
}

// BFS：借助队列，从 start 出发广度优先遍历
void bfs(ALGraph *g, int start) {
    int visited[MAX_VERTICES] = {0};
    int queue[MAX_VERTICES], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (ArcNode *p = g->vertices[u].first; p != NULL; p = p->next) {
            int v = p->adjvex;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
        }
    }
    printf("\n");
}

// DFS 辅助：递归访问顶点 u
void dfsVisit(ALGraph *g, int u, int visited[]) {
    printf("%d ", u);
    visited[u] = 1;
    for (ArcNode *p = g->vertices[u].first; p != NULL; p = p->next) {
        int v = p->adjvex;
        if (!visited[v])
            dfsVisit(g, v, visited);
    }
}

// DFS：从 start 出发深度优先遍历（递归）
void dfs(ALGraph *g, int start) {
    int visited[MAX_VERTICES] = {0};
    dfsVisit(g, start, visited);
    printf("\n");
}

int main() {
    ALGraph g;
    initGraph(&g, 5);

    // 无向图的边 (u, v)
    int edges[][2] = {{0,1}, {0,2}, {1,3}, {1,4}, {2,4}};
    for (int i = 0; i < 5; i++)
        addEdge(&g, edges[i][0], edges[i][1]);

    printf("BFS from 0: ");
    bfs(&g, 0);

    printf("DFS from 0: ");
    dfs(&g, 0);
    return 0;
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 邻接表：vector<int> 的数组，每个元素存邻接顶点编号
class Graph {
public:
    int n;
    vector<vector<int>> adj;

    Graph(int n) : n(n), adj(n) {}

    // 无向图加边 (u,v)
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // BFS：借助队列，从 start 出发广度优先遍历
    void bfs(int start) {
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        cout << endl;
    }

    // DFS 辅助：递归访问顶点 u
    void dfsVisit(int u, vector<bool>& visited) {
        cout << u << " ";
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v])
                dfsVisit(v, visited);
    }

    // DFS：从 start 出发深度优先遍历
    void dfs(int start) {
        vector<bool> visited(n, false);
        dfsVisit(start, visited);
        cout << endl;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);

    cout << "BFS from 0: ";
    g.bfs(0);

    cout << "DFS from 0: ";
    g.dfs(0);
    return 0;
}

Java

import java.util.*;

public class GraphTraversal {
    private int n;
    private List<List<Integer>> adj;

    public GraphTraversal(int n) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    }

    // 无向图加边 (u,v)
    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    // BFS：借助队列
    public void bfs(int start) {
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            System.out.print(u + " ");
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                }
            }
        }
        System.out.println();
    }

    // DFS：递归
    public void dfs(int start) {
        boolean[] visited = new boolean[n];
        dfsVisit(start, visited);
        System.out.println();
    }

    private void dfsVisit(int u, boolean[] visited) {
        System.out.print(u + " ");
        visited[u] = true;
        for (int v : adj.get(u))
            if (!visited[v])
                dfsVisit(v, visited);
    }

    public static void main(String[] args) {
        GraphTraversal g = new GraphTraversal(5);
        int[][] edges = {{0,1}, {0,2}, {1,3}, {1,4}, {2,4}};
        for (int[] e : edges) g.addEdge(e[0], e[1]);

        System.out.print("BFS from 0: ");
        g.bfs(0);

        System.out.print("DFS from 0: ");
        g.dfs(0);
    }
}

Python

from collections import deque


class Graph:
    """邻接表实现的图（无向）"""

    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]   # 邻接表：每个顶点一个列表

    def add_edge(self, u, v):
        """无向图加边"""
        self.adj[u].append(v)
        self.adj[v].append(u)

    def bfs(self, start):
        """BFS：借助队列"""
        visited = [False] * self.n
        q = deque([start])
        visited[start] = True
        order = []
        while q:
            u = q.popleft()
            order.append(u)
            for v in self.adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)
        return order

    def dfs(self, start):
        """DFS：递归"""
        visited = [False] * self.n
        order = []
        self._dfs(start, visited, order)
        return order

    def _dfs(self, u, visited, order):
        order.append(u)
        visited[u] = True
        for v in self.adj[u]:
            if not visited[v]:
                self._dfs(v, visited, order)


if __name__ == "__main__":
    g = Graph(5)
    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4)]
    for u, v in edges:
        g.add_edge(u, v)

    print("BFS from 0:", g.bfs(0))
    print("DFS from 0:", g.dfs(0))

14.图-存储与遍历.md 12 KB Historik Rå