c语言深度优先搜索和广度优先搜索

C语言中的深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的图搜索算法。

深度优先搜索通常使用递归的方法实现，其基本思想是从一个起点开始一直向下探索直到不能继续为止，然后回溯到上一个节点，再继续向下探索，直到遍历完整个图。具体实现可以使用栈来保存节点信息，每次取出栈顶节点，访问它的邻居节点，如果邻居节点没有被访问过，则将其入栈，继续往下探索；如果邻居节点已经被访问过，则回溯到上一个节点，继续从栈中取出节点。

广度优先搜索通常使用队列的方法实现，其基本思想是从一个起点开始，先访问与它相邻的节点，再依次访问与这些节点相邻的节点，直到遍历完整个图。具体实现可以使用队列来保存节点信息，每次取出队首节点，访问它的邻居节点，如果邻居节点没有被访问过，则将其入队，继续往下探索；如果邻居节点已经被访问过，则继续从队列中取出下一个节点。

深度优先搜索和广度优先搜索在不同的场景下有不同的应用，深度优先搜索适用于找到任意一条路径，而广度优先搜索适用于找到最短路径或最优解。同时，这两种算法也有各自的优缺点，需要根据具体情况进行选择。

相关问题

用c语言实现深度优先搜索和广度优先搜索

下面是使用C语言实现深度优先搜索和广度优先搜索的示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 图的邻接表存储结构
typedef struct ArcNode {
    int adjvex;            // 该弧所指向的顶点的位置
    struct ArcNode *next;  // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    int data;              // 顶点信息
    ArcNode *first;        // 指向第一条依附该顶点的弧的指针
} VNode;

typedef struct Graph {
    VNode adjList[MAX_VERTEX_NUM]; // 邻接表
    int vexNum, arcNum;             // 图的顶点数和弧数
} Graph;

// 初始化图
void InitGraph(Graph *G, int vexNum) {
    G->vexNum = vexNum;
    G->arcNum = 0;
    for (int i = 0; i < vexNum; i++) {
        G->adjList[i].data = i;
        G->adjList[i].first = NULL;
    }
}

// 添加弧
void AddArc(Graph *G, int from, int to) {
    ArcNode *arc = (ArcNode*)malloc(sizeof(ArcNode));
    arc->adjvex = to;
    arc->next = G->adjList[from].first;
    G->adjList[from].first = arc;
    G->arcNum++;
}

// 深度优先搜索
void DFS(Graph *G, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);

    ArcNode *arc = G->adjList[v].first;
    while (arc != NULL) {
        int w = arc->adjvex;
        if (visited[w] == 0) {
            DFS(G, w, visited);
        }
        arc = arc->next;
    }
}

// 广度优先搜索
void BFS(Graph *G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;

    visited[v] = 1;
    printf("%d ", v);
    queue[rear++] = v;

    while (front < rear) {
        int w = queue[front++];
        ArcNode *arc = G->adjList[w].first;
        while (arc != NULL) {
            int u = arc->adjvex;
            if (visited[u] == 0) {
                visited[u] = 1;
                printf("%d ", u);
                queue[rear++] = u;
            }
            arc = arc->next;
        }
    }
}

int main() {
    Graph G;
    int vexNum = 5;
    InitGraph(&G, vexNum);

    // 添加弧
    AddArc(&G, 0, 1);
    AddArc(&G, 0, 2);
    AddArc(&G, 1, 3);
    AddArc(&G, 1, 4);

    // 深度优先搜索
    int visited[MAX_VERTEX_NUM] = {0};
    printf("DFS: ");
    DFS(&G, 0, visited);
    printf("\n");

    // 广度优先搜索
    for (int i = 0; i < vexNum; i++) {
        visited[i] = 0;
    }
    printf("BFS: ");
    BFS(&G, 0, visited);
    printf("\n");

    return 0;
}

在这个示例代码中，我们使用邻接表来存储图，其中`VNode`表示顶点，`ArcNode`表示弧。`InitGraph`函数用于初始化图，`AddArc`函数用于添加弧。`DFS`函数和`BFS`函数分别表示深度优先搜索和广度优先搜索。在这个示例代码中，我们使用递归来实现深度优先搜索，使用队列来实现广度优先搜索。最后，我们通过调用`DFS`函数和`BFS`函数来进行搜索。

用c语言编写深度优先搜索和广度优先探索的代码

以下是用 C 语言编写深度优先搜索和广度优先探索的示例代码。

深度优先搜索代码：

#include <stdio.h>
#define MAX_VERTICES 50

int visited[MAX_VERTICES];
int adj[MAX_VERTICES][MAX_VERTICES];
int n;

void dfs(int v)
{
    int i;
    visited[v] = 1;
    printf("%d ", v);
    for (i = 0; i < n; i++)
        if (adj[v][i] && !visited[i])
            dfs(i);
}

int main()
{
    int i, j;
    printf("Enter number of vertices:");
    scanf("%d", &n);
    printf("\nEnter adjecency matrix of the graph:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &adj[i][j]);
    for (i = 0; i < n; i++)
        visited[i] = 0;
    printf("Depth First Search Traversal:\n");
    for (i = 0; i < n; i++)
        if (!visited[i])
            dfs(i);
    return 0;
}

广度优先探索代码：

#include <stdio.h>
#define MAX_VERTICES 50

int visited[MAX_VERTICES];
int adj[MAX_VERTICES][MAX_VERTICES];
int queue[MAX_VERTICES];
int front = -1, rear = -1;
int n;

void enqueue(int v)
{
    if (rear == MAX_VERTICES - 1)
        printf("Queue Overflow\n");
    else
    {
        if (front == -1)
            front = 0;
        rear++;
        queue[rear] = v;
    }
}

int dequeue()
{
    int del_item;
    if (front == -1 || front > rear)
    {
        printf("Queue Underflow\n");
        return -1;
    }
    else
    {
        del_item = queue[front];
        front++;
        return del_item;
    }
}

void bfs(int v)
{
    int i, cur_vertex;
    visited[v] = 1;
    printf("%d ", v);
    enqueue(v);
    while (front != -1)
    {
        cur_vertex = dequeue();
        for (i = 0; i < n; i++)
        {
            if (adj[cur_vertex][i] && !visited[i])
            {
                visited[i] = 1;
                printf("%d ", i);
                enqueue(i);
            }
        }
    }
}

int main()
{
    int i, j;
    printf("Enter number of vertices:");
    scanf("%d", &n);
    printf("\nEnter adjecency matrix of the graph:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &adj[i][j]);
    for (i = 0; i < n; i++)
        visited[i] = 0;
    printf("Breadth First Search Traversal:\n");
    for (i = 0; i < n; i++)
        if (!visited[i])
            bfs(i);
    return 0;
}