C语言数据结构与算法中怎样完成图的遍历

# C语言数据结构与算法中怎样完成图的遍历

## 一、图的基本概念与存储结构

### 1.1 图的定义与基本术语
图(Graph)是由顶点集合(Vertex)和边集合(Edge)组成的数据结构，记作G=(V,E)。根据边是否有方向可分为：
- **有向图**：边有方向性，用<u,v>表示
- **无向图**：边无方向性，用(u,v)表示

常见术语包括：
- 度（Degree）：与顶点关联的边数
- 路径：顶点序列v1,v2,...,vn
- 连通图：任意两顶点间都有路径

### 1.2 图的常见存储方式

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

邻接表

typedef struct ArcNode { // 边结点
    int adjvex; // 邻接点下标
    struct ArcNode *next; // 下一条边
} ArcNode;

typedef struct VNode { // 顶点结点
    int data; // 顶点信息
    ArcNode *first; // 第一条边
} VNode, AdjList[MAX_VERTEX];

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

二、深度优先搜索(DFS)遍历

2.1 DFS算法原理

深度优先搜索采用回溯算法思想，沿着图的深度遍历顶点： 1. 访问起始顶点v 2. 选择一个与v相邻且未被访问的顶点w 3. 递归访问w 4. 当没有未访问的相邻顶点时回溯

2.2 DFS实现代码

邻接矩阵实现

int visited[MAX_VERTEX] = {0};

void DFS(MGraph G, int v) {
    printf("%d ", G.vertex[v]);
    visited[v] = 1;
    for(int i = 0; i < G.vertexNum; i++) {
        if(G.edge[v][i] && !visited[i]) {
            DFS(G, i);
        }
    }
}

邻接表实现

void DFS(ALGraph G, int v) {
    printf("%d ", G.vertices[v].data);
    visited[v] = 1;
    ArcNode *p = G.vertices[v].first;
    while(p) {
        if(!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

2.3 时间复杂度分析

• 邻接矩阵：O(V²)
• 邻接表：O(V+E)

三、广度优先搜索(BFS)遍历

3.1 BFS算法原理

广度优先搜索采用分层搜索策略： 1. 访问起始顶点v 2. 依次访问v的所有未访问邻接点 3. 按访问顺序对每个邻接点重复步骤2

3.2 BFS实现代码

邻接矩阵实现

void BFS(MGraph G, int v) {
    int queue[MAX_VERTEX], front = 0, rear = 0;
    printf("%d ", G.vertex[v]);
    visited[v] = 1;
    queue[rear++] = v;
    
    while(front != rear) {
        int cur = queue[front++];
        for(int i = 0; i < G.vertexNum; i++) {
            if(G.edge[cur][i] && !visited[i]) {
                printf("%d ", G.vertex[i]);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

邻接表实现

void BFS(ALGraph G, int v) {
    int queue[MAX_VERTEX], front = 0, rear = 0;
    printf("%d ", G.vertices[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    
    while(front != rear) {
        int cur = queue[front++];
        ArcNode *p = G.vertices[cur].first;
        while(p) {
            if(!visited[p->adjvex]) {
                printf("%d ", G.vertices[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

3.3 时间复杂度分析

• 邻接矩阵：O(V²)
• 邻接表：O(V+E)

四、遍历算法的应用实例

4.1 连通分量检测

void Components(ALGraph G) {
    for(int i = 0; i < G.vertexNum; i++) {
        if(!visited[i]) {
            DFS(G, i); // 或BFS
            printf("\n"); // 输出一个连通分量
        }
    }
}

4.2 最短路径问题（无权图）

void ShortestPath(ALGraph G, int v) {
    int dist[MAX_VERTEX] = {0};
    int queue[MAX_VERTEX], front = 0, rear = 0;
    
    for(int i = 0; i < G.vertexNum; i++) {
        dist[i] = -1; // 初始化距离
    }
    
    dist[v] = 0;
    queue[rear++] = v;
    
    while(front != rear) {
        int cur = queue[front++];
        ArcNode *p = G.vertices[cur].first;
        while(p) {
            if(dist[p->adjvex] == -1) {
                dist[p->adjvex] = dist[cur] + 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

五、性能比较与选择建议

实际选择建议： 1. 需要寻找最短路径时优先选择BFS 2. 检测环路或进行拓扑排序时使用DFS 3. 稠密图建议使用邻接矩阵 4. 稀疏图建议使用邻接表

六、总结

图的遍历是图算法的基础，DFS和BFS分别体现了深度优先和广度优先的不同策略。实际应用中应根据具体问题特点选择合适的遍历方法，并结合适当的存储结构以获得最佳性能。 “`