用c++写一个图的深度优先搜索代码并附上注释

### 回答1：

用C写一个图的深度优先搜索代码如下： // 定义图的节点数量
#define MAXV 1000
// 定义队列的最大节点数量
#define MAXQUEUE 500 // 定义图的节点数据结构
typedef struct node{
int v;
struct node *next;
}Node; // 定义图的结构
typedef struct{
Node *vertices[MAXV+1];
int nvertices;
int visited[MAXV+1];
}Graph; // 定义队列
typedef struct {
int data[MAXQUEUE];
int front;
int rear;
}Queue; // 初始化图
void initialize_graph(Graph *g, int n){
int i;
g->nvertices = n;
for (i = 1; i <= n; i++) {
g->vertices[i] = NULL;
g->visited[i] = 0;
}
} // 添加边
void insert_edge(Graph *g, int x, int y, int directed){
Node *p;
p = malloc(sizeof(Node));
p->v = y;
p->next = g->vertices[x];
g->vertices[x] = p;
if (directed == 0)
insert_edge(g,y,x,1);
} // 初始化队列
void initialize_queue(Queue *q){
q->front = 0;
q->rear = 0;
} // 入队
void enqueue(Queue *q, int x){
q->data[q->rear++] = x;
} // 出队
int dequeue(Queue *q){
int x;
x = q->data[q->front++];
return x;
} // 判断队列是否为空
int empty(Queue *q){
if (q->front == q->rear)
return 1;
else
return 0;
} // 深度优先搜索
void DFS(Graph *g, int start){
Node *p;
printf("%d ", start);
g->visited[start] = 1;
p = g->vertices[start];
while(p != NULL){
if(g->visited[p->v] == 0)
DFS(g, p->v);
p = p->next;
}
} // 广度优先搜索
void BFS(Graph *g, int start){
Queue q;
Node *p;
int v;

initialize_queue(&q);
enqueue(&q, start);
g->visited[start] = 1;
while(!empty(&q)){
v = dequeue(&q);
printf("%d ", v);
p = g->vertices[v];
while(p != NULL){
if (g->visited[p->v] == 0) {
enqueue(&q, p->v);
g->visited[p->v] = 1;
}
p = p->next;
}
}
}

### 回答2：
深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索图的算法。下面是用C语言编写的图的深度优先搜索代码，并附上注释：

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

#define MAX_VERTICES 100   // 图中最大顶点数

// 图的顶点结构体
typedef struct {
    bool visited;  // 顶点是否已被访问
} Vertex;

// 图的结构体
typedef struct {
    int matrix[MAX_VERTICES][MAX_VERTICES];  // 二维矩阵表示图的连接情况
    Vertex vertices[MAX_VERTICES];   // 顶点数组
    int numVertices;   // 顶点数
} Graph;

// 深度优先搜索函数
void DFS(Graph* graph, int vertexIndex) {
    Vertex* vertex = &(graph->vertices[vertexIndex]);   // 获取当前顶点
    vertex->visited = true;    // 标记当前顶点为已访问
    printf("Visited vertex: %d\n", vertexIndex);   // 访问当前顶点

    // 遍历当前顶点的邻接顶点
    for (int i = 0; i < graph->numVertices; i++) {
        // 如果邻接顶点未被访问且与当前顶点相连，则继续深度优先搜索
        if (!graph->vertices[i].visited && graph->matrix[vertexIndex][i] == 1) {
            DFS(graph, i);
        }
    }
}

int main() {
    Graph graph;
    // 初始化图的顶点数
    graph.numVertices = 6;

    // 初始化图的连接情况
    int matrix[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0, 0},  // 0与1、2顶点相连
        {1, 0, 0, 1, 1, 0},  // 1与0、3、4顶点相连
        {1, 0, 0, 0, 0, 1},  // 2与0、5顶点相连
        {0, 1, 0, 0, 0, 0},  // 3与1顶点相连
        {0, 1, 0, 0, 0, 0},  // 4与1顶点相连
        {0, 0, 1, 0, 0, 0}   // 5与2顶点相连
    };
    for (int i = 0; i < graph.numVertices; i++) {
        for (int j = 0; j < graph.numVertices; j++) {
            graph.matrix[i][j] = matrix[i][j];
        }
    }

    // 初始化顶点的访问情况
    for (int i = 0; i < graph.numVertices; i++) {
        graph.vertices[i].visited = false;
    }

    // 从顶点0开始进行深度优先搜索
    DFS(&graph, 0);
    
    return 0;
}

该代码实现了一个图的深度优先搜索算法。在代码中，我们通过一个矩阵表示图的连接情况，并通过一个顶点数组记录每个顶点是否已被访问。通过递归调用`DFS`函数，我们从指定的起始顶点开始进行深度优先搜索，将已访问的顶点标记为`visited`，并输出当前访问的顶点。然后遍历与当前顶点相连的邻接顶点，选择未被访问且与当前顶点相连的邻接顶点继续进行深度优先搜索，直到所有顶点被访问完毕为止。最后，我们以顶点0作为起始点进行测试。

### 回答3：
下面是一个用C语言编写的图的深度优先搜索代码，附有注释说明每一步的功能和原理。

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

// 定义最大顶点的个数
#define MAX_VERTEX 100

// 定义图的结构体
typedef struct {
    int vertices[MAX_VERTEX];     // 顶点数组
    int adjacency_matrix[MAX_VERTEX][MAX_VERTEX];   // 邻接矩阵
    int num_vertices;    // 图中顶点的个数
} Graph;

// 初始化图
void initGraph(Graph* graph) {
    int i, j;
    graph->num_vertices = 0;

    // 将邻接矩阵中所有元素初始化为0，表示没有边
    for (i = 0; i < MAX_VERTEX; i++) {
        for (j = 0; j < MAX_VERTEX; j++) {
            graph->adjacency_matrix[i][j] = 0;
        }
    }
}

// 添加顶点
void addVertex(Graph* graph, int vertex) {
    graph->vertices[graph->num_vertices] = vertex;
    graph->num_vertices++;
}

// 添加边
void addEdge(Graph* graph, int vertex1, int vertex2) {
    graph->adjacency_matrix[vertex1][vertex2] = 1;
    graph->adjacency_matrix[vertex2][vertex1] = 1;
}

// 深度优先搜索
void depthFirstSearch(Graph* graph, int visited[], int vertex) {
    int i;
    printf("%d ", graph->vertices[vertex]);

    // 将该顶点设为已访问
    visited[vertex] = 1;

    // 遍历与当前顶点相邻的所有顶点
    for (i = 0; i < graph->num_vertices; i++) {
        // 如果相邻顶点未被访问且存在边，则递归访问
        if (graph->adjacency_matrix[vertex][i] == 1 && visited[i] == 0) {
            depthFirstSearch(graph, visited, i);
        }
    }
}

int main() {
    Graph graph;
    int visited[MAX_VERTEX] = { 0 };   // 标记顶点是否已被访问

    initGraph(&graph);

    // 添加顶点
    addVertex(&graph, 1);
    addVertex(&graph, 2);
    addVertex(&graph, 3);
    addVertex(&graph, 4);
    addVertex(&graph, 5);

    // 添加边
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 1, 4);

    printf("深度优先搜索结果：");
    depthFirstSearch(&graph, visited, 0);

    return 0;
}

本代码实现了一个图的深度优先搜索算法。首先，通过初始化函数`initGraph`初始化一个空的图。然后通过`addVertex`函数逐个添加顶点，并通过`addEdge`函数添加边。在`main`函数中定义了一个`visited`数组来标记顶点是否已被访问。最后，调用`depthFirstSearch`函数进行深度优先搜索，从指定的顶点开始遍历。在每次递归调用`depthFirstSearch`函数时，先输出当前访问的顶点，然后将当前顶点标记为已访问，再递归地访问与当前顶点相邻且未被访问的顶点。最终输出的结果即为深度优先搜索的遍历序列。