看来群的作用真的很大啊
刚才为了一下,发现自己的抽象思维能力简直为0
总以为没有办法处理集合,然后群里面的人说可以用bool 数组,然后研究了一下,果然可以
算法描述的时候说集合的并啊,减啊,在c语言里,用个bool数组就可以,
刚开始初始化为false
然后进来一个true一个
发现还是自己写程序容易理解,个别的知识点再问别人,刚才搜一下别人怎么实现的,那个长啊,根本不愿意读
也不理解。程序还是自己写的,自己理解啊
/* author :lingling date:2011-10-8 description: 有向图邻接矩阵的建立,连接矩阵的深度优先遍历,dijkstral求一个顶点到其余各顶点的最短距离 */ #include <stdio.h> #include <stdlib.h> #define MaxVertexNum 100 typedef int VertexType ; //由用户定义顶点类型 typedef int EdgeType; //由用户定义边上的权值类型 typedef struct { VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int n,e; }MGrap; bool visited[MaxVertexNum]; void createMGrap(MGrap*); void DFSTraverse(MGrap* ); void DFS(MGrap* , int ); void Dijkstra(MGrap* ,int,int[]); void main() { freopen("input1.txt","r",stdin); MGrap *G =(MGrap*)malloc(sizeof(MGrap)); createMGrap(G); for (int i=0;i<G->n;i++) { for(int j=0;j<G->n;j++) { printf("%-8d",G->edges[i][j]); } printf("\n"); } DFSTraverse(G); int D[5]; Dijkstra(G,0,D); } void createMGrap(MGrap* G) { int i,j,k,w=0,p; // printf("输入顶点数和边数\n"); scanf("%d,%d",&G->n,&G->e); for ( p=0;p<G->n;p++) { //fflush(stdin); //清除缓冲区 // printf("输入顶点信息"); scanf("%d",&G->vexs[p]); } // printf("邻接矩阵初始化\n"); for ( i=0;i<G->n;i++) for ( j=0;j<G->n;j++) G->edges[i][j]=1000; for ( k=0;k<G->e;k++) { //printf("读入两个顶点(i,j)之间边的值w\n"); scanf("%d,%d,%d",&i,&j,&w); G->edges[i][j]=w; // G->edges[j][i]=w; // printf("读入的数i=%d,j=%d,w=%d\n",i,j,w); } } void DFSTraverse(MGrap* G) { int i; for (i=0;i<G->n;i++) visited[i]=false; printf("深度优先遍历序列:\n"); for (i=0;i<G->n;i++) //确保每一个顶点都遍历过,如果有孤立的也可以 if (!visited[i]) { DFS(G,i); } printf("\n"); } void DFS(MGrap* G, int i) { printf("%d->",G->vexs[i]); //fflush(stdout); visited[i]=true; for (int j=0;j<G->n;j++) if (G->edges[i][j]==1&&!visited[j]) DFS(G,j); } void Dijkstra(MGrap* G ,int s,int D[]) { int k=0; D[s]=0; for (int i=0;i<G->n;i++) visited[i]=false; visited[s]=true; //初始化最短距离一维数组 for (int i=0;i<G->n;i++) if (!visited[i]) D[i]=G->edges[s][i]; //修改最短距离一维数组 for (int i=0;i<G->n-1;i++) { //找出最小的值,下次找的时候不包括已经找到的 int min =1000; for (int j=0;j<G->n;j++) { if (!visited[j]&&D[j]<min) { min=D[j]; k=j; } } visited[k]=true; printf("最小值的下标%d\n",k); //修改剩余点的距离值 for (int j=0;j <G->n;j++) if (!visited[j]&& D[j]>D[k]+G->edges[k][j] ) D[j]= D[k]+G->edges[k][j]; } for (int i=0;i<G->n;i++) { printf("s到顶点%d的最短距离%d\n",i,D[i]); } printf("\n"); }
最后这部分是这个算法,其余的部分还是以前写的,在这个基础上写的,要不然也不能随便一个算法就能执行的啊
结果
直观图