1.Prim算法生成最小生成树
//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
int min,i,j,k;
int adjvex[MAXVEX];
int lowcost[MAXVEX];
lowcost[0] = 0;
adjvex[0] = 0;
for(i = 1;i < G.numVertexes;i++)
{
lowcost[i] = G.arc[0][i];
adjvex[i] = 0;
}
for(i = 1;i < G.numVertexes;i++)
{
min = INFINITY;
j = 1;k = 0;
while(j < G.numVertexes)
{
if(lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j];
k = j;
}
j++;
}
printf("(%d,%d)",adjvex[k],k);
lowcost[k] = 0;
for(j = i;j < G.numVertexes;j++)
{
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{
lowcost[j] = G.arc[k][j];
adjvex[j] = k;
}
}
}
}42
1
//Prim算法生成最小生成树
2
void MiniSpanTree_Prim(MGraph G)
3
{
4
int min,i,j,k;
5
int adjvex[MAXVEX];
6
int lowcost[MAXVEX];
7
lowcost[0] = 0;
8
9
10
adjvex[0] = 0;
11
for(i = 1;i < G.numVertexes;i++)
12
{
13
lowcost[i] = G.arc[0][i];
14
adjvex[i] = 0;
15
}
16
for(i = 1;i < G.numVertexes;i++)
17
{
18
min = INFINITY;
19
20
j = 1;k = 0;
21
while(j < G.numVertexes)
22
{
23
if(lowcost[j] != 0 && lowcost[j] < min)
24
{
25
min = lowcost[j];
26
k = j;
27
}
28
j++;
29
}
30
31
printf("(%d,%d)",adjvex[k],k);
32
lowcost[k] = 0;
33
for(j = i;j < G.numVertexes;j++)
34
{
35
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
36
{
37
lowcost[j] = G.arc[k][j];
38
adjvex[j] = k;
39
}
40
}
41
}
42
}
2.克鲁斯卡尔（Kruskal）算法
//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
int i,n,m;
Edge edges[MAXEDGE];
int parentp[MAXVEX];
//省略将邻接矩阵转化为边集数组edges并按权由小到大排序的代码
for(i = 0; i < G.numEdges;i++)
{
parent[i] = 0;
}
for(i = o;i < G.numEdges;i++)
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if(n != m)
{
parent[n] = m;
printf("(%d,%d) %d ",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
int Find(int *parent,int f)
{
while(parent[f] > 0)
{
f = parent[f];
}
return f;
}34
1
//Kruskal算法生成最小生成树
2
void MiniSpanTree_Kruskal(MGraph G)
3
{
4
int i,n,m;
5
Edge edges[MAXEDGE];
6
int parentp[MAXVEX];
7
8
//省略将邻接矩阵转化为边集数组edges并按权由小到大排序的代码
9
for(i = 0; i < G.numEdges;i++)
10
{
11
parent[i] = 0;
12
}
13
for(i = o;i < G.numEdges;i++)
14
{
15
n = Find(parent,edges[i].begin);
16
m = Find(parent,edges[i].end);
17
if(n != m)
18
{
19
parent[n] = m;
20
printf("(%d,%d) %d ",edges[i].begin,edges[i].end,edges[i].weight);
21
22
}
23
}
24
}
25
26
27
int Find(int *parent,int f)
28
{
29
while(parent[f] > 0)
30
{
31
f = parent[f];
32
}
33
return f;
34
}
3.迪杰斯特拉（Dijkstra）算法
//迪杰斯特拉（Dijkstra）算法
#define MAXVEX 9
#define INFINITY 65535
typedef int Patharc[MAXVEX];
typedef int ShortPathTable[MAXVEX];
void ShortestPath_Dijkstra(MGraph G,INT V0,Patharc *P,ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX];
for(v = 0;v < G.numVertexes;v++)
{
final[v] = 0;
(*D)[v] = G.arc[v0][v];
(*P)[v] = 0;
}
(*D)[v0] = 0;
final[vo] = 1;
for(v = 1;v < G.numVertexes;w++)
{
min = INFINITY;
for(w = 0;w < G.numVertexes;w++)
{
if(!final[w] && (*D)[w] < min)
{
k = w;
min = (*D)[w];
}
}
final[k] = 1;
for(w = 0;w < G.numVertexes;w++)
{
if(!final[w] && (min+G.arc[k][w])< (*D)[w])
{
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}44
1
//迪杰斯特拉（Dijkstra）算法
2
#define MAXVEX 9
3
#define INFINITY 65535
4
5
typedef int Patharc[MAXVEX];
6
typedef int ShortPathTable[MAXVEX];
7
8
9
void ShortestPath_Dijkstra(MGraph G,INT V0,Patharc *P,ShortPathTable *D)
10
{
11
int v,w,k,min;
12
int final[MAXVEX];
13
for(v = 0;v < G.numVertexes;v++)
14
{
15
final[v] = 0;
16
(*D)[v] = G.arc[v0][v];
17
(*P)[v] = 0;
18
}
19
(*D)[v0] = 0;
20
final[vo] = 1;
21
22
for(v = 1;v < G.numVertexes;w++)
23
{
24
min = INFINITY;
25
for(w = 0;w < G.numVertexes;w++)
26
{
27
if(!final[w] && (*D)[w] < min)
28
{
29
k = w;
30
min = (*D)[w];
31
}
32
}
33
34
final[k] = 1;
35
for(w = 0;w < G.numVertexes;w++)
36
{
37
if(!final[w] && (min+G.arc[k][w])< (*D)[w])
38
{
39
(*D)[w] = min + G.arc[k][w];
40
(*P)[w] = k;
41
}
42
}
43
}
44
}
4.弗洛伊德（Floyd算法）
//弗洛伊德（Floyd算法）
typedef int PathMatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
{
int v,w,k;
for(v = 0;v < G.numVertexes; ++v)
{
for(w = 0;w < G.numVertexes;++w)
{
(*D)[v][w] = G.matirx[v][w]；
(*P)[v][w] = w;
}
}
for(k = 0;k < G.numVertexes;++k)
{
for(v = 0;v < G.numVertexes;++v)
{
for(w = 0;w < G.numVertexes;++w)
{
if((*D)[v][w] > (*D)[v][k]+(*D)[k][w])
{
(*D)[v][w] = (*D)[v][w]+(*D)[k][w];
(*P)[v][w] = (*P)[v][k];
}
}
}
}
}
//最短路径显示代码段
for(v = 0;v < Q.numVertexes;++v)
{
for(w = v+1;w < G.numVertexes;w++)
{
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
k = P[v][w];
printf(" path: %d",v);
while(k != w)
{
printf(" -> %d",k);
k = P[k][w];
}
printf(" -> %d\n",w);
}
printf("\n");
}x
1
//弗洛伊德（Floyd算法）
2
typedef int PathMatirx[MAXVEX][MAXVEX];
3
typedef int ShortPathTable[MAXVEX][MAXVEX];
4
5
void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
6
{
7
int v,w,k;
8
for(v = 0;v < G.numVertexes; ++v)
9
{
10
for(w = 0;w < G.numVertexes;++w)
11
{
12
(*D)[v][w] = G.matirx[v][w]；
13
(*P)[v][w] = w;
14
}
15
}
16
17
for(k = 0;k < G.numVertexes;++k)
18
{
19
for(v = 0;v < G.numVertexes;++v)
20
{
21
for(w = 0;w < G.numVertexes;++w)
22
{
23
if((*D)[v][w] > (*D)[v][k]+(*D)[k][w])
24
{
25
(*D)[v][w] = (*D)[v][w]+(*D)[k][w];
26
(*P)[v][w] = (*P)[v][k];
27
}
28
}
29
}
30
}
31
}
32
33
34
35
//最短路径显示代码段
36
for(v = 0;v < Q.numVertexes;++v)
37
{
38
for(w = v+1;w < G.numVertexes;w++)
39
{
40
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
41
k = P[v][w];
42
printf(" path: %d",v);
43
44
while(k != w)
45
{
46
printf(" -> %d",k);
47
k = P[k][w];
48
}
49
printf(" -> %d\n",w);
50
}
51
printf("\n");
52
}