深度优先遍历和广度优先遍历有向邻接表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 {
    int data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        int i, j;
        printf("请输入边(vi, vj)的顶点序号：");
        scanf("%d%d", &i, &j);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

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

void DFSTraverse(ALGraph *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() {
    ALGraph G;
    CreateGraph(&G);
    printf("深度优先遍历结果为：");
    DFSTraverse(&G);
    return 0;
}

广度优先遍历：

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

#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_SIZE 20

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

typedef struct {
    int data[MAX_QUEUE_SIZE];
    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(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        int i, j;
        printf("请输入边(vi, vj)的顶点序号：");
        scanf("%d%d", &i, &j);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

void BFS(ALGraph *G, int v) {
    Queue Q;
    InitQueue(&Q);
    visited[v] = 1;
    printf("%d ", G->vertices[v].data);
    EnQueue(&Q, v);
    while (!QueueEmpty(&Q)) {
        int u = DeQueue(&Q);
        ArcNode *p = G->vertices[u].firstarc;
        while (p) {
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = 1;
                printf("%d ", G->vertices[w].data);
                EnQueue(&Q, w);
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(ALGraph *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() {
    ALGraph G;
    CreateGraph(&G);
    printf("广度优先遍历结果为：");
    BFSTraverse(&G);
    return 0;
}