c语言bfs dfs

C语言中的BFS和DFS是图遍历算法，用于遍历图中的所有节点。其中BFS是广度优先搜索，DFS是深度优先搜索。

BFS算法从起始节点开始，先遍历所有与起始节点相邻的节点，再遍历与这些节点相邻的节点，以此类推，直到遍历完整个图。BFS算法通常使用队列来实现。

DFS算法从起始节点开始，先遍历一个相邻节点，然后再遍历这个节点的相邻节点，以此类推，直到遍历完整个图。DFS算法通常使用递归或栈来实现。

<<引用>>中的代码是用邻接矩阵创建图的代码，而<<引用>>中的代码是用邻接链表创建图的代码。这两种数据结构都可以用于存储图，但它们在实现图遍历算法时的效率有所不同。

相关问题

c语言中dfs和bfs

DFS和BFS是图遍历中两种常见的算法，它们在C语言中的实现如下：

DFS的实现：

#define MAXN 1000
int head[MAXN], ver[MAXN], nxt[MAXN], tot = 1;
bool vis[MAXN];

void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

void dfs(int x) {
    vis[x] = true;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!vis[y]) dfs(y);
    }
}

BFS的实现：

#define MAXN 1000
int head[MAXN], ver[MAXN], nxt[MAXN], tot = 1;
bool vis[MAXN];

void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    vis[x] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (!vis[y]) {
                vis[y] = true;
                q.push(y);
            }
        }
    }
}

其中，DFS使用递归实现，BFS使用队列实现。

c语言邻接矩阵bfs和dfs

以下是C语言中邻接矩阵实现的BFS和DFS算法的示例代码：

BFS算法：

#include <stdio.h>
#include <stdlib.h>
#define MaxInt 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
} AMGraph;

int visited[MVNum];

void BFS(AMGraph G, int v) {
    int queue[MVNum], front = 0, rear = 0;
    int i, j, w;
    printf("%c ", G.vexs[v]);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        i = queue[front++];
        for (j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != MaxInt && !visited[j]) {
                printf("%c ", G.vexs[j]);
                visited[j] = 1;
                queue[rear++] = j;
            }
        }
    }
}

int main() {
    AMGraph G;
    int i, j;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vexs[i]);
    }
    printf("请输入邻接矩阵：");
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            scanf("%d", &G.arcs[i][j]);
            if (G.arcs[i][j] == 0) {
                G.arcs[i][j] = MaxInt;
            }
        }
    }
    printf("请输入遍历起点：");
    int v;
    scanf("%d", &v);
    printf("BFS遍历结果：");
    BFS(G, v);
    return 0;
}

DFS算法：

#include <stdio.h>
#include <stdlib.h>
#define MaxInt 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
} AMGraph;

int visited[MVNum];

void DFS(AMGraph G, int v) {
    int i;
    printf("%c ", G.vexs[v]);
    visited[v] = 1;
    for (i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] != MaxInt && !visited[i]) {
            DFS(G, i);
        }
    }
}

int main() {
    AMGraph G;
    int i, j;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vexs[i]);
    }
    printf("请输入邻接矩阵：");
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            scanf("%d", &G.arcs[i][j]);
            if (G.arcs[i][j] == 0) {
                G.arcs[i][j] = MaxInt;
            }
        }
    }
    printf("请输入遍历起点：");
    int v;
    scanf("%d", &v);
    printf("DFS遍历结果：");
    DFS(G, v);
    return 0;
}