数据结构 |
您所在的位置：网站首页 › 树边的集合怎么看 › 数据结构 |
数据结构
|
前言 A wise man changes his mind,a fool never. Name:Willam Time:2017/3/1 1、什么是最小生成树现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？ 于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。 构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用MST性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。 2、普里姆算法—Prim算法算法思路： 首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。 下面我们对下面这幅图求其最小生成树： 假设我们从顶点v1开始，所以我们可以发现（v1,v3）边的权重最小，所以第一个输出的边就是：v1—v3=1: 然后，我们要从v1和v3作为起点的边中寻找权重最小的边，首先了（v1,v3）已经访问过了，所以我们从其他边中寻找，发现(v3,v6)这条边最小，所以输出边就是：v3—-v6=4 然后，我们要从v1、v3、v6这三个点相关联的边中寻找一条权重最小的边，我们可以发现边(v6,v4)权重最小，所以输出边就是：v6—-v4=2. 然后，我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最小的边，发现边（v3，v2）的权重最小，所以输出边：v3—–v2=5 然后，我们就从v1、v3、v6、v4，v2这2五个顶点相关联的边中寻找权重最小的边，发现边（v2，v5）的权重最小，所以输出边：v2—–v5=3 最后，我们发现六个点都已经加入到集合U了，我们的最小生成树建立完成。 3、普里姆算法—代码实现（1）采用的是邻接矩阵的方式存储图，代码如下 #include #include #include using namespace std; //首先是使用邻接矩阵完成Prim算法 struct Graph { int vexnum; //顶点个数 int edge; //边的条数 int ** arc; //邻接矩阵 string *information; //记录每个顶点名称 }; //创建图 void createGraph(Graph & g) { cout g.vexnum; cin >> g.edge; //输入边的条数 g.information = new string[g.vexnum]; g.arc = new int*[g.vexnum]; int i = 0; //开辟空间的同时，进行名称的初始化 for (i = 0; i < g.vexnum; i++) { g.arc[i] = new int[g.vexnum]; g.information[i]="v"+ std::to_string(i+1);//对每个顶点进行命名 for (int k = 0; k < g.vexnum; k++) { g.arc[i][k] = INT_MAX; //初始化我们的邻接矩阵 } } cout start; //输入每条边的起点 cin >> end; //输入每条边的终点 int weight; cin >> weight; g.arc[start-1][end-1]=weight;//无向图的边是相反的 g.arc[end-1][start-1] = weight; } } //打印图 void print(Graph g) { int i; for (i = 0; i < g.vexnum; i++) { //cout next) {//找到表结点中start-1这个结点的链表的最后一个顶点 temp = temp->next; } temp->next = next_2; //在该链表的尾部插入一个结点 } } } void print(Graph_List g) { cout> edge; while (!check(Vexnum, edge)) { cout Vexnum >> edge; } //声明一个边集数组 Edge * edge_tag; //输入每条边的信息 createGraph(edge_tag, Vexnum, edge); int * parent = new int[Vexnum]; //记录每个顶点所在子树的根节点下标 int * child = new int[Vexnum]; //记录每个顶点为根节点时，其有的孩子节点的个数 int i; for (i = 0; i < Vexnum; i++) { parent[i] = i; child[i] = 0; } //对边集数组进行排序，按照权重从小到达排序 qsort(edge_tag, edge, sizeof(Edge), cmp); int count_vex; //记录输出的边的条数 count_vex = i = 0; while (i != edge) { //如果两颗树可以组合在一起，说明该边是生成树的一条边 if (union_tree(edge_tag[i], parent, child)) { cout |
【本文地址】