📄 ln22.c
字号:
void FLOYD()
{
int i, j, k, next;
for( i = 1; i < z; i++ )
for( j = 1; j < z; j++ )
{
if( wb.dist[ i ][ j ] != max )
path[ i ][ j ] = j;
else
path[ i ][ j ] = 0;
A[ i ][ j ] = wb.dist[ i ][ j ];
}
for( k = 1; k < z; k++ )
for( i = 1; i < z; i++ )
for( j = 1; j < z; j++ )
if( A[ i ][ j ] > ( A[ i ][ k ] + A[ k ][ j ] ) )
{
A[ i ][ j ] = A[ i ][ k ] + A[ k ][ j ];
path[ i ][ j ] = path[ i ][ k ];
}
for( i = 1; i < z; i++ )
for( j = 1; j < z; j++ )
{
if( A[ i ][ j ] == max )
printf(" 距离为: MAX! ");
else
printf(" 距离为: %d ", A[ i][ j ] );
next = path[ i ][ j ];
if( next == 0 )
printf(" %d 到 %d 无路径! \n", i, j );
else
{
printf(" %d ", i );
while( next != j )
{
printf(" --> %d ", next );
next = path[ next ][ j ];
}printf(" --> %d \n", j );
}
if( j == z - 1 )
{
printf("\n 按回车键( ENTER )继续.\n ");
getchar();
getchar();
}
}
}
void TOPOSORT()
{
int i, j, k, m = 0, top = -1;
tnode *p;
for( i = 0; i < tn; i++ )
if( dig[ i ].id == 0 )
{
dig[ i ].id = top;
top = i;
}
printf("\n 进行拓扑排序后顺序为: ");
while( top != -1 )
{
j = top;
top = dig[ top ].id;
printf(" %c ",dig[ j ].vertex );
m++;
p = dig[ j ].link;
while( p )
{
k = p->adjvex;
dig[ k ].id--;
if( dig[ k ].id == 0 )
{
dig[ k ].id = top;
top = k;
}
p = p->next;
}
}
if( m < tn )
printf("\n 这个有向连通网络有回路! \n");
}
void Picture()
{
int driver = CGA, mode = CGAC0;
initgraph( &driver, &mode, " " );
setbkcolor( BLACK );
setcolor( 3 );
circle( 150, 80, 10 );
circle( 100, 60, 10 );
circle( 200, 60, 10 );
circle( 175, 120, 10 );
circle( 125, 120, 10 );
circle( 150, 40, 10 );
line( 150, 80, 150, 40 );
line( 150, 80, 175, 120 );
line( 150, 80, 125, 120 );
line( 175, 120, 200, 60 );
line( 125, 120, 100, 60 );
settextstyle( 0, 0, 0 );
setcolor( 2 );
outtextxy( 140, 77, " 3 " );
outtextxy( 140, 37, " 1 " );
outtextxy( 90, 57, " 2 " );
outtextxy( 190, 57, " 4 " );
outtextxy( 115, 117, " 5 " );
outtextxy( 165, 117, " 6 " );
}
void Picture_1()
{
Picture();
setcolor( 3 );
line( 150, 40, 100, 60 );
line( 150, 40, 200, 60 );
line( 150, 80, 100, 60 );
line( 150, 80, 200, 60 );
line( 175, 120, 125, 120 );
settextstyle( 0, 0, 0 );
setcolor( 1 );
outtextxy( 116, 62, " 5 " );
outtextxy( 144, 56, " 1 " );
outtextxy( 98, 95, " 3 " );
outtextxy( 165, 62, " 7 " );
outtextxy( 125, 90, " 5 " );
outtextxy( 138, 112, " 6 " );
outtextxy( 157, 94, " 4 " );
outtextxy( 165, 42, " 5 " );
outtextxy( 117, 40, " 6 " );
outtextxy( 180, 94, " 2 " );
}
void Picture_2()
{
int driver = CGA, mode = CGAC0;
initgraph( &driver, &mode, " " );
setbkcolor( BLACK );
setcolor( 3 );
circle( 100, 60, 10 );
circle( 200, 60, 10 );
circle( 175, 120, 10 );
circle( 125, 120, 10 );
circle( 150, 40, 10 );
line( 150, 40, 100, 60 );
line( 175, 120, 125, 120 );
line( 125, 120, 200, 60 );
line( 150, 40, 175, 120 );
settextstyle( 0, 0, 0 );
setcolor( 2 );
outtextxy( 140, 37, " 1 " );
outtextxy( 90, 57, " 2 " );
outtextxy( 190, 57, " 5 " );
outtextxy( 115, 117, " 3 " );
outtextxy( 165, 117, " 4 " );
setcolor( 1 );
outtextxy( 126, 91, " 10 " );
outtextxy( 112, 40, " 10 " );
outtextxy( 132, 56, " 30 " );
outtextxy( 138, 122, " 20 " );
}
void Picture_3()
{
Picture_2();
setcolor( 3 );
line( 125, 120, 100, 60 );
line( 175, 120, 200, 60 );
line( 150, 40, 200, 60 );
settextstyle( 0, 0, 0 );
setcolor( 1 );
outtextxy( 92, 95, " 50 " );
outtextxy( 165, 42, " 100 " );
outtextxy( 180, 94, " 60 " );
}
void fun3()
{
printf("\n 设连通网络的边数为10，顶点数为6 ");
printf("\n 如下图所示，建立其邻接矩阵: ");
getchar();
getchar();
Picture_1();
getchar();
restorecrtmode();
printf("\n 各顶点间权值关系为: ");
printf("\n (1)====(2): '6' (1)====(3): '1' (1)====(4): '5' ");
printf("\n (2)====(3): '5' (3)====(4): '7' (2)====(5): '3' ");
printf("\n (3)====(5): '5' (3)====(6): '4' (4)====(6): '2' ");
printf("\n (5)====(6): '6' ");
CREATW();
Prim();
getchar();
printf("\n 生成的最小生成树如下图所示: ");
getchar();
Picture();
getchar();
restorecrtmode();
Print();
}
void fun4()
{
printf("\n 设连通网络的边数为10，顶点数为6 ");
CREATW();
Prim();
Print();
}
void fun6();
void fun5()
{
int v;
printf("\n 设连通有向网络的顶点为5,边数为7 ");
printf("\n 如下图所示，建立其邻接矩阵: ");
getchar();
getchar();
Picture_3();
getchar();
restorecrtmode();
fun6();
getchar();
getchar();
printf("\n 最短路径关系,如下图所示: ");
getchar();
Picture_2();
getchar();
restorecrtmode();
}
void fun6()
{
int v;
printf("\n 各边权值关系如下: ");
printf("\n (1)=====>(2): 10 ");
printf("\n (1)=====>(4): 30 ");
printf("\n (1)=====>(5): 100 ");
printf("\n (2)=====>(3): 50 ");
printf("\n (3)=====>(5): 10 ");
printf("\n (4)=====>(3): 20 ");
printf("\n (4)=====>(5): 60 ");
CREATD();
printf("\n === 求源点到其与顶点的最短路径及其长度 === ");
printf("\n 输入第几个点作为源点: ");
scanf("%d", &v );
DIJKSTRA( v );
}
void jmenu( void );
void lmenu( void );
void jdmenu( void );
void menu_4( void );
void menu( void )
{
char choice, ch1;
int v;
printf("\n\n");
printf(" =========== 图的操作 ============ \n");
printf(" = 1.邻接矩阵表示法 \n");
printf(" = 2.邻接表表示法 \n");
printf(" = 3.构造最小生成树（Prim算法） \n");
printf(" = 4.最短路径 \n");
printf(" = 5.拓扑排序 \n");
printf(" = 0.返回 \n");
printf(" ================================= \n");
do
{
choice = getchar();
switch ( choice )
{
case '1':
jmenu();
break;
case '2':
lmenu();
break;
case '3':
getchar();
printf("\n 如果按例题建立最小生成树，按'Y', 否则按'N',其它键返回主菜单: ");
ch1 = getchar();
switch ( ch1 )
{
case 'y':
fun3();
break;
case 'n':
fun4();
break;
}
menu();
break;
case '4':
menu_4();
break;
case '5':
getchar();
CREATT();
TOPOSORT();
menu();
break;
case '0':
exit( 0 );
}
}while( 1 );
}
void jmenu( void )
{
char choice;
int i;
printf("\n");
printf(" ==== 图（邻接矩阵表示法）===== \n");
printf(" = 1.邻接矩阵表示法（建图） \n");
printf(" = 2.按深度优先搜索遍历 \n");
printf(" = 3.按广度优先搜索遍历 \n");
printf(" = 0.返回 \n");
printf(" ============================== \n");
do
{
choice = getchar();
switch ( choice )
{
case '1':
getchar();
CREATG();
jmenu();
break;
case '2':
printf("\n 输入从第几个位置开始遍历图（输入数字1至4）: ");
SETNULL();
scanf("%d",&i );
DFS( i - 1 );
jmenu();
break;
case '3':
printf("\n 输入从第几个位置开始遍历图（输入数字1至4）: ");
SETNULL();
scanf("%d",&i );
BFS( i - 1 );
jmenu();
break;
case '0':
menu();
}
}while( 1 );
}
void lmenu( void )
{
char choice;
int i;
printf("\n");
printf(" ==== 图（邻接表表示法）===== \n");
printf(" = 1.邻接表表示法（建图） \n");
printf(" = 2.按深度优先搜索遍历 \n");
printf(" = 3.按广度优先搜索遍历 \n");
printf(" = 0.返回 \n");
printf(" ============================ \n");
do
{
choice = getchar();
switch ( choice )
{
case '1':
getchar();
CREATA();
lmenu();
break;
case '2':
getchar();
printf("\n 输入从第几个位置开始遍历图（输入数字1至4）: ");
SETNULL();
scanf("%d", &i );
DFSL( i - 1 );
lmenu();
break;
case '3':
printf("\n 输入从第几个位置开始遍历图（输入数字1至4）: ");
SETNULL();
scanf("%d",&i );
BFSL( i - 1);
lmenu();
break;
case '0':
menu();
}
}while( 1 );
}
void menu_4( void )
{
char choice, ch1;
int i, v;
printf("\n");
printf(" ================ 最短路径 ================ \n");
printf(" = 1.单源最短路径（Dijkstra算法） \n");
printf(" = 2.所有顶点对间的最短路径（Floyd算法） \n");
printf(" = 0.返回 \n");
printf(" ========================================== \n");
do
{
choice = getchar();
switch ( choice )
{
case '1':
getchar();
printf("\n 如果按例题建立最短路径，按'Y', 否则按'N',其它键返上层菜单: ");
ch1 = getchar();
switch ( ch1 )
{
case 'y':
fun5();
break;
case 'n':
printf("\n 设连通有向网络的顶点为5,边数为7 ");
fun6();
break;
}
menu_4();
break;
case '2':
CREATF();
FLOYD();
printf("\n 各顶点间路程关系如下图: ");
getchar();
getchar();
Picture_3();
getchar();
restorecrtmode();
menu_4();
break;
case '0':
menu();
}
}while( 1 );
}
main()
{
menu();
}
.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -