深搜与广搜的区别、优缺点

深度优先搜索（DFS）和广度优先搜索（BFS）都是图遍历算法，它们在搜索树或图中寻找特定节点或遍历整个树/图。它们的主要区别在于搜索顺序和占用的内存空间。

区别：

1. 搜索顺序不同：DFS 从根节点开始，一直遍历到叶子节点，沿途存下所有经过的节点，而BFS则从根节点开始，先遍历所有与根节点相邻的节点，再遍历与它们相邻的节点，以此类推。

2. 内存占用不同：DFS 会一直深入到最深的节点，需要保存所有经过的节点，因此占用的内存空间相对较小，而BFS 需要保存所有层次的节点，因此占用的内存空间相对较大。

优点：

DFS：

1. 实现简单，容易理解。

2. 占用的内存空间相对较小。

BFS：

1. 可以找到最短路径。

2. 适合用于有多解情况下的最优解问题。

缺点：

DFS：

1. 无法找到最短路径。

2. 可能会陷入死循环。

BFS：

1. 实现相对较为复杂。

2. 占用的内存空间较大。

在实际应用中，我们需要根据具体问题来选择使用 DFS 还是 BFS。如果要求搜索最短路径或找到最优解，则应该使用 BFS；如果要求占用的内存空间较少或实现简单，则应该使用 DFS。

相关问题

c++ 图 深搜 广搜

在提供的AC代码中，有关于图的深度优先搜索(DFS)和广度优先搜索(BFS)的实现方法。
在第一段代码中，是一个关于深度优先搜索的实现。该代码通过递归的方式来实现深度优先搜索。它使用了一个路径数组和一个标记数组来记录路径和访问状态。在每一次递归时，根据条件进行搜索，并在搜索完成后进行回溯操作。最终输出所有路径的结果。

在第二段代码中，是一个关于图的广度优先搜索的实现。该代码使用了一个队列来进行广度优先搜索。它使用了一个二维数组来表示图的状态和一个二维数组来记录访问状态。在搜索时，将起始点入队并标记为已访问，然后通过循环遍历队列中的元素，并根据条件进行搜索，并将符合条件的点入队并标记为已访问。最终返回从入口到出口的路径长度。

因此，根据提供的AC代码，可以实现图的深度优先搜索和广度优先搜索算法。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [【C++】数据结构之深搜+广搜 经典题型](https://blog.csdn.net/weixin_64967734/article/details/124994451)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]

邻接表的深搜广搜c语言

邻接表是一种图的存储结构，它可以用于实现图的深度优先搜索（DFS）和广度优先搜索（BFS）。下面是邻接表的深搜和广搜的C语言实现：

1. 邻接表的深度优先搜索（DFS）C语言实现：

#define MAXNODE 1000
#define MAXSIDE 10000

typedef struct SIDE {
    int tailNode;
    int nextSide;
    int weight;
} SIDE;

SIDE edge[MAXSIDE];
int head[MAXNODE];
int visited[MAXNODE];
int counttEdge = 0;

void CreateABoundary(int headNode, int tailNode, int weight) {
    edge[counttEdge].tailNode = tailNode;
    edge[counttEdge].weight = weight;
    edge[counttEdge].nextSide = head[headNode];
    head[headNode] = counttEdge;
    counttEdge++;
}

void DFS(int node) {
    visited[node] = 1;
    printf("%d ", node);
    for (int i = head[node]; i != -1; i = edge[i].nextSide) {
        int nextNode = edge[i].tailNode;
        if (!visited[nextNode]) {
            DFS(nextNode);
        }
    }
}

int main() {
    // 初始化
    memset(head, -1, sizeof(head));
    memset(visited, 0, sizeof(visited));
    counttEdge = 0;

    // 创建图
    CreateABoundary(1, 2, 0);
    CreateABoundary(1, 3, 0);
    CreateABoundary(2, 4, 0);
    CreateABoundary(2, 5, 0);
    CreateABoundary(3, 6, 0);
    CreateABoundary(3, 7, 0);

    // DFS遍历
    DFS(1);

    return 0;
}

2. 邻接表的广度优先搜索（BFS）C语言实现：

#define MAXNODE 1000
#define MAXSIDE 10000

typedef struct SIDE {
    int tailNode;
    int nextSide;
    int weight;
} SIDE;

SIDE edge[MAXSIDE];
int head[MAXNODE];
int visited[MAXNODE];int counttEdge = 0;

void CreateABoundary(int headNode, int tailNode, int weight) {
    edge[counttEdge].tailNode = tailNode;
    edge[counttEdge].weight = weight;
    edge[counttEdge].nextSide = head[headNode];
    head[headNode] = counttEdge;
    counttEdge++;
}

void BFS(int node) {
    int queue[MAXNODE];
    int front = 0, rear = 0;

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

    while (front < rear) {
        int curNode = queue[front++];
        for (int i = head[curNode]; i != -1; i = edge[i].nextSide) {
            int nextNode = edge[i].tailNode;
            if (!visited[nextNode]) {
                visited[nextNode] = 1;
                printf("%d ", nextNode);
                queue[rear++] = nextNode;
            }
        }
    }
}

int main() {
    // 初始化
    memset(head, -1, sizeof(head));
    memset(visited, 0, sizeof(visited));
    counttEdge = 0;

    // 创建图
    CreateABoundary(1, 2, 0);
    CreateABoundary(1, 3, 0);
    CreateABoundary(2, 4, 0);
    CreateABoundary(2, 5, 0);
    CreateABoundary(3, 6, 0);
    CreateABoundary(3, 7, 0);

    // BFS遍历
    BFS(1);

    return 0;
}