C++语言，利用邻接矩阵创建无向图实现DFS和BFS

下面是基于邻接矩阵实现的DFS和BFS代码：

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

#define MAX_VERTEX_NUM 100

typedef struct Graph {
    int vertex[MAX_VERTEX_NUM];
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num;
    int edge_num;
} Graph;

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

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

// 判断队列是否为空
bool IsQueueEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

// 入队
bool EnQueue(Queue* queue, int x) {
    if ((queue->rear + 1) % MAX_VERTEX_NUM == queue->front) {
        return false;
    }
    queue->data[queue->rear] = x;
    queue->rear = (queue->rear + 1) % MAX_VERTEX_NUM;
    return true;
}

// 出队
bool DeQueue(Queue* queue, int* x) {
    if (IsQueueEmpty(queue)) {
        return false;
    }
    *x = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_VERTEX_NUM;
    return true;
}

// 初始化图
void InitGraph(Graph* graph) {
    int i, j;
    printf("输入顶点数和边数：");
    scanf("%d%d", &graph->vertex_num, &graph->edge_num);
    for (i = 0; i < graph->vertex_num; ++i) {
        printf("输入第%d个顶点的值：", i);
        scanf("%d", &graph->vertex[i]);
    }
    for (i = 0; i < graph->vertex_num; ++i) {
        for (j = 0; j < graph->vertex_num; ++j) {
            graph->matrix[i][j] = 0;
        }
    }
    for (i = 0; i < graph->edge_num; ++i) {
        int v1, v2;
        printf("输入第%d条边的起点和终点：", i);
        scanf("%d%d", &v1, &v2);
        graph->matrix[v1][v2] = 1;
        graph->matrix[v2][v1] = 1;
    }
}

// DFS遍历
void DFS(Graph* graph, bool* visited, int v) {
    int i;
    printf("%d ", graph->vertex[v]);
    visited[v] = true;
    for (i = 0; i < graph->vertex_num; ++i) {
        if (graph->matrix[v][i] == 1 && !visited[i]) {
            DFS(graph, visited, i);
        }
    }
}

// BFS遍历
void BFS(Graph* graph, bool* visited, Queue* queue, int v) {
    int i;
    printf("%d ", graph->vertex[v]);
    visited[v] = true;
    EnQueue(queue, v);
    while (!IsQueueEmpty(queue)) {
        int u;
        DeQueue(queue, &u);
        for (i = 0; i < graph->vertex_num; ++i) {
            if (graph->matrix[u][i] == 1 && !visited[i]) {
                printf("%d ", graph->vertex[i]);
                visited[i] = true;
                EnQueue(queue, i);
            }
        }
    }
}

int main() {
    Graph graph;
    bool visited[MAX_VERTEX_NUM];
    Queue queue;
    int i;
    InitGraph(&graph);
    for (i = 0; i < graph.vertex_num; ++i) {
        visited[i] = false;
    }
    printf("DFS遍历结果：");
    for (i = 0; i < graph.vertex_num; ++i) {
        if (!visited[i]) {
            DFS(&graph, visited, i);
        }
    }
    printf("\n");
    for (i = 0; i < graph.vertex_num; ++i) {
        visited[i] = false;
    }
    InitQueue(&queue);
    printf("BFS遍历结果：");
    for (i = 0; i < graph.vertex_num; ++i) {
        if (!visited[i]) {
            BFS(&graph, visited, &queue, i);
        }
    }
    printf("\n");
    return 0;
}

这里利用邻接矩阵存储图结构，实现了DFS和BFS遍历算法。在程序中，首先通过InitGraph函数读入图的顶点数、边数以及每个顶点的值，然后通过邻接矩阵表示图的连通关系。DFS和BFS遍历时，都需要记录每个节点是否已经被访问过，因此定义了visited数组用于记录。DFS遍历采用递归方式，而BFS遍历则利用队列实现。