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

好的，下面给你提供图结构的深度优先遍历和广度优先遍历的C语言实现代码。

前置条件：假设图的顶点编号从0开始，邻接表的结构体定义如下：

#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef int VertexType; // 顶点数据类型
typedef struct ArcNode { // 边结点
    int adjvex; // 邻接点编号
    struct ArcNode *nextarc; // 下一个邻接点指针
} ArcNode;
typedef struct VNode { // 顶点结点
    VertexType data; // 顶点数据
    ArcNode *firstarc; // 第一个邻接点指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图结构
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

深度优先遍历的C语言实现：

void DFS(ALGraph G, int v, int visited[]) {
    visited[v] = 1; // 标记该节点已被访问
    printf("%d ", v); // 输出该节点的数据
    ArcNode *p = G.vertices[v].firstarc; // 获取该节点的邻接点链表头指针
    while (p) {
        int w = p->adjvex; // 获取邻接点的编号
        if (!visited[w]) { // 如果邻接点未被访问，则递归访问该邻接点
            DFS(G, w, visited);
        }
        p = p->nextarc; // 获取下一个邻接点
    }
}

void DFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点为未访问
    for (int i = 0; i < G.vexnum; i++) { // 遍历所有节点，防止图不连通
        if (!visited[i]) { // 如果该节点未被访问，则从该节点开始进行深度优先遍历
            DFS(G, i, visited);
        }
    }
}

广度优先遍历的C语言实现：

void BFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点为未访问
    Queue *Q = InitQueue(); // 初始化队列
    for (int i = 0; i < G.vexnum; i++) { // 遍历所有节点，防止图不连通
        if (!visited[i]) { // 如果该节点未被访问，则从该节点开始进行广度优先遍历
            visited[i] = 1; // 标记该节点已被访问
            printf("%d ", i); // 输出该节点的数据
            EnQueue(Q, i); // 将该节点入队列
            while (!QueueIsEmpty(Q)) { // 队列非空时循环
                int v = DeQueue(Q); // 取出队头元素
                ArcNode *p = G.vertices[v].firstarc; // 获取该节点的邻接点链表头指针
                while (p) {
                    int w = p->adjvex; // 获取邻接点的编号
                    if (!visited[w]) { // 如果邻接点未被访问，则标记为已访问、输出数据、入队列
                        visited[w] = 1;
                        printf("%d ", w);
                        EnQueue(Q, w);
                    }
                    p = p->nextarc; // 获取下一个邻接点
                }
            }
        }
    }
    DestroyQueue(Q); // 销毁队列
}

其中，队列结构体定义如下：

typedef struct QueueNode { // 队列结点
    int data; // 数据
    struct QueueNode *next; // 下一个结点指针
} QueueNode;
typedef struct Queue { // 队列
    QueueNode *front, *rear; // 队头和队尾指针
} Queue;

Queue *InitQueue() { // 初始化队列
    Queue *Q = (Queue *)malloc(sizeof(Queue));
    Q->front = Q->rear = NULL;
    return Q;
}

int QueueIsEmpty(Queue *Q) { // 判断队列是否为空
    return (Q->front == NULL);
}

void EnQueue(Queue *Q, int data) { // 入队列
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
    p->data = data;
    p->next = NULL;
    if (Q->rear == NULL) {
        Q->front = Q->rear = p;
    } else {
        Q->rear->next = p;
        Q->rear = p;
    }
}

int DeQueue(Queue *Q) { // 出队列
    if (QueueIsEmpty(Q)) {
        return -1;
    }
    QueueNode *p = Q->front;
    int data = p->data;
    Q->front = p->next;
    if (Q->front == NULL) {
        Q->rear = NULL;
    }
    free(p);
    return data;
}

void DestroyQueue(Queue *Q) { // 销毁队列
    while (!QueueIsEmpty(Q)) {
        DeQueue(Q);
    }
    free(Q);
}

希望这段代码能对你有所帮助。