{

m1=m+b[i][j]; jj=j;

for(si=0;si

for(si=0;si

for(si=0;si

while(sj!=max);

printf(“\\n\\n the route path is:”); for(i=0;i<=k;i++)

printf(“M->”,path[i]); printf(“温州”);

printf(“\\n total of travelling expense :”); printf(“]”,min);

92

}

实验6 最小生成树kruskal算法

[程序实现]

/*最小生成树kruskal算法用邻接矩阵做图 */ #include #include #define M 20 #define MAX 20 typedef struct {

int begin; int end; int weight;

}edge;

typedef struct {

int adj; int weight;

}AdjMatrix[MAX][MAX]; typedef struct {

AdjMatrix arc;

int vexnum, arcnum; }MGraph;

void CreatGraph(MGraph *);//函数申明 void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *); int Find(int *, int );

void Swapn(edge *, int, int);

void CreatGraph(MGraph *G)//构件图 {

int i, j,n, m;

printf(\请输入边数和顶点数:\

scanf(\

for (i = 1; i <= G->vexnum; i++)//初始化图 {

for ( j = 1; j <= G->vexnum; j++)

93

{

G->arc[i][j].adj = G->arc[j][i].adj = 0; } }

for ( i = 1; i <= G->arcnum; i++)//输入边和权值 {

printf(\请输入有边的2个顶点\scanf(\

while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) {

printf(\输入的数字不符合要求 请重新输入:\scanf(\}

G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar();

printf(\请输入%d与%d之间的权值:\scanf(\}

printf(\邻接矩阵为:\\n\

for ( i = 1; i <= G->vexnum; i++) {

for ( j = 1; j <= G->vexnum; j++) {

printf(\}

printf(\} }

void sort(edge edges[],MGraph *G)//对权值进行排序 {

int i, j;

for ( i = 1; i < G->arcnum; i++) {

for ( j = i + 1; j <= G->arcnum; j++) {

if (edges[i].weight > edges[j].weight) {

Swapn(edges, i, j); } }

94

}

printf(\权排序之后的为:\\n\for (i = 1; i < G->arcnum; i++) {

printf(\ %d\\n\}

}

void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾 {

int temp;

temp = edges[i].begin;

edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end;

edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight;

edges[i].weight = edges[j].weight; edges[j].weight = temp; }

void MiniSpanTree(MGraph *G)//生成最小生成树 {

int i, j, n, m; int k = 1;

int parent[M]; edge edges[M];

for ( i = 1; i < G->vexnum; i++) {

for (j = i + 1; j <= G->vexnum; j++) {

if (G->arc[i][j].adj == 1) {

edges[k].begin = i; edges[k].end = j;

edges[k].weight = G->arc[i][j].weight; k++;

} } }

sort(edges, G);

95