图基础：图的定义与术语、存储结构与遍历

图，说实话，是数据结构里最灵活、也最让人头疼的一个。树你还能找到根，链表你还能找到头，图呢？图没有固定的起点，也没有固定的终点。我当年第一次接触图的时候，脑子里全是问号——这东西到底怎么存？怎么走？别急，咱们一步步来。

图的定义与基本术语

图，说白了就是一堆顶点和一堆边的集合。用数学话说，叫 G = (V, E)。V 是顶点集，E 是边集。你想想看，社交网络里每个人是一个顶点，好友关系就是一条边。地图上每个城市是一个顶点，高速公路就是边。就这么简单。

但图有几个关键术语，我建议你记牢：

• 有向图 vs 无向图：边有没有方向？有方向就是有向图，比如微博的关注关系。没方向就是无向图，比如微信的好友关系。
• 权值：边上的数值，比如距离、时间、花费。带权值的图叫网。
• 度：顶点关联的边数。有向图里还分入度和出度。
• 路径与回路：从一个顶点到另一个顶点的顶点序列。如果起点和终点相同，就叫回路。
• 连通图与强连通图：无向图中任意两点都连通，叫连通图。有向图中任意两点互相可达，叫强连通图。

图的存储结构

图怎么存进计算机？我做过一个项目，要处理几十万个节点的社交关系图。当时选错了存储方式，内存直接爆了。嗯，这里要注意，选存储结构要看图的密度。

邻接矩阵

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

// 邻接矩阵定义
#define MAX_VERTEX 100

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

邻接矩阵的好处是直观，判断两个顶点是否相连，O(1) 就搞定了。但缺点也很明显——稀疏图太浪费空间。你想想看，一万个顶点，边只有几千条，却要开一亿个元素的矩阵，大部分都是 0。我曾经在一个项目里犯过这个错，内存直接飙到 400MB，后来改成邻接表才降到 20MB。

邻接表

邻接表，说白了就是给每个顶点挂一个链表。链表里存的是这个顶点能到达的所有邻居。这样只存实际存在的边，空间省很多。

// 邻接表定义
typedef struct EdgeNode {
    int adjvex;                // 邻接点下标
    int weight;                // 权值（如果有）
    struct EdgeNode *next;     // 下一个邻接点
} EdgeNode;

typedef struct {
    int data;                  // 顶点信息
    EdgeNode *firstEdge;       // 第一条边
} VertexNode;

typedef struct {
    VertexNode adjList[MAX_VERTEX];
    int vertexNum, edgeNum;
} ALGraph;

邻接表遍历邻居很方便，时间复杂度是 O(邻接边数)。但判断两个顶点是否相连，需要遍历链表，最坏 O(n)。

图的遍历：DFS 与 BFS

图建好了，怎么走？两种经典方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

DFS 的思路很简单：一条路走到黑，走不通了再回头。就像走迷宫，先沿着一条路一直走，遇到死胡同就退回来换一条。我习惯用递归实现，代码很简洁。

// DFS 递归实现
int visited[MAX_VERTEX] = {0};

void DFS(ALGraph *G, int v) {
    visited[v] = 1;
    printf("访问顶点: %d\n", v);
    
    EdgeNode *p = G->adjList[v].firstEdge;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph *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);
        }
    }
}

DFS 的时间复杂度，邻接表是 O(n + e)，邻接矩阵是 O(n²)。空间复杂度 O(n)，主要花在递归栈上。

广度优先搜索（BFS）

BFS 的思路是层层推进。先访问起点，再访问起点的所有邻居，再访问邻居的邻居……就像水波一样一圈圈扩散。BFS 需要借助队列来实现。

// BFS 实现
void BFS(ALGraph *G, int v) {
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;
    
    visited[v] = 1;
    printf("访问顶点: %d\n", v);
    queue[rear++] = v;
    
    while (front != rear) {
        int u = queue[front++];
        EdgeNode *p = G->adjList[u].firstEdge;
        
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                printf("访问顶点: %d\n", p->adjvex);
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

BFS 的时间复杂度和 DFS 一样，但空间复杂度最坏 O(n)，因为队列里最多存所有顶点。

知识体系总览

下面这张图，是我梳理的本章知识结构。你对照着看，心里就有谱了。

图这块，说白了就是三个问题：图长什么样（定义）、怎么存（存储结构）、怎么走（遍历）。你把这三点吃透了，后面学最短路径、最小生成树、拓扑排序，都会轻松很多。

---

公众号:蓝海资料掘金营，微信deep3321