#include<stdio.h>
#include <stdlib.h>
#include<windows.h>
#define M 200
#define Max 200
#define MAXSIZE 200
#define MAXSUM(a, b) (((a) != MAXSIZE && (b) != MAXSIZE) ? ((a) + (b)) : MAXSIZE)
#define SWAP( a, b) {temp = a;a = b;b = temp;}
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 floyd(int [][MAXSIZE], int [][MAXSIZE], int);
void display_path(int [][MAXSIZE], int [][MAXSIZE], int);
void reverse(int [], int);
void readin(int [][MAXSIZE], int *);
void ReturnMainMenu();
void ExitPro() ;
int sidenumber=0;
void ReturnMainMenu()
{
char ch;
scanf("%c",&ch);
while(ch!='y')
{
scanf("%c",&ch);
}
}
void ExitPro()
{
printf("welcome your next using\n");
exit(1);
}
void CreatGraph(MGraph *G)
{
int i, j,n, m;
int length;
printf("put in point number:");
scanf("%d",&G->vexnum);
for (i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
printf(" put in the sides end in 0,0,0:\n");
scanf("%d%d%d", &n, &m, &length);
while (n != 0 && n != 0 &&length != 0)
{
while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{
printf("error:\n");
scanf("%d%d%d",&n,&m,&length);
}
G->arc[n][m].adj = G->arc[m][n].adj = 1;
//getchar();
G->arc[n][m].weight=G->arc[m][n].weight=length;
sidenumber++;
scanf("%d%d%d", &n, &m, &length);
G->arcnum =sidenumber;
}
}
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);
}
}
}
}
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);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("result:\n");
for (i = 1; i <= G->arcnum ; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("< %d, %d > %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
printf("return(y):");
ReturnMainMenu();
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
void floyd(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
{
int i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
path[i][j] = i;
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (dist[i][j] > MAXSUM(dist[i][k], dist[k][j]))
{
path[i][j] = path[k][j];
dist[i][j] = MAXSUM(dist[i][k], dist[k][j]);
}
}
void reverse(int x[], int n)
{
int i, j, temp;
for (i = 0, j = n-1; i < j; i++, j--)
SWAP(x[i], x[j]);
}
void display_path(int dist[][MAXSIZE], int path[][MAXSIZE], int n)
{
int *chain;
int count;
int i, j, k;
printf("\n\nOrigin->Dest Dist Path");
printf( "\n-----------------------------");
chain = (int *) malloc(sizeof(int)*n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (i != j)
{
printf("\n%6d->%d ", i+1, j+1);
if (dist[i][j] == MAXSIZE)
printf(" NA ");
else
{
printf("%4d ", dist[i][j]);
count = 0;
k = j;
do
{
k = chain[count++] = path[i][k];
} while (i != k);
reverse(chain, count);
printf("%d", chain[0]+1);
for (k = 1; k < count; k++)
printf("->%d", chain[k]+1);
printf("->%d", j+1);
}
}
}
free(chain);
printf("\n");
printf("return(y):");
ReturnMainMenu();
}
void readin(int dist[][MAXSIZE], int *number)
{
int origin, dest, length, n;
int i, j;
printf("请输入顶点个数:");
scanf("%d", &n);
*number = n;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
dist[i][j] =MAXSIZE;
dist[i][i] = 0;
}
printf("put in the sides end in 0 0 0结束:\n");
scanf("%d%d%d", &origin, &dest, &length);
while (origin != 0 && dest != 0 && length != 0)
{
while(origin < 0 || origin > n || dest < 0 || dest > n)
{
printf("error:\n");
scanf("%d%d%d",&origin,&dest,&length);
}
dist[origin-1][dest-1] = length;
scanf("%d%d%d", &origin, &dest, &length);
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if(dist[i][j] >dist[j][i])
dist[i][j] =dist[j][i];
else
dist[j][i]=dist[i][j];
}
}
}
void main()
{
int n,a;
int dist[MAXSIZE][MAXSIZE];
int path[MAXSIZE][MAXSIZE];
while(1)
{
system("CLS");
printf("\n\t\t**************最小生成树或最短路径计算*************\n");
printf("\n\t\t _____________主菜单_____________ ");
printf("\n\t\t 请按照提示选择要使用的功能\n");
printf("\n\t\t 1.求最小生成树(kruskal算法):\n");
printf("\n\t\t 2.求最短路径(floyd算法):\n");
printf("\n\t\t 3.exit(退出):\n");
scanf("%d",&a);
switch(a)
{
case 1:
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));
if (G == NULL)
{
printf("memory allcation failed,goodbye");
exit(1);
}
CreatGraph(G);
MiniSpanTree(G);
break;
case 2:
readin(dist, &n);
floyd(dist, path, n);
display_path(dist, path, n);
break;
case 3:ExitPro();
default:printf("error\n");
Sleep(1000);
break;
}
}
}
zui-xiao-sheng-cheng-shu.rar_出行
版权申诉
86 浏览量
2022-09-24
17:20:05
上传
评论
收藏 2KB RAR 举报
JonSco
- 粉丝: 72
- 资源: 1万+
最新资源
- 简单的Python示例,演示了如何使用TCP/IP协议进行基本的客户端和服务器通信
- 考试.sql
- keil2 + proteus + 8051.exe
- 1961ee27df03bd4595d28e24b00dde4e_744c805f7e4fb4d40fa3f695bfbab035_8(1).c
- mediapipe-0.9.0.1-cp37-cp37m-win-amd64.whl.zip
- windows注册表编辑工具
- mediapipe-0.9.0.1-cp37-cp37m-win-amd64.whl.zip
- 校园通行码预约管理系统20240522075502
- 车类型数据集6250张VOC+YOLO格式.zip
- The PyTorch implementation of STGCN.STGCN-main.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈