Skip to main content

第59章 图的定义及基本图论算法

图是一种比线性表和树更复杂的非线性数据结构，它由顶点和边组成，能够描述多对多的复杂关系，在社交网络、路线规划、电路设计等领域有广泛应用。图的遍历是指从图中某一顶点出发，按照一定规则访问图中所有顶点且每个顶点仅被访问一次的过程，是图论中的基础操作。

59.1 图的定义​

在数学中，图通常表示为 G=(V,E)G=(V, E)，其中VV表示顶点集，EE表示边集。顶点集是一个非空的有限集合，每个元素称为顶点（或节点）；边集是由顶点之间的连接关系构成的集合，每条边表示两个顶点之间的关联。

59.2 图的种类​

59.2.1 无向图​

无向图中，边是无方向的，连接顶点 uu 和 vv 的边写作 (u,v)(u, v)，(u,v)(u, v) 与 (v,u)(v, u) 代表同一条边。 示例：社交好友关系，互为朋友，属于无向关联。

59.2.2 有向图​

有向图的边带有方向，从uu指向vv的有向边记作 <u,v><u, v>，uu为起点，vv为终点。 示例：网页超链接，A链接B不代表B链接A。

59.3 图节点的度的概念​

59.3.1 无向图的度​

顶点的度deg(v)deg(v)：与该顶点相连的边总数。 性质：无向图所有顶点度数之和等于边数的两倍。

59.3.2 有向图的度​

  • 入度inDegree(v)inDegree(v)：以该点为终点的有向边数量
  • 出度outDegree(v)outDegree(v)：以该点为起点的有向边数量
  • 总度：deg(v)exp=inDegree(v)+outDegree(v)deg(v)exp= inDegree (v)+ outDegree (v) 性质：所有顶点入度总和 = 所有顶点出度总和 = 图的总边数。

59.4 图的数据结构表示​

59.4.1 邻接矩阵​

使用二维数组 graph[n][n]graph[n][n] 存储图，nn 为顶点总数。 无向图：graph[i][j]exp=graph[j][i]graph[i][j]exp = graph[j][i]； 有向图：仅<i,j><i,j>存在时graph[i][j]graph[i][j]标记为1/权重。 优点：两点是否有边查询O(1)O(1)； 缺点：稀疏图空间浪费严重，空间复杂度 O(n2)O(n^2)。

#include <stdio.h>
#define MAX_VERTEX 5

// 初始化无向图邻接矩阵
void InitUndirectedGraph(int graph[MAX_VERTEX][MAX_VERTEX]) {
    for (int i = 0; i < MAX_VERTEX; i++) {
        for (int j = 0; j < MAX_VERTEX; j++) {
            expgraph[i][j]exp = 0;
        }
    }
    // 添加无向边
    graph[0][1] = 1; graph[1][0] = 1;
    graph[0][2] = 1; graph[2][0] = 1;
    graph[1][3] = 1; graph[3][1] = 1;
    graph[1][4] = 1; graph[4][1] = 1;
    graph[2][4] = 1; graph[4][2] = 1;
}

int main(){
    int graph[MAX_VERTEX][MAX_VERTEX];
    InitUndirectedGraph(graph);
    printf("无向图邻接矩阵:\n");
    for (int i = 0; i < MAX_VERTEX; i++) {
        for (int j = 0; j < MAX_VERTEX; j++) {
            printf("%d ", graph[i]);
        }
        printf("\n");
    }
    return 0;
}

59.4.2 邻接表​

数组+链表组合存储：数组下标代表顶点，每个顶点挂载一条链表存储相邻顶点。 无向图：每条边存两次；有向图仅起点链表存储。 优点：稀疏图节省空间，空间复杂度 O(n+e)O(n+e)； 缺点：查询两点连边需要遍历链表，效率偏低。

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

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 邻表头结点
typedef struct AdjList {
    Node* head;
} AdjList;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjList* adjLists;
} Graph;

// 创建链表节点
Node* createNode(int v){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建空图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph *)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (AdjList*) malloc(vertices * sizeof(AdjList));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i].head = NULL;
    }
    return graph;
}

// 添加无向边
void addUndirectedEdge(Graph* graph, int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = graph->adjLists[u].head;
    graph->adjLists[u].head = newNode;

    newNode = createNode(u);
    newNode->next = graph->adjLists[v].head;
    graph->adjLists[v].head = newNode;
}

// 打印邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        printf("顶点%d的邻接表: ",v);
        Node* temp = graph->adjLists[v].head;
        while (temp){
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main(){
    Graph* graph = createGraph(5);
    addUndirectedEdge(graph, 0, 1);
    addUndirectedEdge(graph, 0, 2);
    addUndirectedEdge(graph, 1, 3);
    addUndirectedEdge(graph, 1, 4);
    addUndirectedEdge(graph, 2, 4);
    printGraph(graph);
    return 0;
}

59.5 深度优先搜索 DFS​

59.5.1 遍历逻辑​

从起点出发，尽可能向深处遍历，遇到未访问邻点递归；无路可走则回溯，使用数组标记访问过的顶点，防止环路重复访问。

59.5.2 递归实现​

void DFSRecursive(int v, int visited[], Graph* graph) {
    visited[v] = 1;
    printf("%d ",v);
    Node* temp = graph->adjLists[v].head;
    while (temp){
        int u = temp->vertex;
        if (!visited[u]){
            DFSRecursive(u, visited, graph);
        }
        temp = temp->next;
    }
}

59.5.3 非递归（栈）实现​

void DFSNonRecursive(int start, Graph* graph) {
    int numVertices = graph->numVertices;
    int visited[numVertices];
    for (int i = 0; i < numVertices; i++){
        visited[i] = 0;
    }
    int stack[numVertices];
    int top = -1;
    visited[start] = 1;
    stack[++top] = start;
    printf("DFS非递归遍历顺序:");
    while (top != -1){
        int v = stack[top--];
        printf("%d ",v);
        Node* temp = graph->adjLists[v].head;
        int tempStack[numVertices];
        int tempTop = -1;
        while (temp){
            int u = temp->vertex;
            if (!visited[u]){
                visited[u] = 1;
                tempStack[++tempTop] = u;
            }
            temp = temp->next;
        }
        while(tempTop != -1){
            stack[++top] = tempStack[tempTop--];
        }
    }
    printf("\n");
}

59.5.4 适用场景​

环检测、拓扑排序、连通块计数；无法求无权图最短路径。

59.6 广度优先搜索 BFS​

59.6.1 遍历逻辑​

逐层遍历，使用队列存储待访问顶点，标记访问状态，同一层全部访问完毕再进入下一层。

59.6.2 代码实现​

void BFS(int start, Graph* graph) {
    int numVertices = graph->numVertices;
    int visited[numVertices];
    for (int i = 0; i < numVertices; i++){
        visited[i] = 0;
    }
    int queue[numVertices];
    int front = 0, rear = 0;
    visited[start] = 1;
    queue[rear++] = start;
    printf("BFS遍历顺序:");
    while (front < rear){
        int v = queue[front++];
        printf("%d ",v);
        Node* temp = graph->adjLists[v].head;
        while (temp){
            int u = temp->vertex;
            if (!visited[u]){
                visited[u] = 1;
                queue[rear++] = u;
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

59.6.3 适用场景​

无权图最短路径、连通区域统计、层级遍历。

59.7 泛洪填充 Flood Fill​

泛洪填充是图遍历在二维网格的应用，网格单元格为顶点，上下左右相邻单元格为边，常用于图像填充、迷宫遍历。

59.7.1 DFS实现​

#include <stdio.h>
#define ROW 4
#define COL 5

void floodFillDFS(int grid[ROW][COL], int x, int y, int oldColor, int newColor) {
    if(x < 0 || x >= ROW || y < 0 || y >= COL)
        return;
    if(grid[x][y] != oldColor){
        return;
    }
    grid[x][y] = newColor;
    floodFillDFS(grid, x-1, y, oldColor, newColor);
    floodFillDFS(grid, x+1, y, oldColor);
    floodFillDFS(grid, x, y+1, oldColor, newColor);
    floodFillDFS(grid, x, y-1, oldColor, newColor);
}

void printGrid(int grid[ROW][COL]){
    for (int i = 0; i < ROW; i++){
        for (int j = 0; j < COL; j++){
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
}

int main(){
    int grid[ROW][COL]={
        {1,1,0,0,0},
        {1,0,1,1,0},
        {1,0,0,1,0},
        {0,0,0,0,0}
    };
    printf("填充前网格:\n");
    printGrid(grid);
    floodFillDFS(grid, 0, 0, 1, 2);
    printf("填充后网格:\n");
    printGrid(grid);
    return 0;
}

59.7.2 BFS实现​

#include <stdio.h>
#define ROW 4
#define COL 5

typedef struct Point{
    int x;
    int y;
} Point;

void floodFillBFS(int grid[ROW][COL], int startX, int startY, int oldColor, int newColor){
    if (startX <0 || startX >= ROW || startY <0 || startY >= COL)
        return;
    if (grid[startX][startY] != oldColor)
        return;
    Point queue[ROW*COL];
    int front = 0, rear = 0;
    queue[rear++] = {startX, startY};
    grid[startX][startY] = newColor;
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    while (front < rear){
        Point current = queue[front++];
        for(int i=0;i<4;i++){
            int x = current.x + dirs[i][0];
            int y = current.y + dirs[i][1];
            if(x>=0 && x<ROW && y>=0 && y<COL && grid[x][y]==oldColor){
                grid[x][y] = newColor;
                queue[rear++] = {x,y};
            }
        }
    }
}

59.7.3 优缺点对比​

  • DFS：代码简洁，递归深度过大会栈溢出；
  • BFS：无栈溢出风险，适合大规模网格，代码更长。

59.7.4 应用​

画图软件油漆桶、迷宫寻路、地图连通区域统计。