自己总结的关于图论的一些算法实现（C语言实现，有较详细注释，800行左右）
View Post
自己总结的关于图论的一些算法实现（C语言实现，有较详细注释，800行左右）
(提示，是C语言实现。)
代码仅供学习使用，如果觉得不错的话，点个赞喔~~Thanks
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define TRUE 1 5 #define FALSE 0 6 #define inf 99999 7 typedef int BOOL; 8 typedef int ElemType; 9 typedef struct mGraph 10 { 11 ElemType **a; //邻接矩阵 12 int n; //图的当前顶点数 13 int e; //图的当前边数 14 ElemType noEdge; //两顶点间无边时的值 15 }MGraph; 16 typedef struct queue 17 { 18 int front; //队头 19 int rear; //队尾 20 int MaxSize; //队的最大容量 21 ElemType *element; //存储元素 22 }Queue; 23 typedef struct eNode 24 { 25 int adjVex; //与任意顶点u相邻接的顶点 26 ElemType w; //边的权值 27 struct eNode *nextArc; //指向下一个结点 28 }ENode; 29 typedef struct lGraph 30 { 31 int n; //图当前的顶点数 32 int e; //图当前的边数 33 ENode **a; //指向一维指针数组 34 }LGraph; 35 typedef struct stack 36 { 37 int top; //栈顶 38 int maxSize; //栈所能装最大元素量 39 ElemType *element; //数据 40 }Stack; 41 42 int vis_m[1000]; //邻接矩阵对应图的标记数组。 vis_m[i]用于表示 编号为i的结点是否被使用过，没有使用过则 =0，否则 =1; 43 int vis_l[1000]; //邻接表对应图的标记数组。 vis_m[i]用于表示 编号为i的结点是否被使用过，没有使用过则 =0，否则 =1; 44 int path[1000]; //用于记录最佳路径上的结点编号 45 int Min_Time=999999; //用于记录最佳路径所花费的时间，初始化时尽量使它大 46 int count; //记录最佳路径上结点的个数 47 int load[1000]; //用于图的遍历，让遍历路径数组的储存空间足够大 48 int cnt; //用于表示load[]数组的下标 49 50 void Clear_Flag() //标记清零操作 51 { 52 int i; 53 cnt=0; 54 for( i=0;i<1000;i++ ) 55 load[i]=vis_m[i]=vis_l[i]=0; 56 } 57 58 void Create_S( Stack *s,int size ) //创建栈 59 { 60 s->maxSize=size; 61 s->top=-1; //现在栈还是空的，所以栈顶为“-1” 62 s->element=(ElemType*)malloc(sizeof(ElemType)); 63 } 64 void Destroy_S( Stack *s ) //销毁栈 65 { 66 s->top=-1; 67 s->maxSize=0; 68 free(s->element); //因为只申请了一次，所以只释放一次 69 } 70 BOOL IsEmpty_S( Stack *s ) //判断栈是否为空栈 71 { 72 return s->top==-1; 73 } 74 BOOL IsFull_S( Stack *s ) //判断一个栈是否已满 75 { 76 return s->top==s->maxSize-1; 77 } 78 void Top_S( Stack *s,ElemType *x ) //获取栈顶元素 79 { 80 if( IsEmpty_S(s) ) //如果栈为空 81 { 82 printf("现在栈为空栈，没有东西可取喔。\n"); 83 return ; 84 } 85 *x=s->element[s->top]; 86 } 87 void Push_S( Stack *s,ElemType x ) //入栈 88 { 89 if( IsFull_S(s) ) //如果栈已满 90 { 91 printf("现在栈已满，不能再装东西啦喔。\n"); 92 return ; 93 } 94 s->top++; 95 s->element[s->top]=x; 96 } 97 void Pop_S( Stack *s ) //删除栈顶元素 98 { 99 if( IsEmpty_S(s) ) //如果栈为空 100 { 101 printf("现在栈为空栈喔。\n"); 102 return ; 103 } 104 s->top--; 105 } 106 void Clear_S( Stack *s ) //清空栈，但不释放空间 107 { 108 s->top=-1; 109 } 110 111 void Create_Q( Queue *q,int size ) //创建队列 112 { 113 q->front=q->rear=0; //创建时，这里为0，都指向队头 114 q->MaxSize=size; 115 q->element=(ElemType*)malloc(size*sizeof(ElemType)); 116 } 117 void Destroy_Q( Queue *q ) 118 { 119 q->front=q->rear=-1; 120 q->MaxSize=0; 121 free(q->element); 122 } 123 void Clear_Q( Queue *q ) 124 { 125 q->front=q->rear=0; //注意这里也是0，清空时，让它俩都指向队头 126 } 127 BOOL IsEmpty_Q( Queue *q ) //判断队列是否为空 128 { 129 return q->front==q->rear; 130 } 131 BOOL IsFull_Q( Queue *q ) //判断队列是否已满 132 { 133 return (q->rear+1)%q->MaxSize==q->front; 134 } 135 void Push_Q( Queue *q,ElemType x ) 136 { 137 if( IsFull_Q(q) ) 138 { 139 printf("队列已满，无法再进行入队操作！\n"); 140 return ; 141 } 142 q->rear=(q->rear+1)%q->MaxSize; 143 q->element[q->rear]=x; 144 } 145 void DeQueue_Q( Queue *q ) //删除队头元素，出队操作 146 { 147 if( IsEmpty_Q(q) ) 148 { 149 printf("队列为空，无法再进行出队操作！\n"); 150 return ; 151 } 152 q->front=(q->front+1)%q->MaxSize; 153 } 154 void Front_Q( Queue *q,ElemType *x ) //获取队头元素 155 { 156 if( IsEmpty_Q(q) ) 157 { 158 printf("队列为空，无法获取队头元素！\n"); 159 return ; 160 } 161 *x=q->element[(q->front+1)%q->MaxSize]; 162 } 163 164 165 void Init_M( MGraph *mg,int v,ElemType noEdge ) //v为顶点数，noEdge为：两顶点无边时的值 166 { 167 int i,j; 168 mg->n=v; 169 mg->e=0; //初始化时没有边 170 mg->noEdge=noEdge; 171 mg->a=(ElemType**)malloc(mg->n*sizeof(ElemType*)); //申请二维动态空间 172 for( i=0;i<mg->n;i++ ) 173 { 174 mg->a[i]=(ElemType*)malloc(mg->n*sizeof(ElemType)); //申请一维动态空间 175 for( j=0;j<mg->n;j++ ) 176 mg->a[i][j]=mg->noEdge; 177 mg->a[i][i]=0; 178 } 179 printf("邻接矩阵已成功初始化！\n"); 180 return ; 181 } 182 void Destroy_M( MGraph *mg ) 183 { 184 int i; 185 for( i=0;i<mg->n;i++ ) //申请了几次一维动态空间就要释放几次 186 free(mg->a[i]); 187 free(mg->a); 188 printf("邻接矩阵已经成功撤销！\n"); 189 return ; 190 } 191 BOOL Find_M_E( MGraph *mg,int u,int v ) //邻接矩阵的边的搜索,u为出发点，v为被指向点 192 { 193 if( u<0||u>=mg->n||v<0||v>=mg->n||u==v ) //增强代码的健壮性，判断错误输出 194 { 195 printf("请输入正确的 你所要找查的边的两端的结点值！\n"); 196 return FALSE; 197 } 198 if( mg->a[u][v]==mg->noEdge ) //如果 u→v 没有边 199 return FALSE; 200 else 201 return TRUE; 202 } 203 void Insert_M_E( MGraph *mg,int u,int v,ElemType x ) //邻接矩阵的边的插入 204 { 205 if( u<0||u>=mg->n||v<0||v>=mg->n||u==v ) //增强代码的健壮性，判断错误输出 206 { 207 printf("请输入正确的 你所要找插入的边的两端的结点值！\n"); 208 return ; 209 } 210 if( Find_M_E(mg,u,v) ) //如果该边的已经有了，则不能在进行重复插入操作 211 { 212 printf("该边已经在图中存在了，请勿重复插入！\n"); 213 } 214 else 215 { 216 mg->a[u][v]=x; //执行插入操作 217 mg->e++; 218 } 219 } 220 BOOL Delete_M_E( MGraph *mg,int u,int v ) //邻接矩阵的边的删除 221 { 222 if( u<0||u>=mg->n||v<0||v>=mg->n||u==v ) //增强代码的健壮性，判断错误输出 223 { 224 printf("请输入正确的 你所要找删除的边的两端的结点值！\n"); 225 return FALSE; 226 } 227 if( !Find_M_E(mg,u,v) ) //如果该边的在图中本身就没有，则不能在进行删除操作 228 { 229 printf("该边在图中不存在！\n"); 230 return FALSE; 231 } 232 else 233 { 234 mg->a[u][v]=mg->noEdge; 235 mg->e--; 236 return TRUE; 237 } 238 } 239 240 //以上述邻接矩阵为存储结构，编写程序，实现图的深度优先遍历、宽度优先遍历 241 void Dfs_M( MGraph *mg,int u ) //u为开始遍历的起点 242 { 243 int i=0; 244 if( !vis_m[u] ) 245 { 246 printf("%3d ",u); 247 load[cnt++]=u; 248 vis_m[u]=1; //编号为u的结点 的标记改变 249 } 250 while( i<mg->n ) 251 { 252 if( !vis_m[i]&&mg->a[u][i]!=mg->noEdge&&u!=i ) //如果u→编号为i的结点有边，并且结点i未被“走过”（即标记过） 253 { 254 Dfs_M( mg,i ); 255 } 256 i++; 257 } 258 } 259 void Bfs_M( MGraph *mg,int u ) //u为开始遍历的起点 260 { 261 int i; 262 Queue q; 263 Create_Q(&q,mg->n); //创建队列，最大容量要+1才行 264 vis_m[u]=1; //编号为u的结点 的标记改变 265 Push_Q(&q,u); //编号为u的结点 压入 266 while( !IsEmpty_Q(&q) ) //只要队列还不为空，就继续执行 267 { 268 Front_Q(&q,&u); //将队头元素传给u 269 printf("%3d ",u); //打印 270 load[cnt++]=u; 271 DeQueue_Q(&q); //将队头元素去掉 272 for( i=0;i<mg->n;i++ ) 273 { 274 if( !vis_m[i]&&mg->a[u][i]!=mg->noEdge&&u!=i ) //如果u→编号为i的结点有边，并且结点i未被“走过”（即标记过） 275 { 276 Push_Q(&q,i); 277 vis_m[i]=1; //标记改变 278 } 279 } 280 } 281 Destroy_Q(&q); //撤销队列 282 return ; 283 } 284 285 void Init_L( LGraph *lg,int size ) //x表示顶点数的意思 286 { 287 int i; 288 lg->n=size; 289 lg->e=0; //刚开始图是没有边的 290 lg->a=(ENode**)malloc(lg->n*sizeof(ENode*)); 291 for( i=0;i<lg->n;i++ ) 292 lg->a[i]=NULL; //将指针数组a置空 293 return ; 294 } 295 void Destroy_L( LGraph *lg ) 296 { 297 ENode *front,*cur; //指针cur用于释放，指针front用于遍历 298 int i; 299 for( i=0;i<lg->n;i++ ) 300 { 301 front=lg->a[i]; //指针front指向顶点i的单链表的第一个边结点 302 cur=front; 303 while( cur ) 304 { 305 front=front->nextArc; 306 free(cur); 307 cur=front; 308 } 309 } 310 free( lg->a ); //释放一维指针数组a的存储空间 311 return ; 312 } 313 BOOL Find_L_E( LGraph *lg,int u,int v ) //邻接表 边的搜索 314 { 315 ENode *fp=lg->a[u]; 316 if( u<0||u>=lg->n||v<0||v>=lg->n||u==v ) //增强代码的健壮性，判断错误输出 317 { 318 printf("请输入正确的 你所要找查的边的两端的结点值！\n"); 319 return FALSE; 320 } 321 while( fp&&fp->adjVex!=v ) 322 { 323 fp=fp->nextArc; 324 } 325 if( fp!=NULL ) //若找到了这条边 326 return TRUE; 327 else 328 return FALSE; 329 } 330 void Insert_L_E( LGraph *lg,int u,int v,ElemType w ) 331 { 332 ENode *fp; //front作为前驱指针，指向插入位置的前一个结点 333 if( u<0||u>=lg->n||v<0||v>=lg->n||u==v ) //增强代码的健壮性，判断错误输出 334 { 335 printf("请输入正确的 你所要找插入的边的两端的结点值！\n"); 336 return ; 337 } 338 if( Find_L_E(lg,u,v) ) //如果在图中找到这条边 339 { 340 printf("该边已经在图中存在了，请勿重复插入！\n"); 341 return ; 342 } 343 else 344 { 345 fp=(ENode*)malloc(sizeof(ENode)); //为新的边结点分配存储空间 346 fp->adjVex=v; 347 fp->w=w; 348 fp->nextArc=lg->a[u]; //将新的边结点插入单链表的最前面 349 lg->a[u]=fp; 350 lg->e++; //细节 351 } 352 } 353 BOOL Delete_L_E( LGraph *lg,int u,int v ) 354 { 355 ENode *front,*fp; //一般情况下，前驱结点front指向删除结点fp 的前一个结点 356 if( u<0||u>=lg->n||v<0||v>=lg->n||u==v ) //增强代码的健壮性，判断错误输出 357 { 358 printf("请输入正确的 你所要删除的边的两端的结点值！\n"); 359 return FALSE; 360 } 361 front=NULL; 362 fp=lg->a[u]; 363 while( fp&&fp->adjVex!=v ) //找查待删除的边是否存在 364 { 365 front=fp; 366 fp=fp->nextArc; 367 } 368 if( fp==NULL ) //指针fp为空，说明该边不存在 369 { 370 printf("你所要删除的边在图中不存在！\n"); 371 return FALSE; 372 } 373 if( front==NULL ) //前驱结点为空，说明，要删除的边在表头 374 { 375 lg->a[u]=fp->nextArc; 376 free(fp); 377 } 378 else //否则要删除的边不在表头 379 { 380 front->nextArc=fp->nextArc; 381 free(fp); 382 } 383 lg->e--; //细节 384 return TRUE; 385 } 386 387 /* 以上述邻接表为存储结构，编写程序，实现图的深度、宽度优先遍历 */ 388 void Dfs_L( LGraph *lg,int u ) //u为开始遍历的起点 389 { 390 ENode *fp; 391 printf("%3d ",u); 392 load[cnt++]=u; 393 vis_l[u]=1; //标记改变 394 for( fp=lg->a[u];fp;fp=fp->nextArc ) 395 { 396 if( !vis_l[fp->adjVex] ) //只要下一结点未被访问过 397 { 398 Dfs_L(lg,fp->adjVex); 399 } 400 } 401 return ; 402 } 403 void Bfs_L( LGraph *lg,int u ) 404 { 405 ENode *fp; //移动指针，在邻接表上移动 406 Queue q; 407 Create_Q(&q,lg->n); 408 Push_Q(&q,u); //将编号为u的结点入队 409 while( !IsEmpty_Q(&q) ) //只要队列还不为空，就继续执行 410 { 411 Front_Q(&q,&u); 412 DeQueue_Q(&q); 413 printf("%3d ",u); //打印 414 load[cnt++]=u; 415 vis_l[u]=1; //标记改变 416 for( fp=lg->a[u];fp;fp=fp->nextArc ) 417 { 418 if( !vis_l[fp->adjVex] ) //只要与u连接的结点未被访问过，就让他们入队 419 { 420 Push_Q(&q,fp->adjVex); 421 vis_l[fp->adjVex]=1; //标记改变 422 } 423 } 424 } 425 Destroy_Q(&q); //撤销队列 426 return ; 427 } 428 429 void Print_M( MGraph *mg ) //邻接矩阵打印 430 { 431 int i,j; 432 printf("\n\n该图的邻接矩阵为：\n"); 433 for( i=0;i<mg->n;i++ ) 434 { 435 for( j=0;j<mg->n;j++ ) 436 { 437 if( mg->a[i][j]!=mg->noEdge ) 438 printf("%d\t",mg->a[i][j]); 439 else 440 printf("*\t"); 441 } 442 printf("\n"); 443 } 444 printf("（注：“*”代表结点u到结点v没有边）\n"); 445 } 446 void Print_L( LGraph *lg ) //邻接表打印 447 { 448 ENode *fp; //移动指针，在邻接表上移动 449 int i; 450 printf("\n\n该图的邻接表为：（注：“ |2| 1-50 ”代表的意思是，表头结点2，有指向结点1的边，边的值为50）\n"); 451 for( i=0;i<lg->n;i++ ) 452 { 453 printf("表头结点: |%d|",i); 454 for( fp=lg->a[i];fp;fp=fp->nextArc ) 455 { 456 printf("%3d-%-3d ",fp->adjVex,fp->w); 457 } 458 printf("\n"); 459 } 460 } 461 void Print_Indegree_1( MGraph *mg ) //（邻接矩阵）每个结点的入度打印，load[]为遍历路径 462 { 463 int i,j,ans; 464 int *fp; 465 for( i=0;i<cnt;i++ ) 466 { 467 ans=0; 468 for( j=0;j<cnt;j++ ) 469 { 470 fp=&(mg->a[j][ load[i] ]); //以第一排的每个元素 作起始地址 进行向下搜索 471 if( *fp!=0&&*fp!=mg->noEdge ) 472 ans++; 473 } 474 printf("%3d ",ans); 475 } 476 } 477 void Print_Outdegree_1( MGraph *mg ) //（邻接矩阵）每个结点的出度打印，load[]为遍历路径 478 { 479 int i,j,ans; //ans表示结点度数 480 int *fp; 481 for( i=0;i<cnt;i++ ) 482 { 483 ans=0; 484 fp=mg->a[ load[i] ]; 485 for( j=0;j<cnt;j++ ) 486 { 487 if( *fp!=0&&*fp!=mg->noEdge ) 488 ans++; 489 fp++; //指针向右移动 490 } 491 printf("%3d ",ans); 492 } 493 } 494 void Print_Indegree_2( LGraph *lg ) //（邻接表）每个结点的入度打印，load[]为遍历路径 495 { 496 int i; 497 ENode *fp; 498 int *in_degree=(int*)malloc(lg->n*sizeof(int)); //用数组in_degree[]记录每个结点的入度 499 for( i=0;i<lg->n;i++ ) //初始化 500 in_degree[i]=0; 501 for( i=0;i<lg->n;i++ ) 502 { 503 for( fp=lg->a[ load[i] ];fp;fp=fp->nextArc ) 504 { 505 in_degree[fp->adjVex]++; //编号为 fp->adjVex 的结点的编号 的入度加1 506 } 507 } 508 for( i=0;i<lg->n;i++ ) 509 { 510 printf("%3d ",in_degree[ load[i] ] ); 511 } 512 } 513 void Print_Outdegree_2( LGraph *lg ) //（邻接表）每个结点的出度打印，load[]为遍历路径 514 { 515 int i,ans; //ans表示结点度数 516 ENode *fp; 517 for( i=0;i<lg->n;i++ ) 518 { 519 ans=0; 520 for( fp=lg->a[ load[i] ];fp;fp=fp->nextArc ) 521 { 522 ans++; 523 } 524 printf("%3d ",ans); 525 } 526 } 527 528 void Bfs_Judge( LGraph *lg,int u ) //用于判断是否是强连通图的辅助函数 529 { 530 ENode *fp; //移动指针，在邻接表上移动 531 Queue q; 532 Create_Q(&q,lg->n); 533 Push_Q(&q,u); //将编号为u的结点入队 534 while( !IsEmpty_Q(&q) ) //只要队列还不为空，就继续执行 535 { 536 Front_Q(&q,&u); 537 DeQueue_Q(&q); 538 cnt++; 539 vis_l[u]=1; //标记改变 540 for( fp=lg->a[u];fp;fp=fp->nextArc ) 541 { 542 if( !vis_l[fp->adjVex] ) //只要与u连接的结点未被访问过，就让他们入队 543 { 544 Push_Q(&q,fp->adjVex); 545 vis_l[fp->adjVex]=1; //标记改变 546 } 547 } 548 } 549 Destroy_Q(&q); //撤销队列 550 return ; 551 } 552 BOOL Judge_QiangLiTongTu( LGraph *lg ) //判断是否是强连通图（针对于有向图） 553 { 554 int i; 555 for( i=0;i<lg->n;i++ ) 556 { 557 Clear_Flag(); //标记清零操作 558 Bfs_Judge(lg,i); 559 if( cnt!=lg->n ) //若任意一对顶点之间都存在路径，则以某一结点为起点宽度遍历后，路径长度cnt应该为lg->n (注：cnt为全局变量) 560 return FALSE; //不是连通图,返回FALSE 561 } 562 return TRUE; //每个结点都满足，这说明是强连通图 563 } 564 565 void In_Degree_Helper( int *in_degree,LGraph *lg ) 566 { 567 ENode *fp; 568 int i; 569 for( i=0;i<lg->n;i++ ) 570 in_degree[i]=0; //先初始化 571 for( i=0;i<lg->n;i++ ) 572 { 573 for( fp=lg->a[i];fp;fp=fp->nextArc ) 574 { 575 in_degree[ fp->adjVex ]++; //编号为fp->adjVex的结点的入度加1 576 } 577 } 578 } 579 void TopSort( LGraph *lg ) //拓扑排序 580 { 581 ENode *fp; 582 int *in_degree,i,top_node; 583 Stack sta; 584 Create_S(&sta,lg->n); 585 in_degree=(int*)malloc(lg->n*sizeof(int)); 586 In_Degree_Helper(in_degree,lg); //初始化该数组 587 for( i=0;i<lg->n;i++ ) 588 { 589 if( in_degree[i]==0 ) 590 Push_S(&sta,i); 591 } 592 while( !IsEmpty_S(&sta) ) 593 { 594 Top_S(&sta,&top_node); 595 Pop_S(&sta); //这条语句不能放到for循环下面！不然栈里的元素不能被覆盖，要出大问题 596 load[cnt++]=top_node; 597 for( fp=lg->a[top_node];fp;fp=fp->nextArc ) 598 { 599 in_degree[fp->adjVex]--; //更新编号为fp->adjVex的结点的入度 600 if( in_degree[fp->adjVex]==0 ) //并判断编号为fp->adjVex的结点入度是否为零，是则放入栈 601 Push_S(&sta,fp->adjVex); 602 } 603 } 604 if( cnt==lg->n ) 605 { 606 printf("\n该图的拓扑排序为："); 607 for( i=0;i<lg->n;i++ ) 608 printf("%3d ",load[i]); 609 } 610 else 611 { 612 printf("该图中存在有向回路，不能拓扑排序。\n"); 613 } 614 } 615 616 /* 617 编写程序，实现智能交通中的最佳路径选择：设有n个地点，编号为0~n-1，m条路径的起点、终点 618 和代价由用户输入提供，采用上述邻接表为存储结构，寻找最佳路径方案（花费时间最少） 619 */ 620 void DFS_PLF( LGraph *lg,Stack *s,int v,int Time ) //v为终点，起点已经装进了栈里了 621 { 622 ENode *fp; //fp为移动指针，在邻接表上移动 623 int t,i; 624 Top_S(s,&t); 625 if( t==v&&Time<Min_Time ) //终止条件：栈顶元素为终点。并且所花时间 比 以前记录的所花最少时间还要小 626 { 627 Min_Time=Time; 628 for( i=0;i<=s->top;i++ ) 629 path[i]=s->element[i]; //记录当前最佳路径 630 count=i; 631 return ; 632 } 633 for( fp=lg->a[t];fp;fp=fp->nextArc ) 634 { 635 if( !vis_l[fp->adjVex] ) //如果 编号为t的结点指向的 编号为fp->adjVex的结点未被访问过 636 { 637 Push_S(s,fp->adjVex); //入栈 638 vis_l[fp->adjVex]=1; //标记改变 639 DFS_PLF(lg,s,v,Time+fp->w); //时间代价要加fp->w 640 vis_l[fp->adjVex]=0; //标记回溯 641 Pop_S(s); //出栈(回溯) 642 } 643 } 644 } 645 void Prefect_Load_Find( LGraph *lg,int u,int v ) //最佳路径找查(花费时间最少),思路：深度优先搜索 646 { 647 Stack s; 648 int i; 649 Create_S(&s,lg->n); 650 Push_S(&s,u); 651 vis_l[u]=1; //标记改变，编号为u的结点已被访问 652 DFS_PLF( lg,&s,v,0 ); 653 printf("从 编号为%d的起点 到 编号为%d的终点的最佳路径(花费时间最少)为：",u,v); 654 for( i=0;i<count;i++ ) 655 printf("%d ",path[i]); 656 printf("\n所花费的时间为：%d\n",Min_Time); 657 } 658 void Experiment_5() //入口函数：智能交通的最佳路径的实现(花费时间最少) 659 { 660 int n; //n个地点 ，编号为0~n-1 661 int m; //m条路径 662 int u,v,w; //路径的起点u、终点v和代价w 663 int i; 664 LGraph lg; 665 Clear_Flag(); //标记清零操作 666 printf("请分别输入地点个数n和路径个数m："); 667 scanf("%d%d",&n,&m); 668 Init_L(&lg,n); //初始化邻接表，n个顶点 669 i=m; 670 while( i>0 ) 671 { 672 printf("请分别输入第%d条路径的起点、终点和时间代价：",m-i+1); 673 scanf("%d%d%d",&u,&v,&w); 674 Insert_L_E(&lg,u,v,w); 675 i--; 676 } 677 printf("请输入你想找哪两个结点的最佳路径：（分别输入起点和终点）"); 678 scanf("%d%d",&u,&v); 679 if( u<0||u>=lg.n||v<0||v>=lg.n||u==v ) //增强代码的健壮性，判断错误输出 680 { 681 printf("请输入正确的 你所要找查最佳路径的起点和终点！\n"); 682 return ; 683 } 684 Prefect_Load_Find( &lg,u,v ); 685 return ; 686 } 687 688 void M_Grapg() //入口函数：邻接矩阵的实现(额外包含矩阵打印出、入度计算) 689 { 690 int i,u,v,w,n; 691 MGraph mg; 692 printf("请输入该图的结点数："); 693 scanf("%d",&n); 694 Init_M(&mg,n,-9999); 695 printf("输入u为-999时结束。\n"); 696 while( 1 ) 697 { 698 scanf("%d%d%d",&u,&v,&w); 699 if( u==-999 ) 700 break; 701 Insert_M_E(&mg,u,v,w); 702 } 703 Clear_Flag(); //标记清零操作 704 printf("\n矩阵的 深度遍历 结果为：\n"); 705 printf("结点 "); 706 for( i=0;i<mg.n;i++ ) 707 { 708 if(!vis_m[i]) 709 Dfs_M(&mg,i); 710 } 711 printf("\n入度 "); 712 Print_Indegree_1(&mg); //每个结点的入度打印 713 printf("\n出度 "); 714 Print_Outdegree_1(&mg); //每个结点的出度打印 715 Print_M(&mg); //邻接矩阵打印51 716 printf("\n请分别输入需要删除的边的两端的结点值："); 717 scanf("%d%d",&u,&v); 718 if( !Delete_M_E(&mg,u,v) ) 719 return ; 720 printf("删除边后矩阵的 宽度遍历 结果为：\n"); 721 printf("结点 "); 722 Clear_Flag(); //标记清零操作 723 for( i=0;i<mg.n;i++ ) 724 { 725 if(!vis_m[i]) 726 Dfs_M(&mg,i); 727 } 728 printf("\n入度 "); 729 Print_Indegree_1(&mg); //每个结点的入度打印 730 printf("\n出度 "); 731 Print_Outdegree_1(&mg); //每个结点的出度打印 732 printf("\n"); 733 Print_M(&mg); //邻接矩阵打印 734 Destroy_M(&mg); 735 } 736 void L_Graph() //入口函数：邻接表的实现(额外包含强连通图判断、邻接表打印、拓扑排序) 737 { 738 int i,u,v,w,count=0,n; //n为结点数 739 LGraph lg; 740 printf("请输入该图的结点数："); 741 scanf("%d",&n); 742 Init_L(&lg,n); 743 printf("输入u为-999时结束。\n"); 744 while( 1 ) 745 { 746 scanf("%d%d%d",&u,&v,&w); 747 if( u==-999 ) 748 break; 749 Insert_L_E(&lg,u,v,w); 750 } 751 Clear_Flag(); //标记清零操作 752 printf("\n矩阵的 深度遍历 结果为：\n结点 "); 753 for( i=0;i<lg.n;i++ ) 754 { 755 if( !vis_l[i] ) 756 Dfs_L(&lg,i); 757 } 758 printf("\n入度 "); 759 Print_Indegree_2(&lg); //（邻接表）每个结点的入度打印 760 printf("\n出度 "); 761 Print_Outdegree_2(&lg); //（邻接表）每个结点的出度打印 762 Print_L(&lg); //打印邻接表 763 if( Judge_QiangLiTongTu(&lg) ) 764 printf("\n该图 是 强连通图。\n"); 765 else 766 printf("\n该图 不是 强连通图。\n"); 767 Clear_Flag(); //标记清零操作 768 TopSort(&lg); 769 printf("\n\n请分别输入需要删除的边的两端的结点值："); 770 scanf("%d%d",&u,&v); 771 if( !Delete_L_E(&lg,u,v) ) 772 return ; 773 Clear_Flag(); //标记清零操作 774 printf("删除后的图的 宽度遍历 为：\n结点 "); 775 for( i=0;i<lg.n;i++ ) 776 { 777 if( !vis_l[i] ) 778 Dfs_L(&lg,i); 779 } 780 printf("\n入度 "); 781 Print_Indegree_2(&lg); //（邻接表）每个结点的入度打印 782 printf("\n出度 "); 783 Print_Outdegree_2(&lg); //（邻接表）每个结点的出度打印 784 Print_L(&lg); //打印邻接表 785 Destroy_L(&lg); 786 } 787 788 void Main_Menu() //主菜单打印 789 { 790 printf("+--------------------------------------------------------------------------+\n"); 791 printf("| 主菜单 |\n"); 792 printf("| 1、邻接矩阵的实现(额外包含矩阵打印出、入度计算) |\n"); 793 printf("| 2、邻接表的实现(额外包含强连通图判断、邻接表打印、拓扑排序) |\n"); 794 printf("| 3、智能交通的最佳路径的实现(花费时间最少) |\n"); 795 printf("| 0、退出 |\n"); 796 printf("+--------------------------------------------------------------------------+\n"); 797 } 798 799 int main() 800 { 801 int choice; 802 do 803 { 804 system("cls"); 805 Main_Menu(); 806 printf("请输入你的选择:\n"); 807 scanf("%d",&choice); 808 switch(choice) 809 { 810 case 1: M_Grapg(); //邻接矩阵的实现(额外包含矩阵打印出、入度计算) 811 break; 812 case 2: L_Graph(); //邻接表的实现(额外包含强连通图判断、邻接表打印、拓扑排序) 813 break; 814 case 3: Experiment_5(); //智能交通的最佳路径的实现(花费时间最少) 815 break; 816 } 817 system("pause"); 818 }while(choice); 819 return 0; 820 }
如果您觉得不错的话，点个赞，编者再接再厉~ Thanks~ ^_^
版权声明：本文为Wang-dou-dou原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。