c语言对图进行深度优先和广度优先遍历

在 C 语言中，可以使用邻接矩阵或邻接表来表示图。下面给出两种遍历图的方法。

1. 深度优先遍历

深度优先遍历使用栈来实现。具体步骤如下：

1. 从初始节点开始，将其标记为已访问，并将其压入栈中。
2. 从栈中弹出一个节点，访问它的邻居节点。
3. 对于未访问的邻居节点，将其标记为已访问，并将其压入栈中。
4. 重复步骤 2 和 3，直到栈为空。

以下是使用邻接矩阵表示图的深度优先遍历的代码示例：

#define MAX_SIZE 100

int visited[MAX_SIZE];  // 记录节点是否被访问过

void dfs_matrix(int graph[][MAX_SIZE], int n, int start) {
    int stack[MAX_SIZE], top = -1;
    stack[++top] = start;
    visited[start] = 1;
    while (top != -1) {
        int node = stack[top--];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {
                visited[i] = 1;
                stack[++top] = i;
            }
        }
    }
}

以下是使用邻接表表示图的深度优先遍历的代码示例：

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

Node* graph[MAX_SIZE];  // 邻接表

void dfs_list(int start) {
    int stack[MAX_SIZE], top = -1;
    stack[++top] = start;
    visited[start] = 1;
    while (top != -1) {
        int node = stack[top--];
        printf("%d ", node);
        Node* cur = graph[node];
        while (cur) {
            int neighbor = cur->val;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                stack[++top] = neighbor;
            }
            cur = cur->next;
        }
    }
}

2. 广度优先遍历

广度优先遍历使用队列来实现。具体步骤如下：

1. 从初始节点开始，将其标记为已访问，并将其加入队列中。
2. 从队列中取出一个节点，访问它的邻居节点。
3. 对于未访问的邻居节点，将其标记为已访问，并将其加入队列中。
4. 重复步骤 2 和 3，直到队列为空。

以下是使用邻接矩阵表示图的广度优先遍历的代码示例：

void bfs_matrix(int graph[][MAX_SIZE], int n, int start) {
    int queue[MAX_SIZE], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while (front != rear) {
        int node = queue[front++];
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

以下是使用邻接表表示图的广度优先遍历的代码示例：

void bfs_list(int start) {
    int queue[MAX_SIZE], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while (front != rear) {
        int node = queue[front++];
        printf("%d ", node);
        Node* cur = graph[node];
        while (cur) {
            int neighbor = cur->val;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                queue[rear++] = neighbor;
            }
            cur = cur->next;
        }
    }
}