一、图（一）：图的定义与基本术语、存储结构与遍历

图，说实话，是数据结构里最灵活、也最让人头疼的结构之一。树你还能找到"根"，链表你还能找到"头"，图呢？它没有固定的起点，节点之间可以任意连接。我当年第一次接触图的时候，脑子里全是问号——这东西到底怎么存？怎么遍历？别急，今天咱们就把这些事掰扯清楚。

1. 图的定义与基本术语

图，说白了就是一堆顶点和一堆边的集合。用数学语言说：G = (V, E)，V 是顶点集合，E 是边集合。你想想看，社交网络里每个人是一个顶点，好友关系就是一条边。就是这么简单。

但图的世界里，术语不少。我挑几个最常用的，咱们过一遍：

• 有向图 vs 无向图：边有没有方向？有方向的就是有向图，比如微博的关注关系；没方向的就是无向图，比如微信的好友关系。
• 完全图：任意两个顶点之间都有边。无向完全图有 n(n-1)/2 条边，有向完全图有 n(n-1) 条边。嗯，这个公式我建议你记住，笔试常考。
• 度：无向图中，一个顶点的度就是它关联的边数。有向图里分入度和出度，入度是"指向我"的边数，出度是"我指向别人"的边数。
• 路径与回路：从一个顶点到另一个顶点经过的顶点序列叫路径。如果路径的起点和终点是同一个顶点，就叫回路或环。
• 连通图与强连通图：无向图中任意两个顶点都连通，叫连通图。有向图中任意两个顶点都互相可达，叫强连通图。

2. 图的存储结构

图怎么存进计算机？主流就两种方式：邻接矩阵和邻接表。各有各的脾气，咱们一个一个说。

2.1 邻接矩阵

邻接矩阵，就是用二维数组来存图。假设有 n 个顶点，就开一个 n×n 的矩阵。matrix[i][j] = 1 表示顶点 i 到顶点 j 有边，= 0 表示没有边。如果是带权图，就把 1 换成权值。

优点很明显：判断两个顶点之间有没有边，O(1) 时间搞定。缺点也很要命：空间复杂度 O(n²)，对于稀疏图来说，太浪费了。

// 邻接矩阵存储无向图
#define MAX_VERTEX 100

typedef struct {
    int vertex[MAX_VERTEX];      // 顶点数组
    int edge[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
    int vertexNum, edgeNum;      // 顶点数和边数
} MGraph;

// 初始化图
void initGraph(MGraph *G, int n) {
    G->vertexNum = n;
    G->edgeNum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G->edge[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(MGraph *G, int i, int j) {
    G->edge[i][j] = 1;
    G->edge[j][i] = 1;  // 无向图对称
    G->edgeNum++;
}

2.2 邻接表

邻接表，说白了就是"每个顶点挂一个链表"。链表里存的是这个顶点能到达的邻居。对于稀疏图，这玩意省空间省得不是一星半点。

空间复杂度 O(V + E)，V 是顶点数，E 是边数。你想想看，如果图里有 10000 个顶点，但只有 20000 条边，邻接表只需要存 10000 个头指针加 20000 个节点，比邻接矩阵省太多了。

// 邻接表存储无向图
#define MAX_VERTEX 100

// 边节点
typedef struct EdgeNode {
    int adjVertex;              // 邻接顶点下标
    struct EdgeNode *next;      // 下一个边节点
} EdgeNode;

// 顶点节点
typedef struct VertexNode {
    int data;                   // 顶点数据
    EdgeNode *firstEdge;        // 第一条边
} VertexNode, AdjList[MAX_VERTEX];

// 图
typedef struct {
    AdjList vertices;
    int vertexNum, edgeNum;
} ALGraph;

// 添加边
void addEdge(ALGraph *G, int i, int j) {
    // 添加 i->j 的边
    EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = j;
    e->next = G->vertices[i].firstEdge;
    G->vertices[i].firstEdge = e;
    
    // 无向图，再添加 j->i 的边
    e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjVertex = i;
    e->next = G->vertices[j].firstEdge;
    G->vertices[j].firstEdge = e;
    
    G->edgeNum++;
}

3. 图的遍历

图的遍历，说白了就是"怎么把图里的所有顶点都走一遍"。树有前序、中序、后序，图呢？图有深度优先搜索（DFS）和广度优先搜索（BFS）。

3.1 深度优先搜索（DFS）

DFS 的思路很简单：从一个顶点出发，沿着一条路走到黑，走不动了就回头，换条路继续走。说白了就是"不撞南墙不回头"。

实现上，DFS 可以用递归，也可以用栈。我个人更喜欢递归，代码简洁，逻辑清晰。

// DFS 递归实现（邻接矩阵版）
int visited[MAX_VERTEX] = {0};

void DFS(MGraph *G, int v) {
    visited[v] = 1;
    printf("访问顶点: %d\n", v);
    
    for (int w = 0; w < G->vertexNum; w++) {
        if (G->edge[v][w] == 1 && !visited[w]) {
            DFS(G, w);
        }
    }
}

void DFSTraverse(MGraph *G) {
    for (int i = 0; i < G->vertexNum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G->vertexNum; i++) {
        if (!visited[i]) {
            DFS(G, i);  // 处理非连通图
        }
    }
}

3.2 广度优先搜索（BFS）

BFS 的思路是"层层推进"：先访问起点，再访问起点的所有邻居，再访问邻居的邻居……就像水波一样一圈一圈扩散。

实现 BFS 需要用到队列。为什么？因为你要先访问的先处理，后访问的后处理——先进先出，正好是队列的特性。

// BFS 实现（邻接表版）
void BFS(ALGraph *G, int start) {
    int visited[MAX_VERTEX] = {0};
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;
    
    visited[start] = 1;
    printf("访问顶点: %d\n", start);
    queue[rear++] = start;
    
    while (front != rear) {
        int v = queue[front++];
        EdgeNode *p = G->vertices[v].firstEdge;
        
        while (p != NULL) {
            int w = p->adjVertex;
            if (!visited[w]) {
                visited[w] = 1;
                printf("访问顶点: %d\n", w);
                queue[rear++] = w;
            }
            p = p->next;
        }
    }
}

4. 知识体系总览

下面这张图，把本章的核心知识点串起来了。我建议你多看几遍，理清它们之间的关系。

5. 总结

图这一章，说白了就三件事：术语要懂、存储要会选、遍历要能写。邻接矩阵和邻接表各有千秋，DFS 和 BFS 各有用途。我个人建议你先把邻接表的代码多写几遍，因为实际项目中邻接表用得更多。至于遍历，BFS 在求最短路径时特别好用，DFS 在拓扑排序、连通分量检测中很常见。

嗯，今天就到这儿。图的内容不少，但别怕，多画图、多写代码，慢慢就熟了。

---