C语言数据结构图如何创建与遍历

图（Graph）是一种非常重要的数据结构，广泛应用于计算机科学中的各个领域，如社交网络、路径规划、网络流等。本文将介绍如何在C语言中创建图数据结构，并实现常见的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）。

1. 图的表示

在C语言中，图可以通过多种方式表示，最常见的有邻接矩阵和邻接表两种方式。

1.1 邻接矩阵

邻接矩阵是一个二维数组，其中matrix[i][j]表示顶点i和顶点j之间是否存在边。对于无向图，邻接矩阵是对称的；对于有向图，则不一定对称。

#define MAX_VERTICES 100

typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

void initGraph(Graph *g, int numVertices) {
    g->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            g->vertices[i][j] = 0;
        }
    }
}

void addEdge(Graph *g, int src, int dest) {
    g->vertices[src][dest] = 1;
    g->vertices[dest][src] = 1; // 对于无向图，需要对称添加
}

1.2 邻接表

邻接表使用链表来表示图的边。每个顶点都有一个链表，链表中存储了与该顶点相连的所有顶点。

#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *adjList[MAX_VERTICES];
    int numVertices;
} Graph;

void initGraph(Graph *g, int numVertices) {
    g->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        g->adjList[i] = NULL;
    }
}

void addEdge(Graph *g, int src, int dest) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;

    // 对于无向图，需要对称添加
    newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = g->adjList[dest];
    g->adjList[dest] = newNode;
}

2. 图的遍历

图的遍历是指从图中的某一顶点出发，访问图中的所有顶点，且每个顶点仅被访问一次。常见的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

2.1 深度优先搜索（DFS）

深度优先搜索是一种递归的遍历算法，它从起始顶点开始，沿着一条路径尽可能深地访问顶点，直到不能再继续为止，然后回溯并继续搜索下一条路径。

void DFS(Graph *g, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("Visited %d\n", vertex);

    for (int i = 0; i < g->numVertices; i++) {
        if (g->vertices[vertex][i] && !visited[i]) {
            DFS(g, i, visited);
        }
    }
}

void DFSTraversal(Graph *g) {
    int visited[MAX_VERTICES] = {0};
    for (int i = 0; i < g->numVertices; i++) {
        if (!visited[i]) {
            DFS(g, i, visited);
        }
    }
}

2.2 广度优先搜索（BFS）

广度优先搜索是一种非递归的遍历算法，它从起始顶点开始，逐层访问与该顶点相邻的顶点，直到所有顶点都被访问。

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

#define MAX_VERTICES 100

typedef struct {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isEmpty(Queue *q) {
    return q->rear == -1;
}

void enqueue(Queue *q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("Queue is full\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

void BFS(Graph *g, int startVertex) {
    Queue q;
    initQueue(&q);
    int visited[MAX_VERTICES] = {0};

    visited[startVertex] = 1;
    enqueue(&q, startVertex);

    while (!isEmpty(&q)) {
        int currentVertex = dequeue(&q);
        printf("Visited %d\n", currentVertex);

        for (int i = 0; i < g->numVertices; i++) {
            if (g->vertices[currentVertex][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

3. 总结

本文介绍了如何在C语言中创建图数据结构，并实现了深度优先搜索（DFS）和广度优先搜索（BFS）两种常见的图遍历算法。图的表示方式有邻接矩阵和邻接表两种，选择哪种方式取决于具体的应用场景和图的稀疏程度。DFS和BFS是图算法的基础，掌握它们对于理解更复杂的图算法非常重要。