用邻接矩阵表示无向带权图prim c++

无向带权图可以用邻接矩阵来表示，而Prim算法是一种用来寻找最小生成树的算法。首先，我们需要构建一个二维数组作为邻接矩阵来表示图的边的权重。假设该无向带权图有n个顶点，我们可以构建一个n*n的矩阵来表示图中顶点之间的边的权重。

接着，我们可以利用Prim算法来找出该图的最小生成树。具体做法是从任意一个顶点开始，将其加入到最小生成树中，并标记为已访问。然后依次找出与已访问的顶点相连且权重最小的边所连接的顶点，将其加入到最小生成树中，并标记为已访问。

重复上述步骤直到所有的顶点都被访问过，即可得到该图的最小生成树。最小生成树的邻接矩阵就是Prim算法中每一步都选取的顶点与其连接的边所构成的矩阵。

总的来说，用邻接矩阵表示无向带权图prim c 就是利用二维数组来表示图的边的权重，然后利用Prim算法来寻找最小生成树，最后得到最小生成树的邻接矩阵来表示整个图的结构。

相关问题

c++邻接矩阵prim算法

邻接矩阵Prim算法是一种用于解决最小生成树问题的算法，它基于贪心策略，每次选择当前最小的边来扩展生成树。下面是C++实现邻接矩阵Prim算法的基本步骤：

1. 定义一个邻接矩阵来表示图，其中矩阵中的元素表示两个顶点之间的边的权重。

2. 定义一个数组来记录每个顶点是否已经被访问过，初始值为false。

3. 定义一个数组来记录每个顶点到生成树的最小距离，初始值为无穷大。

4. 选择一个起始顶点，将其标记为已访问，并将其到生成树的最小距离设为0。

5. 对于起始顶点的所有邻居，更新它们到生成树的最小距离。

6. 从未访问过的顶点中选择一个到生成树距离最小的顶点，将其标记为已访问，并将其到生成树的最小距离设为0。

7. 重复步骤5和6，直到所有顶点都被访问过。

8. 最终生成的树即为最小生成树。

给我一个 采用邻接矩阵存储一个无向图并用这个邻接矩阵实现无向图的最小生成树的PRIM算法c++代码

以下是一个使用邻接矩阵存储无向图并实现Prim算法的C++代码：

#include <iostream>
#include <climits>
using namespace std;

#define MAX_SIZE 100

class Graph {
private:
    int num_vertex;  // 图顶点的个数
    int adj_matrix[MAX_SIZE][MAX_SIZE];  // 邻接矩阵
    int parent[MAX_SIZE];  // 最小生成树中每个节点的父节点
    int key[MAX_SIZE];  // 用于Prim算法的关键字数组
    bool visited[MAX_SIZE];  // 节点是否已经被访问

public:
    Graph(int num_vertex) {
        this->num_vertex = num_vertex;
        for (int i = 0; i < num_vertex; i++) {
            for (int j = 0; j < num_vertex; j++) {
                adj_matrix[i][j] = 0;
            }
            visited[i] = false;
            key[i] = INT_MAX;
        }
    }

    void add_edge(int i, int j, int weight) {
        adj_matrix[i][j] = weight;
        adj_matrix[j][i] = weight;
    }

    void prim() {
        key[0] = 0;
        parent[0] = -1;
        for (int i = 0; i < num_vertex - 1; i++) {
            // 找到未被访问的关键字最小的节点
            int min_key = INT_MAX;
            int min_index = -1;
            for (int j = 0; j < num_vertex; j++) {
                if (!visited[j] && key[j] < min_key) {
                    min_key = key[j];
                    min_index = j;
                }
            }
            visited[min_index] = true;

            // 更新相邻节点的关键字和父节点
            for (int j = 0; j < num_vertex; j++) {
                if (adj_matrix[min_index][j] && !visited[j] && adj_matrix[min_index][j] < key[j]) {
                    key[j] = adj_matrix[min_index][j];
                    parent[j] = min_index;
                }
            }
        }
    }

    void print_tree() {
        cout << "Edge\tWeight" << endl;
        for (int i = 1; i < num_vertex; i++) {
            cout << parent[i] << " - " << i << "\t" << adj_matrix[i][parent[i]] << endl;
        }
    }
};

int main() {
    Graph g(7);
    g.add_edge(0, 1, 7);
    g.add_edge(0, 3, 5);
    g.add_edge(1, 2, 8);
    g.add_edge(1, 3, 9);
    g.add_edge(1, 4, 7);
    g.add_edge(2, 4, 5);
    g.add_edge(3, 4, 15);
    g.add_edge(3, 5, 6);
    g.add_edge(4, 5, 8);
    g.add_edge(4, 6, 9);
    g.add_edge(5, 6, 11);

    g.prim();
    g.print_tree();

    return 0;
}

以上代码中，我们在Graph类中增加了三个成员变量：parent、key和visited，分别用于存储最小生成树中每个节点的父节点、Prim算法的关键字数组和节点是否已经被访问。在prim函数中，我们首先将节点0标记为已访问，并将其关键字设为0，然后依次找到未被访问的关键字最小的节点，并将其标记为已访问。接着，我们更新未被访问的相邻节点的关键字和父节点。

最后，我们在print_tree函数中输出最小生成树的边和权重。在main函数中，我们创建了一个Graph对象，并向其中添加了一些边，然后调用prim函数求解最小生成树，并调用print_tree函数输出结果。