定义采用邻接矩阵存储的图结构,并封装深度优先搜索算法,广度优先搜索算法,Prim算法,Kruskal算法,Dijstra算法,Floyd算法.

C++中可以使用二维数组来表示邻接矩阵存储的图结构，其中数组的行和列分别表示图中的节点，数组中的值表示节点之间的边的权重。下面是封装的各种算法的介绍：

1. 深度优先搜索算法（DFS）：从图的某个节点开始，沿着一条路径一直走到底，直到不能再走为止，然后回溯到前一个节点，继续走其他的路径，直到所有的节点都被访问过。这个算法可以用递归或者栈来实现。

2. 广度优先搜索算法（BFS）：从图的某个节点开始，先访问它的所有邻居节点，然后再访问邻居节点的邻居节点，以此类推，直到所有的节点都被访问过。这个算法可以用队列来实现。

3. Prim算法：用于求解最小生成树，从一个节点开始，每次选择与当前节点相邻的权重最小的边所连接的节点，直到所有的节点都被访问过。这个算法可以用堆来实现。

4. Kruskal算法：也用于求解最小生成树，将所有的边按照权重从小到大排序，然后依次加入到生成树中，如果加入的边会形成环，则不加入。这个算法可以用并查集来实现。

5. Dijstra算法：用于求解单源最短路径，从一个节点开始，每次选择与当前节点距离最短的节点，然后更新其他节点到起点的距离，直到所有的节点都被访问过。这个算法可以用堆来实现。

6. Floyd算法：用于求解所有节点之间的最短路径，通过动态规划的方式，依次计算出所有节点之间的最短路径。这个算法的时间复杂度为O(n^3)。

下面是一些相关问题：

相关问题

定义采用邻接矩阵存储的图结构，封装DFS、BFS算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的C++代码，包括主函数

以下是定义采用邻接矩阵存储的图结构，封装DFS、BFS算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的C++代码，包括主函数：

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

const int INF = 0x3f3f3f3f; // 表示正无穷

// 定义邻接矩阵存储的图结构
const int MAXN = 1005;
int G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n表示顶点数，m表示边数

// DFS算法
bool vis[MAXN]; // 标记数组，表示该点是否被访问过
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v = 1; v <= n; v++) {
        if (G[u][v] && !vis[v]) {
            dfs(v);
        }
    }
}

// BFS算法
bool vis[MAXN]; // 标记数组，表示该点是否被访问过
void bfs(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << " ";
        for (int v = 1; v <= n; v++) {
            if (G[x][v] && !vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

// Prim算法
int prim() {
    int ans = 0;
    int d[MAXN]; // 存储每个点到已选点集的最短距离
    bool vis[MAXN]; // 标记数组，表示该点是否已经被选入点集
    memset(vis, false, sizeof(vis));
    memset(d, INF, sizeof(d));
    d[1] = 0; // 从1号点开始
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || d[u] > d[j])) {
                u = j;
            }
        }
        vis[u] = true;
        ans += d[u];
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && G[u][v] < d[v]) {
                d[v] = G[u][v];
            }
        }
    }
    return ans;
}

// Kruskal算法
struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
};
vector<Edge> edges; // 存储所有边的信息
int fa[MAXN]; // 并查集数组，用于判断是否形成环
int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
int kruskal() {
    int ans = 0;
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int x = find(u), y = find(v);
        if (x != y) {
            fa[x] = y;
            ans += w;
        }
    }
    return ans;
}

// Dijkstra算法
int d[MAXN]; // 存储每个点到源点的最短距离
bool vis[MAXN]; // 标记数组，表示该点是否已经确定最短路
void dijkstra(int s) {
    memset(vis, false, sizeof(vis));
    memset(d, INF, sizeof(d));
    d[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || d[u] > d[j])) {
                u = j;
            }
        }
        vis[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && G[u][v] && d[v] > d[u] + G[u][v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

// Floyd算法
int d[MAXN][MAXN]; // 存储每对顶点之间的最短距离
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(G, 0, sizeof(G));
    memset(d, INF, sizeof(d));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w; // 无向图
        d[u][v] = d[v][u] = w;
        edges.push_back({u, v, w});
    }

    // DFS算法
    memset(vis, false, sizeof(vis));
    dfs(1);
    cout << endl;

    // BFS算法
    memset(vis, false, sizeof(vis));
    bfs(1);
    cout << endl;

    // Prim算法
    cout << prim() << endl;

    // Kruskal算法
    cout << kruskal() << endl;

    // Dijkstra算法
    dijkstra(1);
    for (int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    cout << endl;

    // Floyd算法
    floyd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << d[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

详细介绍深度优先遍历，广度优先遍历，Prim算法，Kruskal算法，Dijkstra算法，Floyd算法

一、深度优先遍历

深度优先遍历（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。在深度优先遍历中，从根节点开始，沿着一条路径走到底部，然后回溯到上一个节点，继续走下一条路径，直到遍历完整个树或图。

深度优先遍历通常使用栈来实现。首先将根节点压入栈中，然后从栈中弹出一个节点，并将其未访问过的邻居节点压入栈中。重复这个过程，直到栈为空为止。

二、广度优先遍历

广度优先遍历（Breadth-First-Search，BFS）是一种用于遍历或搜索树或图的算法。在广度优先遍历中，从根节点开始，依次访问所有相邻的节点，然后依次访问这些节点的相邻节点，以此类推，直到遍历完整个树或图。

广度优先遍历通常使用队列来实现。首先将根节点放入队列中，然后从队列中取出一个节点，并将其未访问过的邻居节点放入队列中。重复这个过程，直到队列为空为止。

三、Prim算法

Prim算法是一种用于求解最小生成树的算法。最小生成树是指一棵包含所有节点的树，且其所有边的权值之和最小。

Prim算法的基本思想是从一个节点开始，逐步扩展生成树，选择距离当前生成树最近的节点进行扩展。具体来说，首先将起始节点加入生成树中，然后将该节点的所有邻居节点加入候选集合中，并选出距离当前生成树最近的节点扩展生成树。重复这个过程，直到所有节点都被加入生成树中。

四、Kruskal算法

Kruskal算法也是一种用于求解最小生成树的算法。与Prim算法不同的是，Kruskal算法是基于边来构建生成树的。

Kruskal算法的基本思想是将所有边按照权值从小到大排序，然后依次加入生成树中。具体来说，首先将所有节点看作是单独的连通块，然后将所有边按照权值排序。接着，依次选择权值最小的边，如果这条边连接的两个节点不在同一个连通块中，就将它们合并成一个连通块，并将这条边加入生成树中。重复这个过程，直到所有节点都被合并成一个连通块为止。

五、Dijkstra算法

Dijkstra算法是一种用于求解单源最短路径的算法。单源最短路径是指从一个起始节点到所有其他节点的最短路径。

Dijkstra算法的基本思想是从起始节点开始，逐步扩展最短路径，选择距离起始节点最近的节点进行扩展。具体来说，首先将起始节点加入已访问节点集合中，然后将该节点的所有邻居节点加入未访问节点集合中，并计算它们到起始节点的距离。接着，选择距离起始节点最近的节点加入已访问节点集合中，并更新其邻居节点的距离。重复这个过程，直到所有节点都被加入已访问节点集合中。

六、Floyd算法

Floyd算法是一种用于求解所有节点之间最短路径的算法。具体来说，给定一个带权重的图，Floyd算法可以计算出任意两个节点之间的最短路径。

Floyd算法的基本思想是动态规划。假设已知节点i到节点j之间的最短路径是k，然后考虑节点i到节点j之间经过节点k+1的最短路径。如果i到k+1之间的路径和k+1到j之间的路径都是最短路径，那么i到j之间的路径就是最短路径。否则，需要继续遍历节点k+2、k+3，直到所有节点都被遍历完为止。