图的DFS队列模板邻接矩阵c++实现

以下是使用邻接矩阵实现图的DFS遍历的队列模板，使用C语言编写：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int data[MAX_VERTEX_NUM];
    int front;
    int rear;
} Queue;

void init(Queue *q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

bool isFull(Queue *q) {
    return (q->rear + 1) % MAX_VERTEX_NUM == q->front;
}

bool enqueue(Queue *q, int x) {
    if (isFull(q)) {
        return false;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_VERTEX_NUM;
    return true;
}

bool dequeue(Queue *q, int *x) {
    if (isEmpty(q)) {
        return false;
    }
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAX_VERTEX_NUM;
    return true;
}

typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertexNum, edgeNum; // 顶点数和边数
} Graph;

void initGraph(Graph *g, int vertexNum) {
    g->vertexNum = vertexNum;
    g->edgeNum = 0;
    for (int i = 0; i < vertexNum; ++i) {
        for (int j = 0; j < vertexNum; ++j) {
            g->edge[i][j] = 0;
        }
    }
}

void addEdge(Graph *g, int u, int v) {
    g->edge[u][v] = 1;
    g->edgeNum++;
}

void dfs(Graph *g, int v, bool *visited) {
    visited[v] = true;
    printf("%d ", g->vertex[v]);
    for (int i = 0; i < g->vertexNum; ++i) {
        if (g->edge[v][i] == 1 && !visited[i]) {
            dfs(g, i, visited);
        }
    }
}

void bfs(Graph *g, int v, bool *visited) {
    Queue q;
    init(&q);
    visited[v] = true;
    enqueue(&q, v);
    while (!isEmpty(&q)) {
        dequeue(&q, &v);
        printf("%d ", g->vertex[v]);
        for (int i = 0; i < g->vertexNum; ++i) {
            if (g->edge[v][i] == 1 && !visited[i]) {
                visited[i] = true;
                enqueue(&q, i);
            }
        }
    }
}

int main() {
    int vertexNum = 5;
    Graph g;
    initGraph(&g, vertexNum);
    for (int i = 0; i < vertexNum; ++i) {
        g.vertex[i] = i;
    }
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 2, 0);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 3);

    bool visited[MAX_VERTEX_NUM] = {false};
    printf("DFS: ");
    for (int i = 0; i < vertexNum; ++i) {
        if (!visited[i]) {
            dfs(&g, i, visited);
        }
    }
    printf("\n");

    for (int i = 0; i < vertexNum; ++i) {
        visited[i] = false;
    }
    printf("BFS: ");
    for (int i = 0; i < vertexNum; ++i) {
        if (!visited[i]) {
            bfs(&g, i, visited);
        }
    }
    printf("\n");

    return 0;
}

其中，`Queue`结构体表示队列，使用循环队列实现。`Graph`结构体表示图，使用邻接矩阵实现。`initGraph`函数用于初始化图，`addEdge`函数用于添加边。`dfs`函数和`bfs`函数分别表示深度优先遍历和广度优先遍历，其中`bfs`函数使用队列实现。