关于图的简单路径和最短路径

我的蜡笔丢了

1. #include<stdio.h>
   
2. #include<malloc.h>
   
3. #include<string.h>
   
4. #define MAXV 100                        //最大顶点个数
   
5. #define INF 32767                        //INF表示无穷大
   
6. typedef struct{
   
7.         int no;                                        //顶点编号
   
8.         int info;                                //顶点的其他信息
   
9.         char name[60];                       
   
10. }VertexType;                                //顶点类型
    
11. 
    
12. typedef struct{                                //图的定义
    
13.         int edges[MAXV][MAXV];        //邻接矩阵
    
14.         int n,e;                                //顶点数，边数
    
15.         VertexType vexs[MAXV];        //存放顶点信息
    
16. }MGraph;
    
17. //以下定义邻接表类型
    
18. typedef struct ANode                   //边的节点结构类型
    
19. {        int adjvex;                      //该边的终点位置
    
20. struct ANode *nextarc;                 //指向下一条边的指针
    
21. int info;                                  //该边的相关信息,这里用于存放权值
    
22. } ArcNode;
    
23. 
    
24. typedef struct Vnode                      //邻接表头结点的类型
    
25. {        int data;                                        //顶点信息
    
26. char name[60];
    
27. ArcNode *firstarc;                     //指向第一条弧
    
28. } VNode;
    
29. 
    
30. typedef VNode AdjList[MAXV];        //AdjList是邻接表类型
    
31. typedef struct
    
32. {        AdjList adjlist;                 //邻接表
    
33. int n,e;                         //图中顶点数n和边数e
    
34. } ALGraph;                           //图的邻接表类型
    
35. int visited[MAXV];
    
36. //********************************************************
    
37. //********************************************************
    
38. void MatToList(MGraph g,ALGraph *&G)        //将邻接矩阵g转换成邻接表G
    
39. {
    
40.         int i,j;                                                        //n为顶点数
    
41.         ArcNode *p;
    
42.         G=(ALGraph *)malloc(sizeof(ALGraph));
    
43.         for (i=0;i<g.n;i++)                                        //给邻接表中所有头结点的指针域置初值
    
44.                 G->adjlist[i].firstarc=NULL;
    
45.         for (i=0;i<g.n;i++)                                        //检查邻接矩阵中每个元素
    
46.                 for (j=g.n-1;j>=0;j--)
    
47.                         if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)                                //邻接矩阵的当前元素不为0
    
48.                         {   
    
49.                                 p=(ArcNode *)malloc(sizeof(ArcNode));        //创建一个结点*p
    
50.                                 p->adjvex=j;
    
51.                                 p->info=g.edges[i][j];
    
52.                                 p->nextarc=G->adjlist[i].firstarc;                //将*p链到链表后
    
53.                                 G->adjlist[i].firstarc=p;
    
54.                         }
    
55.                         for(i=0;i<g.n;i++)
    
56.                                 strcpy(G->adjlist[i].name,g.vexs[i].name);
    
57.                         G->n=g.n;G->e=g.e;
    
58. }
    
59. 
    
60. void DispAdj(ALGraph *G)                //输出邻接表G
    
61. {
    
62.         int i;
    
63.         ArcNode *p;
    
64.         for (i=0;i<G->n;i++)
    
65.         {
    
66.                 p=G->adjlist[i].firstarc;
    
67.                 printf("%3d: ",i);
    
68.                 while (p!=NULL)
    
69.                 {
    
70.                         printf("%3d(%d)",p->adjvex,p->info);
    
71.                         p=p->nextarc;
    
72.                 }
    
73.                 printf("\n");
    
74.         }
    
75. }
    
76. 
    
77. void FindPath(ALGraph *G,int u,int v,int path[],int d)//G用邻接表存储，输出图G从顶点u到v的所有简单路径
    
78. {        //d表示path中的路径长度，初始为-1；
    
79.         int w,i;
    
80.         ArcNode *p;
    
81.         d++;path[d]=u;                //路径长度d增1，顶点u加入到数组path中
    
82.         visited[u]=1;                //置顶点u已经访问
    
83.         if(u==v && d>=1)//找到一条简单路径就输出存储顶点的数组path
    
84.         {                               
    
85.                 for(i=0;i<d;i++)
    
86.                 {
    
87.                         printf("%2s→",G->adjlist[path[i]].name);
    
88.                 }
    
89.                 printf("%2s",G->adjlist[path[i]].name);
    
90.                 printf("\n");   
    
91.         }
    
92.                 p=G->adjlist[u].firstarc;        //p指向顶点u的第一个相邻点
    
93.                 while(p!=NULL)
    
94.                 {
    
95.                         w=p->adjvex;                        //w为顶点u的相邻顶点
    
96.                         if(visited[w]==0){                //若顶点w未访问，递归访问它
    
97.                                 FindPath(G,w,v,path,d);
    
98.                         }
    
99.                         p=p->nextarc;                //p指向顶点u的下一个相邻点
    
100.                 }
     
101.                 visited[u]=0;                //恢复环境，使该顶点可重新使用
     
102. }
     
103. void main(){
     
104.         int path[MAXV],u=1,v=4,d=-1;
     
105.         int i,j;
     
106.         MGraph g;
     
107.         ALGraph *G;
     
108.         g.n=5;
     
109.         g.e=8;
     
110.         int A[MAXV][MAXV]={
     
111.                 {0,3,0,5,4},{3,0,5,4,0},{0,5,0,2,1},
     
112.                 {5,4,2,0,1},{4,0,1,1,0}};
     
113.                 for(i=0;i<g.n;i++)
     
114.                         for(j=0;j<g.n;j++)
     
115.                                 g.edges[i][j]=A[i][j];
     
116.                         for(i=0;i<g.n;i++)
     
117.                                 g.vexs[i].no=i;
     
118.                         strcpy(g.vexs[0].name,"正门");
     
119.                         strcpy(g.vexs[1].name,"教学楼");
     
120.                         strcpy(g.vexs[2].name,"英东楼");
     
121.                         strcpy(g.vexs[3].name,"学生宿舍");
     
122.                         strcpy(g.vexs[4].name,"艺术学院");                               
     
123.                         MatToList(g,G);
     
124.                         for(i=0;i<g.n;i++)
     
125.                                 visited[i]=0;
     
126.                         DispAdj(G);
     
127.                         FindPath(G,u,v,path,d);
     
128. }
     

复制代码

我这是带权无向图，我想在简单的路径后面把边的权值和算出来，但老不错，求各位大神！
还有 关于最短路径的求法，到底需要怎么求？小甲鱼的视频看不懂不会用？

我的蜡笔丢了

有人吗？求救
我这是带权无向图，我想在简单的路径后面把边的权值和算出来，但老不错，求各位大神！
还有 关于最短路径的求法，到底需要怎么求？小甲鱼的视频看不懂不会用？

jerryxjr1220

参考我的“带权重的最优路径解法”的帖子吧
http://bbs.fishc.com/thread-81073-1-1.html