实现图的遍历算法c语言

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

深度优先遍历：

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

typedef struct ArcNode { // 边表结点
    int adjvex; // 邻接点在顶点数组中的下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode { // 顶点表结点
    char data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct { // 图
    AdjList vertices; // 顶点数组
    int vexnum, arcnum; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 访问标记数组

void CreateGraph(Graph *G) { // 创建图
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar(); // 吸收回车符
    printf("请输入顶点信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("第%d个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
        getchar(); // 吸收回车符
    }
    printf("请输入边信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int i, j;
        printf("第%d条边：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar(); // 吸收回车符
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

void DFS(Graph G, int v) { // 深度优先遍历
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);
    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(Graph G) { // 深度优先遍历图
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

int main() {
    Graph G;
    CreateGraph(&G);
    printf("深度优先遍历结果：");
    DFSTraverse(G);
    return 0;
}

广度优先遍历：

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

typedef struct ArcNode { // 边表结点
    int adjvex; // 邻接点在顶点数组中的下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode { // 顶点表结点
    char data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct { // 图
    AdjList vertices; // 顶点数组
    int vexnum, arcnum; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 访问标记数组

typedef struct { // 队列
    int data[MAX_VERTEX_NUM];
    int front, rear;
} Queue;

void InitQueue(Queue *Q) { // 初始化队列
    Q->front = Q->rear = 0;
}

int QueueEmpty(Queue Q) { // 判断队列是否为空
    return Q.front == Q.rear;
}

void EnQueue(Queue *Q, int x) { // 入队
    Q->data[Q->rear++] = x;
}

int DeQueue(Queue *Q) { // 出队
    return Q->data[Q->front++];
}

void CreateGraph(Graph *G) { // 创建图
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar(); // 吸收回车符
    printf("请输入顶点信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("第%d个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
        getchar(); // 吸收回车符
    }
    printf("请输入边信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int i, j;
        printf("第%d条边：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar(); // 吸收回车符
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

void BFS(Graph G, int v) { // 广度优先遍历
    Queue Q;
    InitQueue(&Q);
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);
    EnQueue(&Q, v);
    while (!QueueEmpty(Q)) {
        int u = DeQueue(&Q);
        ArcNode *p = G.vertices[u].firstarc;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                printf("%c ", G.vertices[p->adjvex].data);
                EnQueue(&Q, p->adjvex);
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(Graph G) { // 广度优先遍历图
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i);
        }
    }
}

int main() {
    Graph G;
    CreateGraph(&G);
    printf("广度优先遍历结果：");
    BFSTraverse(G);
    return 0;
}