数据结构-最小生成树

一.最小生成树的定义

从V个顶点的图里生成的一颗树，这颗树有V个顶点是连通的，有V-1条边，并且边的权值和是最小的,而且不能有回路

二.Prim算法

Prim算法又叫加点法，算法比较适合稠密图

每次把边权最小的顶点加入到树中，最小生成树的不是唯一的，但最小边权是唯一的

Prim算法和 Dijkstra

核心代码

/*更新顶点距离树的距离*/for(W=0;W<Graph->Nv;W++)/*对图中顶点每个顶点W*/if (dist[W] != 0 && Graph->G[V][W] < INFINITY) {/*若W是V的邻接点并且未被收录*/if (Graph->G[V][W] < dist[W]) {/*若收录V使得dist[W]变小*/dist[W] = Graph->G[V][W];parent[W] = V;/*更新树*/}}

dist每个顶点的变化

dist[i]=0表示已经加入到最小生成树，距离树的距离是0，65535表示和树没有连接

全部代码

#include<iostream>
using namespace std;#define INFINITY 65535
#define MaxvertexNum 100
typedef int Vertex;
typedef int WeightType;
Vertex Visited[MaxvertexNum];
Vertex parent[MaxvertexNum];/*边的定义*/
typedef struct ENode* PtrToENode;
struct ENode
{Vertex V1, V2;WeightType Weight;/*边权*/
};
typedef PtrToENode Edge;typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{Vertex Adjx;/*邻接点下标*/WeightType Weight;/*边权*/PtrToAdjVNode Next;/*指向下一个邻接点*/
};
typedef struct Vnode {PtrToAdjVNode FirstEdge;/*边表头结点*/}AdjList[MaxvertexNum];/*邻接表*/
typedef struct LGNode* PtrToLGNode;
typedef struct LGNode {int Nv;/*顶点数*/int Ne;/*边数*/AdjList G;
};
typedef PtrToLGNode LGraph;/*邻接表方式存储*/
/*图的定义*/
typedef struct GNode* PtrToGNode;
struct GNode {int Nv;/*顶点数*/int Ne;/*边数*/WeightType G[MaxvertexNum][MaxvertexNum];
};
typedef PtrToGNode MGraph;
LGraph Create(int Vertexnum) {Vertex V;LGraph Graph = new LGNode();Graph->Nv = Vertexnum;Graph->Ne = 0;for (V = 0; V < Graph->Nv; V++) {Graph->G[V].FirstEdge = NULL;}return Graph;
}
void Insert(LGraph Gaph, Edge E) {PtrToAdjVNode NewNode;NewNode = new AdjVNode();NewNode->Adjx = E->V2;NewNode->Next = Gaph->G[E->V1].FirstEdge;Gaph->G[E->V1].FirstEdge = NewNode;NewNode = new AdjVNode();NewNode->Adjx = E->V1;NewNode->Next = Gaph->G[E->V2].FirstEdge;Gaph->G[E->V2].FirstEdge = NewNode;
}
//插入边
void InsertEdge(MGraph Graph, Edge E) {Graph->G[E->V1][E->V2] = E->Weight;Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph CreateGraph(int VertexNum) {MGraph Graph = new GNode();Graph->Nv = VertexNum;Graph->Ne = 0;for (int V = 0; V < Graph->Nv; V++)for (int W = 0; W < Graph->Nv; W++)Graph->G[V][W] = INFINITY;return Graph;
}
MGraph BuildGraph() {MGraph Graph;Edge E;int Nv;/*顶点*/cin >> Nv;Graph = CreateGraph(Nv);cin >> Graph->Ne;if (Graph->Ne != 0) {for (int i = 0; i < Graph->Ne; i++) {E = new ENode();cin >> E->V1 >> E->V2 >> E->Weight;InsertEdge(Graph, E);}}return Graph;}
Vertex FindMinDist(MGraph Graph, WeightType dist[]) {/*返回未被收录顶点中dist最小者*/Vertex MinV, V;WeightType MinDist = INFINITY;for (V = 0; V < Graph->Nv; V++) {if (dist[V] != 0 && dist[V] < MinDist) {MinDist = dist[V];MinV = V;}}if (MinDist < INFINITY)return MinV;else return 0;
}
int Prim(MGraph Graph, LGraph& MST) {/*将最小生成树保存为邻接表存储的图MST，返回最小权重和*//*dist表示顶点到树的距离*/ /*权重*/WeightType dist[MaxvertexNum], Tota1Weight;Vertex V, W;int VCount;Edge E;/*初始化。默认初始点下标是0*/for (V = 0; V < Graph->Nv; V++) {/*这里假设V到W没有直接边，则Graph->G[V][W]定义INF*/dist[V] = Graph->G[0][V];parent[V] = 0;/*暂且定义所以顶点的父亲结点都是初始化0*/}Tota1Weight = 0;/*初始化权重*/VCount = 0;/*初始化收入的顶点个数*//*创建一个没有边的邻接表*/MST = Create(Graph->Nv);E = new ENode();/*将初始点0收录MST*/dist[0] = 0;VCount++;parent[0] = -1;/*当前树根是0*/while (1) {V = FindMinDist(Graph,dist);/*V=未被收录顶点中dist最小者*/if (V == 0)/*若这样的V不存在*/break;/*算法结束*/E->V1 = parent[V];/*父亲顶点*/E->V2 = V;/*子结点*/E->Weight = dist[V];Insert(MST, E);Tota1Weight += dist[V];dist[V] = 0;/*将顶点收录集合树*/VCount++;/*更新顶点距离树的距离*/for(W=0;W<Graph->Nv;W++)/*对图中顶点每个顶点W*/if (dist[W] != 0 && Graph->G[V][W] < INFINITY) {/*若W是V的邻接点并且未被收录*/if (Graph->G[V][W] < dist[W]) {/*若收录V使得dist[W]变小*/dist[W] = Graph->G[V][W];parent[W] = V;/*更新树*/}}}/*while结束*/if (VCount < Graph->Nv)/* MST中收的顶点不到|V|个*/Tota1Weight = 0;return Tota1Weight;
}void DFS(LGraph Graph, Vertex V) {cout << V << endl;PtrToAdjVNode W;Visited[V] = 1;for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (Visited[W->Adjx] == 0) {DFS(Graph, W->Adjx);}}}
int main()
{MGraph G = BuildGraph();LGraph Gr =NULL;Prim(G,Gr);DFS(Gr, 0);for (int i = 0; i < G->Nv; i++)cout << i<<" " << parent[i] << endl;return 0;
}
/*
*
6 10
0 1 6
0 2 1
0 3 5
1 4 3
3 2 4
1 2 5
4 2 6
3 5 2
5 2 4
4 5 6
*/

三.Kruskal算法

Kruskal算法又叫加边法，算法比较适合稀疏图

代码

#include<iostream>
using namespace std;
#define MaxVertexNum 100
typedef int Vertex;
typedef int WeightType;
typedef Vertex ElementType;/*默认元素可以用非负正数表示*/
typedef Vertex SetName;/*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[MaxVertexNum];/*假设集合元素下标从0开始*/
Vertex Visited[MaxVertexNum];
typedef struct ENode* PtrToENode;struct ENode
{Vertex V1, V2;WeightType Weight;
};
typedef PtrToENode Edge;typedef struct AdjVNode* PtrToAdjVNode;struct AdjVNode
{Vertex Adjx;/*邻接点下标 */WeightType Weight;/*边权重*/PtrToAdjVNode Next;/*向下下一个邻接点*/
};
typedef struct Vnode {PtrToAdjVNode FirstEdge;/* 边表头指针*/}AdjList[MaxVertexNum];
typedef struct GNode* PtrToGNode;
typedef struct GNode {int Nv;/*顶点个数*/int Ne;/*边的个数*/AdjList G;
};
typedef PtrToGNode LGraph;/*邻接表方式存储*/void InsertEdge(LGraph Graph, Edge E);
LGraph CreateGraph(int Vertexnum) {Vertex W, V;LGraph Graph = new GNode();Graph->Nv = Vertexnum;Graph->Ne = 0;for (V = 0; V < Graph->Nv; V++) {Graph->G[V].FirstEdge = NULL;}return Graph;
}
LGraph BuildGraph() {int Nv;Vertex V;Edge E;cin >> Nv;LGraph Graph =  CreateGraph(Nv);cin >> Graph->Ne;if (Graph->Ne != 0) {for (V = 0; V < Graph->Ne; V++) {E = new ENode();cin >> E->V1 >> E->V2 >> E->Weight;InsertEdge(Graph, E);}}return Graph;
}
void InsertEdge(LGraph Graph, Edge E) {PtrToAdjVNode W;W = new AdjVNode();W->Adjx = E->V2;W->Weight = E->Weight;W->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = W;W = new AdjVNode();W->Adjx = E->V1;W->Weight = E->Weight;W->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = W;}
void InitializeVSet(SetType S, int N) {/*初始化并查集*/ElementType X;for (X = 0; X < N; X++)S[X] = -1;
}
void Union(SetType S, SetName Root1, SetName Root2) {/*这里默认Root1和Root2是不同集合的根节点*/if (S[Root2] < S[Root1]) { /*如果集合2比较大*/S[Root2] += S[Root1];/*集合1并入集合2*/S[Root1] = Root2;}else {S[Root1] += S[Root2];/*集合2并入集合1*/S[Root2] = Root1;}
}
SetName Find(SetType S, ElementType X) {/*默认集合元素全部初始化为-1*/if (S[X] < 0)/*找到集合的根*/return X;elsereturn S[X] = Find(S, S[X]);/*路径压缩*/
}
bool ChekCycle(SetType VSet, Vertex V1, Vertex V2) {/*检查连接V1和V2的边是否在现有的最小生成树子集中构成回来*/Vertex Root1, Root2;Root1 = Find(VSet, V1);/*得到V1所属的连通集名称*/Root2 = Find(VSet, V2);/*得到V2所属的连通集名称*/if (Root1 == Root2)/*若V1和V2已经连通，则该边不能要*/return false;else {/*否则改边可以被收集同时将V1和V2并入同一连通集*/Union(VSet, Root1, Root2);return true;}
}/*边的最小堆*/
/*将N个元素的边数组以ESet[p]为根的子堆调整为关于Weight的最小堆*/
void PerDown(Edge ESet,int p,int N) {//直接用数组，不用heap结构了int Parent, Child;struct ENode X;X = ESet[p];for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {Child = Parent * 2 + 1;if ((Child != N - 1) && (ESet[Child].Weight > ESet[Child + 1].Weight))Child++;if (X.Weight <= ESet[Child].Weight)break;else/*下滤*/ESet[Parent] = ESet[Child];}ESet[Parent] = X;
}
/*将图的边存入数组ESet,并且初始化为最下堆*/
void InitializeESet(LGraph Graph, Edge ESet) {Vertex V;PtrToAdjVNode W;int ECount;/*将图的边存入数组ESet*/ECount = 0;for(V=0;V<Graph->Nv;V++)for(W=Graph->G[V].FirstEdge;W;W=W->Next)if (V < W->Adjx) {/*避免重复录入无向图的边 只收V1<V2的边*/ESet[ECount].V1 = V;ESet[ECount].V2 = W->Adjx;ESet[ECount++].Weight = W->Weight;}/*初始化最小堆*/for (ECount = Graph->Ne / 2; ECount >= 0; ECount--)PerDown(ESet, ECount, Graph->Ne);
}
void Swap(struct ENode* a, struct ENode* b) {struct ENode* c;c = a;a = b;b = c;
}
/*给定当前堆的大小CurrentSize,将当前最小边位置弹出并调整*/
int GetEdeg(Edge ESet, int CurrentSize) {Swap(&ESet[0], &ESet[CurrentSize - 1]);/*将最小边与当前堆的最后一个位置的边交换*/PerDown(ESet, 0, CurrentSize - 1);/*将剩下的边继续调整成最小堆*/return CurrentSize - 1;/*返回最小边所在位置*/
}
int Kruskal(LGraph Graph, LGraph& MST) {WeightType TotalWeight;int ECount, NextEdge;SetType VSet;/*顶点数组*/Edge ESet;//边数组InitializeVSet(VSet, Graph->Nv);/*初始化顶点并查集*/ESet = (Edge)malloc(sizeof(struct ENode) * Graph->Ne);//ESet = new ENode[Graph->Ne];InitializeESet(Graph, ESet);/*初始化边的最小堆*///创建MSV图MST = CreateGraph(Graph->Nv);TotalWeight = 0;ECount = 0;NextEdge = Graph->Ne;//原始边集合的规模while (ECount < Graph->Nv - 1) {//当收集的边下与顶点数-1时NextEdge = GetEdeg(ESet, NextEdge);if (NextEdge < 0)//边收集已经空break;if (ChekCycle(VSet, ESet[NextEdge].V1, ESet[NextEdge].V2))//如果不构成回来{// 插入边到MST中InsertEdge(MST, ESet + NextEdge);//相当于&ESet[NextEdge] ;TotalWeight += ESet[NextEdge].Weight;ECount++;}}//while循环结束 if (ECount < Graph->Nv - 1)TotalWeight = -1;//设置错误标准return TotalWeight;
}
void DFS(LGraph Graph, Vertex V) {cout << V << endl;PtrToAdjVNode W;Visited[V] = 1;for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (Visited[W->Adjx] == 0) {DFS(Graph, W->Adjx);}}}
int main()
{LGraph Graph = BuildGraph();LGraph MST = NULL;Kruskal(Graph, MST);DFS(MST, 0);for(int i=0;i<Graph->Ne;i++)return 0;
}