图的深度优先遍历和宽度优先遍历C语言,图的广度、深度优先遍历 C语言

深度优先遍历：

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

#define MAX_VERTEX_NUM 100 //最大顶点数
#define FALSE 0
#define TRUE 1

typedef struct ArcNode{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;

typedef struct VertexNode{
    int data; //顶点信息
    ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VertexNode;

typedef struct{
    VertexNode vertex[MAX_VERTEX_NUM]; //顶点数组
    int vexnum, arcnum; //图的当前顶点数和弧数
}AdjList;

int visited[MAX_VERTEX_NUM]; //标记数组，用于标记顶点是否已被访问

//创建邻接表
void CreateAdjList(AdjList *G, int *vexs, int vexnum, int arcnum, int (*arcs)[2]){
    G->vexnum = vexnum;
    G->arcnum = arcnum;
    ArcNode *p;
    for(int i = 0; i < G->vexnum; i++){
        G->vertex[i].data = vexs[i];
        G->vertex[i].firstarc = NULL;
    }
    for(int i = 0; i < G->arcnum; i++){
        int from = arcs[i][0];
        int to = arcs[i][1];
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = to;
        p->nextarc = G->vertex[from].firstarc;
        G->vertex[from].firstarc = p;
    }
}

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

int main(){
    int vexs[] = {0, 1, 2, 3, 4, 5}; //顶点数组
    int arcs[][2] = {{0,1},{0,2},{1,3},{1,4},{3,5},{4,5},{5,0}}; //边数组
    int vexnum = 6; //顶点个数
    int arcnum = 7; //边数
    AdjList G;
    CreateAdjList(&G, vexs, vexnum, arcnum, arcs);
    for(int i = 0; i < G.vexnum; i++){
        visited[i] = FALSE;
    }
    printf("DFS: ");
    DFS(G, 0); //从顶点0开始遍历
    printf("\n");
    return 0;
}

宽度优先遍历：

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

#define MAX_VERTEX_NUM 100 //最大顶点数
#define FALSE 0
#define TRUE 1

typedef struct ArcNode{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;

typedef struct VertexNode{
    int data; //顶点信息
    ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VertexNode;

typedef struct{
    VertexNode vertex[MAX_VERTEX_NUM]; //顶点数组
    int vexnum, arcnum; //图的当前顶点数和弧数
}AdjList;

int visited[MAX_VERTEX_NUM]; //标记数组，用于标记顶点是否已被访问

//创建邻接表
void CreateAdjList(AdjList *G, int *vexs, int vexnum, int arcnum, int (*arcs)[2]){
    G->vexnum = vexnum;
    G->arcnum = arcnum;
    ArcNode *p;
    for(int i = 0; i < G->vexnum; i++){
        G->vertex[i].data = vexs[i];
        G->vertex[i].firstarc = NULL;
    }
    for(int i = 0; i < G->arcnum; i++){
        int from = arcs[i][0];
        int to = arcs[i][1];
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = to;
        p->nextarc = G->vertex[from].firstarc;
        G->vertex[from].firstarc = p;
    }
}

//广度优先遍历
void BFS(AdjList G, int v){
    int queue[MAX_VERTEX_NUM]; //定义一个队列
    int front = -1, rear = -1; //队列的头和尾
    visited[v] = TRUE;
    printf("%d ", G.vertex[v].data);
    queue[++rear] = v; //将第一个节点加入队列
    while(front != rear){
        v = queue[++front]; //出队列
        ArcNode *p = G.vertex[v].firstarc;
        while(p != NULL){
            if(visited[p->adjvex] == FALSE){
                visited[p->adjvex] = TRUE;
                printf("%d ", G.vertex[p->adjvex].data);
                queue[++rear] = p->adjvex; //入队列
            }
            p = p->nextarc;
        }
    }
}

int main(){
    int vexs[] = {0, 1, 2, 3, 4, 5}; //顶点数组
    int arcs[][2] = {{0,1},{0,2},{1,3},{1,4},{3,5},{4,5},{5,0}}; //边数组
    int vexnum = 6; //顶点个数
    int arcnum = 7; //边数
    AdjList G;
    CreateAdjList(&G, vexs, vexnum, arcnum, arcs);
    for(int i = 0; i < G.vexnum; i++){
        visited[i] = FALSE;
    }
    printf("BFS: ");
    BFS(G, 0); //从顶点0开始遍历
    printf("\n");
    return 0;
}