Prim算法、Kruskal算法构造最小生成树 && Dijkstra算法求解最短路径（C++完整代码）

 Prim算法

#include 
#define MaxSize 100
#define INFINITY 9999
using namespace std;
typedef struct {
	char vertex[MaxSize];
	int edge[MaxSize][MaxSize];
	int vexnum,arcnum;
} AMGraph;
struct {
	char adjvex;
	int lowcost;
} closeedge[MaxSize];
int locate(AMGraph G,char c){
	for(int i=0;i>G.vexnum>>G.arcnum;
	for(int i=0;i>G.vertex[i];
	}
	cout<>tmp1>>tmp2;
		u=locate(G,tmp1);
		v=locate(G,tmp2);
		cin>>G.edge[u][v];
		G.edge[v][u]=G.edge[u][v];
	}
}
int findMin(AMGraph G){
	int index=-1;
	int min=INFINITY;
	for(int i=0;icloseedge[i].lowcost && closeedge[i].lowcost!=0){
			min=closeedge[i].lowcost;
			index=i;
		}
	}
	return index;
}
void prim(AMGraph G,char u){
	int k,i,j;
	k=locate(G,u);
	for(i=0;i "<G.edge[i][k]){
				closeedge[k].lowcost=G.edge[i][k];
				closeedge[k].adjvex=G.vertex[i];
			}
		}
	}
}
int main(void){
	AMGraph G;
	createGraph(G);
	prim(G,'a');
	return 0;
} 

Kruskal算法

#include 
#define MaxSize 100
#define INFINITY 9999
using namespace std;
typedef struct {
	char vertex[MaxSize];
	int arcnode[MaxSize][MaxSize];
	int vexnum,arcnum;
} AMGraph;
struct {
	char head,tail;
	int weight;
} Edge[50*99];
int vexSet[MaxSize];
int locate(AMGraph G,char c){
	for(int i=0;i>G.vexnum>>G.arcnum;
	for(int i=0;i>G.vertex[i];
	}
	cout<>tmp1>>tmp2;
		u=locate(G,tmp1);
		v=locate(G,tmp2);
		cin>>G.arcnode[u][v];
		G.arcnode[v][u]=G.arcnode[u][v];
		Edge[i].head=tmp1;
		Edge[i].tail=tmp2;
		Edge[i].weight=G.arcnode[u][v];
	}
}
void sort(AMGraph &G){
	int headtmp,tailtmp,weighttmp;
	int m=G.arcnum-2;
	bool flag=false;
	while(m>=0 && flag==false){
		flag=true;
		for(int i=0;i<=m;i++){
			if(Edge[i].weight>Edge[i+1].weight){
				flag=false;
				headtmp=Edge[i].head;
				Edge[i].head=Edge[i+1].head;
				Edge[i+1].head=headtmp;
				tailtmp=Edge[i].tail;
				Edge[i].tail=Edge[i+1].tail;
				Edge[i+1].tail=tailtmp;
				weighttmp=Edge[i].weight;
				Edge[i].weight=Edge[i+1].weight;
				Edge[i+1].weight=weighttmp;
			}
		}
		m--;
	}
}
void kruskal(AMGraph G){
	sort(G);
	int i,u0,v0;
	char u,v;
	for(i=0;i "<

#include 
#define MaxSize 100
#define INFINITY 9999
using namespace std;
int d[MaxSize];
char path[MaxSize];
bool isSelected[MaxSize];
typedef struct {
	char vertices[MaxSize];
	int edge[MaxSize][MaxSize];
	int vernum,arcnum;
} AMGraph;
int locate(AMGraph G,char c){
	for(int i=0;i>G.vernum>>G.arcnum;
	for(int i=0;i>G.vertices[i];
	} 
	cout<>tmp1>>tmp2;
		u=locate(G,tmp1);
		v=locate(G,tmp2);
		cin>>G.edge[u][v];
		G.edge[v][u]=G.edge[u][v];
	}
}
void Dijkstra(AMGraph G,int v){
	for(int i=0;id[v0]+G.edge[v0][k]){
				d[k]=d[v0]+G.edge[v0][k];
				path[k]=G.vertices[v0];
			}
		}
		v=v0;
	}
}
void show(AMGraph G,int u,int v){
	Dijkstra(G,u);
	if(d[v]==0){
		cout<"<>start>>end;
	startnum=locate(G,start);
	endnum=locate(G,end);
	show(G,startnum,endnum);
	return 0;
}