用c语言实现图的深度优先和广度优先遍历

以下是用C语言实现图的深度优先和广度优先遍历的示例代码：

1. 邻接矩阵的深度优先遍历

#define MAX_VERTEX_NUM 20
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
    int vertex_num, arc_num; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

void DFS(Graph G, int v) {
    visited[v] = 1; // 标记当前顶点已被访问
    printf("%d ", G.vertex[v]); // 输出当前顶点
    for (int i = 0; i < G.vertex_num; i++) {
        if (G.arc[v][i] == 1 && visited[i] == 0) { // 如果当前顶点与顶点i有边且顶点i未被访问
            DFS(G, i); // 递归访问顶点i
        }
    }
}

void DFSTraverse(Graph G) {
    memset(visited, 0, sizeof(visited)); // 初始化visited数组
    for (int i = 0; i < G.vertex_num; i++) {
        if (visited[i] == 0) { // 如果顶点i未被访问
            DFS(G, i); // 从顶点i开始深度优先遍历
        }
    }
}

2. 邻接表的深度优先遍历

#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 存储图中所有顶点及其邻接表
    int vertex_num, arc_num; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

void DFS(Graph G, int v) {
    visited[v] = 1; // 标记当前顶点已被访问
    printf("%d ", G.vertices[v].data); // 输出当前顶点
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) { // 如果顶点p->adjvex未被访问
            DFS(G, p->adjvex); // 递归访问顶点p->adjvex
        }
        p = p->next;
    }
}

void DFSTraverse(Graph G) {
    memset(visited, 0, sizeof(visited)); // 初始化visited数组
    for (int i = 0; i < G.vertex_num; i++) {
        if (visited[i] == 0) { // 如果顶点i未被访问
            DFS(G, i); // 从顶点i开始深度优先遍历
        }
    }
}

3. 邻接矩阵的广度优先遍历

#define MAX_VERTEX_NUM 20
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
    int vertex_num, arc_num; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

void BFS(Graph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列
    visited[v] = 1; // 标记当前顶点已被访问
    printf("%d ", G.vertex[v]); // 输出当前顶点
    queue[rear++] = v; // 将当前顶点入队
    while (front != rear) { // 队列不为空时循环
        int w = queue[front++]; // 取出队头元素
        for (int i = 0; i < G.vertex_num; i++) {
            if (G.arc[w][i] == 1 && visited[i] == 0) { // 如果顶点w与顶点i有边且顶点i未被访问
                visited[i] = 1; // 标记顶点i已被访问
                printf("%d ", G.vertex[i]); // 输出顶点i
                queue[rear++] = i; // 将顶点i入队
            }
        }
    }
}

void BFSTraverse(Graph G) {
    memset(visited, 0, sizeof(visited)); // 初始化visited数组
    for (int i = 0; i < G.vertex_num; i++) {
        if (visited[i] == 0) { // 如果顶点i未被访问
            BFS(G, i); // 从顶点i开始广度优先遍历
        }
    }
}

4. 邻接表的广度优先遍历

#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 存储图中所有顶点及其邻接表
    int vertex_num, arc_num; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

void BFS(Graph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列
    visited[v] = 1; // 标记当前顶点已被访问
    printf("%d ", G.vertices[v].data); // 输出当前顶点
    queue[rear++] = v; // 将当前顶点入队
    while (front != rear) { // 队列不为空时循环
        int w = queue[front++]; // 取出队头元素
        ArcNode *p = G.vertices[w].first;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) { // 如果顶点p->adjvex未被访问
                visited[p->adjvex] = 1; // 标记顶点p->adjvex已被访问
                printf("%d ", G.vertices[p->adjvex].data); // 输出顶点p->adjvex
                queue[rear++] = p->adjvex; // 将顶点p->adjvex入队
            }
            p = p->next;
        }
    }
}

void BFSTraverse(Graph G) {
    memset(visited, 0, sizeof(visited)); // 初始化visited数组
    for (int i = 0; i < G.vertex_num; i++) {
        if (visited[i] == 0) { // 如果顶点i未被访问
            BFS(G, i); // 从顶点i开始广度优先遍历
        }
    }
}