六讲贯通C++图的应用之二 DFS和BFS("C++图应用六讲之二：深度优先搜索DFS与广度优先搜索BFS详解")

原创

ithorizon 6个月前 (10-19) 阅读数 42 #后端开发

C++图应用六讲之二：深度优先搜索DFS与广度优先搜索BFS详解

一、引言

在C++中，图是一种常见的数据结构，它广泛应用于各种算法和实际问题中。图的遍历是图论中的一个基本问题，其中包括深度优先搜索（DFS）和广度优先搜索（BFS）两种算法。本文将详细介绍这两种算法的原理、实现和应用。

二、图的即

在C++中，图通常使用邻接表或邻接矩阵来即。以下是使用邻接表即图的代码示例：


#include 
#include 
#include 
using namespace std;
class Graph {
private:
    int numVertices; // 顶点数量
    list *adjLists; // 邻接表
public:
    Graph(int vertices) {
        numVertices = vertices;
        adjLists = new list[vertices];
    }
    void addEdge(int src, int dest) {
        adjLists[src].push_back(dest);
        adjLists[dest].push_back(src); // 无向图
    }
    // ... 其他成员函数
};

三、深度优先搜索（DFS）

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。DFS从图的某个顶点起始，沿着路径深入直到该路径的末端，然后回溯，继续深入其他路径。

3.1 DFS的实现

以下是使用递归实现的DFS算法的代码：


void DFS(Graph *graph, int vertex, bool visited[]) {
    visited[vertex] = true;
    cout << vertex << " ";
    for (int adjVertex : graph->adjLists[vertex]) {
        if (!visited[adjVertex]) {
            DFS(graph, adjVertex, visited);
        }
    }
}
void DFS(Graph *graph) {
    bool visited[graph->numVertices];
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

3.2 DFS的应用

DFS算法可以应用于多种场景，如路径查找、拓扑排序、连通性问题等。以下是DFS算法的一些应用实例：

路径查找：找到从起始顶点到目标顶点的路径。

拓扑排序：对有向无环图进行排序，常用于课程安排问题。

连通性问题：判断图中两个顶点是否连通。

四、广度优先搜索（BFS）

广度优先搜索（BFS）是另一种图遍历算法，它从图的某个顶点起始，沿着路径遍历所有邻接点，然后再深入到下一层邻接点。

4.1 BFS的实现

以下是使用队列实现的BFS算法的代码：


#include 
void BFS(Graph *graph, int startVertex) {
    bool visited[graph->numVertices];
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }
    queue queue;
    visited[startVertex] = true;
    queue.push(startVertex);
    while (!queue.empty()) {
        int currentVertex = queue.front();
        cout << currentVertex << " ";
        queue.pop();
        for (int adjVertex : graph->adjLists[currentVertex]) {
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                queue.push(adjVertex);
            }
        }
    }
}