vector dfs bfs 邻接表

Vector和邻接表都是图数据结构中常用的概念，而DFS（深度优先搜索）和BFS（广度优先搜索）则是用于遍历这些图的算法。

1. Vector：在编程语言中，如C++或Python，`vector`通常是一个动态数组，它可以存储同类型的元素，并提供方便的随机访问功能。在表示图时，我们可以使用向量来存储每条边的连接点，即从一个顶点到另一个顶点的关系。

2. 邻接表：这是一种图的存储结构，它将每个顶点关联到一个链表，链表里包含的是与该顶点直接相连的所有其他顶点。这种方式特别适合稀疏图（边的数量远小于节点数的平方），因为对于每个顶点，我们只存储其相邻的顶点，节省空间。

3. DFS算法：深度优先搜索是一种用于遍历图的递归过程，它从起点开始，尽可能深地探索分支，直到到达无法再继续为止，然后回溯寻找下一个未访问的节点。

4. BFS算法：广度优先搜索则是一种逐层遍历的策略，从起点开始，先访问所有第一层的邻居，然后第二层，以此类推，直至访问完整个图。

相关问题

用C++写邻接矩阵或邻接表创建图然后进行DFS和BFS操作的一个程序

下面是一个使用邻接表创建图并进行DFS和BFS操作的C++程序：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义图的结构体
struct Graph {
    int V;  // 图的顶点数
    vector<int> *adj;  // 指向邻接表的指针
};

// 创建一个新的图
Graph* createGraph(int V) {
    Graph* graph = new Graph;
    graph->V = V;
    graph->adj = new vector<int>[V];
    return graph;
}

// 增加一条边到图中
void addEdge(Graph* graph, int src, int dest) {
    graph->adj[src].push_back(dest);  // 添加 dest 到 src 的邻接表
    graph->adj[dest].push_back(src);  // 添加 src 到 dest 的邻接表
}

// 深度优先搜索
void DFS(Graph* graph, int v, bool visited[]) {
    visited[v] = true;  // 标记当前节点为已访问
    cout << v << " ";  // 输出当前节点

    // 遍历所有邻居节点
    for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); ++i) {
        if (!visited[*i]) {
            DFS(graph, *i, visited);  // 递归遍历邻居节点
        }
    }
}

// 广度优先搜索
void BFS(Graph* graph, int v, bool visited[]) {
    queue<int> q;  // 创建一个队列用于存储待访问的节点
    visited[v] = true;  // 标记当前节点为已访问
    q.push(v);  // 将当前节点加入队列

    while (!q.empty()) {
        v = q.front();  // 取出队列中的头节点
        cout << v << " ";  // 输出头节点
        q.pop();  // 弹出头节点

        // 遍历所有邻居节点
        for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true;  // 标记当前邻居节点为已访问
                q.push(*i);  // 将当前邻居节点加入队列
            }
        }
    }
}

int main() {
    Graph* graph = createGraph(6);  // 创建一个6个节点的图
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);

    bool visited[6] = {false};  // 创建一个布尔类型的数组用于标记节点是否已访问

    cout << "DFS: ";
    DFS(graph, 0, visited);
    cout << endl;

    for (int i = 0; i < 6; ++i) {
        visited[i] = false;  // 重置visited数组
    }

    cout << "BFS: ";
    BFS(graph, 0, visited);
    cout << endl;

    return 0;
}

该程序使用邻接表创建了一个6个节点的图，并且实现了DFS和BFS操作。在DFS和BFS操作中，我们使用了一个布尔类型的数组`visited`来标记每个节点是否已经被访问过。这个数组在每次遍历之前都会被重置。

使用邻接矩阵和邻接表存储结构存储图，并分别对这两种存储结构存储的图进行DFS和BFS

邻接矩阵存储图：

邻接矩阵是用一个二维数组表示的图，数组中每个元素表示两个顶点之间是否存在一条边。如果两个顶点之间存在边，则该元素的值为1，否则为0。在无向图中，邻接矩阵是对称的，即A[i][j]=A[j][i]。

下面是使用邻接矩阵存储图的DFS和BFS算法实现：

// DFS算法实现
void DFS(int v, int visited[], int n, int A[][n]) {
    visited[v] = 1;  // 标记当前节点已被访问
    printf("%d ", v);

    for (int i = 0; i < n; i++) {  // 遍历当前节点的所有邻居
        if (A[v][i] == 1 && visited[i] == 0) {
            DFS(i, visited, n, A);  // 递归访问邻居节点
        }
    }
}

// BFS算法实现
void BFS(int s, int n, int A[][n]) {
    int visited[n];
    memset(visited, 0, sizeof(visited));  // 初始化visited数组

    queue<int> q;
    visited[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("%d ", v);

        for (int i = 0; i < n; i++) {
            if (A[v][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

邻接表存储图：

邻接表是由一个数组和若干个链表组成的数据结构，数组中每个元素对应一个顶点，链表中存储该顶点的所有邻居。在链表中，每个节点表示一个邻居，包含两个字段：邻居节点的编号和指向下一个邻居节点的指针。

下面是使用邻接表存储图的DFS和BFS算法实现：

// DFS算法实现
void DFS(int v, int visited[], vector<int> adj[]) {
    visited[v] = 1;  // 标记当前节点已被访问
    printf("%d ", v);

    for (auto u : adj[v]) {  // 遍历当前节点的所有邻居
        if (visited[u] == 0) {
            DFS(u, visited, adj);  // 递归访问邻居节点
        }
    }
}

// BFS算法实现
void BFS(int s, vector<int> adj[]) {
    int visited[adj.size()];
    memset(visited, 0, sizeof(visited));  // 初始化visited数组

    queue<int> q;
    visited[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("%d ", v);

        for (auto u : adj[v]) {
            if (visited[u] == 0) {
                visited[u] = 1;
                q.push(u);
            }
        }
    }
}