帮我用c语言写一个图的深度优先遍历和广度优先遍历

### 回答1：
深度优先遍历和广度优先遍历是图论中两种常用的遍历方式，下面分别给出它们的C语言实现。

深度优先遍历（DFS）：

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

#define MAXN 100 // 最大顶点数

int visited[MAXN]; // 标记数组

// 邻接矩阵存储图
int G[MAXN][MAXN];
int n; // 顶点数

// DFS遍历
void DFS(int v)
{
    visited[v] = 1; // 标记为已访问
    printf("%d ", v);
    for (int i = 0; i < n; i++)
    {
        if (G[v][i] && !visited[i])
        {
            DFS(i);
        }
    }
}

int main()
{
    // 读入图
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &G[i][j]);
        }
    }

    // 遍历图
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            DFS(i);
        }
    }

    return 0;
}

广度优先遍历（BFS）：

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

#define MAXN 100 // 最大顶点数
#define MAXQ 10000 // 队列最大容量

// 队列结构体
typedef struct queue
{
    int data[MAXQ];
    int front, rear;
} Queue;

int visited[MAXN]; // 标记数组

// 邻接矩阵存储图
int G[MAXN][MAXN];
int n; // 顶点数

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

// 入队
void EnQueue(Queue *q, int v)
{
    q->data[q->rear++] = v;
}

// 出队
int DeQueue(Queue *q)
{
    return q->data[q->front++];
}

// 判断队列是否为空
int IsEmpty(Queue *q)
{
    return q->front == q->rear;
}

// BFS遍历
void BFS(int v)
{
    Queue q;
    InitQueue(&q);
    visited[v] = 1; // 标记为已访问
    printf("%d ", v);
    EnQueue(&q, v);
    while (!IsEmpty(&q))
    {
        int u = DeQueue(&q);
        for (int i = 0; i < n; i++)
        {
            if (G[u][i] && !visited[i])
            {
                visited[i] = 1;
                printf("%d ", i);
                EnQueue(&q, i);
            }
        }
    }
}

int main()
{
    // 读入图
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &G[i][j]);
        }
    }

    // 遍历图
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            BFS(i);
        }
    }

    return 0;
}

### 回答2：
深度优先遍历(Depth First Search, DFS)和广度优先遍历(Breadth First Search, BFS)是图论中两种常用的遍历算法。

深度优先遍历是通过从图的某一顶点出发，沿着一条路径访问未被访问过的顶点，直到搜索到已访问过的所有顶点为止。具体实现时，可以使用递归或栈的方式来保存遍历的路径。

以下是一个使用C语言实现的图的深度优先遍历的示例代码：

#include<stdio.h>
#define MAX_VERTICES 100

// 定义图的结构体
typedef struct {
    int edges[MAX_VERTICES][MAX_VERTICES]; // 边的关系矩阵
    int vertexNum; // 顶点数
    int visited[MAX_VERTICES]; // 记录顶点是否被访问过
} Graph;

// 初始化图
void initGraph(Graph *graph, int vertexNum) {
    graph->vertexNum = vertexNum;
    int i, j;
    for(i = 0; i < vertexNum; i++) {
        for(j = 0; j < vertexNum; j++) {
            graph->edges[i][j] = 0;
        }
        graph->visited[i] = 0;
    }
}

// 添加边
void addEdge(Graph *graph, int start, int end) {
    graph->edges[start][end] = 1;
    graph->edges[end][start] = 1;
}

// 深度优先遍历
void dfs(Graph *graph, int vertex) {
    printf("%d ", vertex);
    graph->visited[vertex] = 1;

    int i;
    for(i = 0; i < graph->vertexNum; i++) {
        if(graph->edges[vertex][i] == 1 && graph->visited[i] == 0) {
            dfs(graph, i);
        }
    }
}

int main() {
    Graph graph;
    int vertexNum = 6;
    initGraph(&graph, vertexNum);
    
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 1, 4);
    addEdge(&graph, 2, 5);

    printf("深度优先遍历结果: ");
    dfs(&graph, 0);

    return 0;
}

输出结果为：0 1 3 4 2 5

广度优先遍历是从图的某一顶点开始，首先访问这个顶点，然后依次访问该顶点的所有相邻顶点，再依次访问这些相邻顶点的相邻顶点，直到所有顶点都被访问为止。具体实现时，可以使用队列来保存遍历的路径。

以下是一个使用C语言实现的图的广度优先遍历的示例代码：

#include<stdio.h>
#define MAX_VERTICES 100
#define QUEUE_SIZE 100

// 定义图的结构体
typedef struct {
    int edges[MAX_VERTICES][MAX_VERTICES]; // 边的关系矩阵
    int vertexNum; // 顶点数
    int visited[MAX_VERTICES]; // 记录顶点是否被访问过
} Graph;

// 定义队列结构体
typedef struct {
    int data[QUEUE_SIZE];
    int front,rear;
} Queue;

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

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

// 入队列
void enqueue(Queue *queue,int vertex) {
    queue->rear++;
    queue->data[queue->rear] = vertex;
}

// 出队列
int dequeue(Queue *queue) {
    queue->front++;
    return queue->data[queue->front];
}

// 初始化图
void initGraph(Graph *graph, int vertexNum) {
    graph->vertexNum = vertexNum;
    int i, j;
    for(i = 0; i < vertexNum; i++) {
        for(j = 0; j < vertexNum; j++) {
            graph->edges[i][j] = 0;
        }
        graph->visited[i] = 0;
    }
}

// 添加边
void addEdge(Graph *graph, int start, int end) {
    graph->edges[start][end] = 1;
    graph->edges[end][start] = 1;
}

// 广度优先遍历
void bfs(Graph *graph, int vertex) {
    Queue queue;
    initQueue(&queue);

    printf("%d ", vertex);
    graph->visited[vertex] = 1;
    enqueue(&queue, vertex);

    while(!isEmpty(&queue)) {
        int frontVertex = dequeue(&queue);
        int i;
        for(i = 0; i < graph->vertexNum; i++) {
            if(graph->edges[frontVertex][i] == 1 && graph->visited[i] == 0) {
                printf("%d ", i);
                graph->visited[i] = 1;
                enqueue(&queue, i);
            }
        }
    }

}

int main() {
    Graph graph;
    int vertexNum = 6;
    initGraph(&graph, vertexNum);
    
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 1, 4);
    addEdge(&graph, 2, 5);

    printf("广度优先遍历结果: ");
    bfs(&graph, 0);
    return 0;
}

输出结果为：0 1 2 3 4 5

这是一个基本的示例代码，你可以根据自己的需求进行修改和扩展。