数据结构——最短路径和最小生成树(强烈推荐).doc

最短路径:
#include<>
#define maxnode 7
#define Maxcost 99999
void dijkstra(int cost[][maxnode],int n,int v0,int *dist)
{
int s[maxnode];
int mindis,dis;
int i,j,u;
for(i=0;i<n;i++)
{
dist[i]=cost[v0][i];
s[i]=0;
}
s[v0]=1;
for(i=1;i<n;i++)
{
mindis=Maxcost;
for(j=1;j<n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=1;j<n;j++)
{
if(s[j]==0)
{
dis=dist[u]+cost[u][j];
if(dist[j]>dis)
{
dist[j]=dis;
}
}
}
}
for(i=1;i<n;i++)
{
printf("%d ",dist[i]);
}
printf("\n");
}
void main()
{
int cost[7][7]={{0,13,8,Maxcost,Maxcost,Maxcost,32},
{Maxcost,0,Maxcost,Maxcost,Maxcost,9,7},
{Maxcost,Maxcost,0,5,Maxcost,Maxcost,Maxcost},
{Maxcost,Maxcost,Maxcost,0,6,Maxcost,Maxcost},
{Maxcost,Maxcost,Maxcost,Maxcost,0,2,Maxcost},
{Maxcost,Maxcost,Maxcost,Maxcost,Maxcost,0,Maxcost},
{32,7,Maxcost,Maxcost,Maxcost,17,0}};
int dist[maxnode];
dijkstra(cost,maxnode,0,dist);
}
最小生成树:
#include <>
#include <>

#define MAX 100
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

int Prim(int graph[][MAX], int n)
{
/* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/
int lowcost[MAX];

/* mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/
int mst[MAX];

int i, j, min, minid, sum = 0;

/* 默认选择1号节点加入生成树,从2号节点开始初始化*/
for (i = 2; i <= n; i