qq_58705390
2021-06-09 21:02
采纳率: 90%
浏览 16

数据结构,用C语言写,谢谢!

(1)图的邻接矩阵定义及实现:定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、深度优先遍历、计算并输出图中每个顶点的度等基本操作实现函数。以下两图为例,建立一个验证操作实现的主函数进行测试。                                           

 

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • 刘一哥GIS 2021-06-09 23:18
    已采纳

    #include<stdio.h>#include<stdlib.h>#define VLENGTH 10struct Graph{ int **pA; char **pV; int num; int *Visited; int Count; int *Low;};struct Graph *GraphInit(int n){ int i; struct Graph *g; if(n<=0) return NULL; g=(struct Graph *)malloc(sizeof(struct Graph)); g->num=n; g->pA=(int **)malloc(sizeof(int )*n); g->pV=(char **)malloc(sizeof(char)*n); for(i=0;i<n;i++) { g->pA[i]=(int *)malloc(sizeof(int)*n); g->pV[i]=(char *)malloc(sizeof(char)*VLENGTH); } g->Visited=(int *)malloc(sizeof(int )*n); g->Low=(int *)malloc(sizeof(int )*n); for(i=0;i<n;i++) { g->Visited[i]=0; g->Low[i]=0; } g->Count=0; return g;}struct Graph * GraphCreat(char FileName[20]){ int i,j,n; FILE *fp,*fopen(); struct Graph *G; fp=fopen(FileName,"r"); if(fp==NULL) return NULL; fscanf(fp,"%d",&n); G=GraphInit(n); for(i=0;i<n;i++) fscanf(fp,"%s",G->pV[i]); for(i=0;i<n;i++) for(j=0;j<n;j++) fscanf(fp,"%d",&G->pA[i][j]); fclose(fp); return G;}int GraphFirstAdj(struct Graph *G,int v){ int i; if(G==NULL) return -1; if(v<0||v>G->num) return -2; for(i=0;i<G->num;i++) if(G->pA[v][i]!=0) return i; return 0;}int GraphNextAdj(struct Graph *G,int v,int w){ int i; if(G==NULL) return -1; if(v<0||v>G->num) return -2; if(w<0||w>G->num) return -3; for(i=w;i<G->num;i++) if(G->pA[v][i]!=0) return i; return 0;}void GraphDestory(struct Graph *G){ int i; if(G==NULL) return; for(i=0;i<G->num;i++) { free(G->pA[i]); free(G->pV[i]); } free(G);}void DFS(struct Graph *G,int v){ int w,min; if(G==NULL) return; if(v<0||v>G->num) return; G->Visited[v]=min=++G->Count; printf("%3s",G->pV[v]); for(w=G->num-1;w>=0;w--) if(G->pA[v][w]!=0) { if(G->Visited[w]==0) { DFS(G,w); if(G->Low[w]<min) min=G->Low[w]; //if(G->Low[w]>=G->Visited[v]) printf("%3s\n",G->pV[v]); } else if(G->Visited[w]<min) min=G->Visited[w]; } G->Low[v]=min; }void DFSTraverse(struct Graph *G){ int i; if(G==NULL) return; for(i=0;i<G->num;i++) if(G->Visited[i]==0) DFS(G,i); printf("\n");}main(){ int i,j; struct Graph *G; G=GraphCreat("P719G5.txt"); for(i=0;i<G->num;i++) printf("%s ",G->pV[i]); printf("\n"); for(i=0;i<G->num;i++) { for(j=0;j<G->num;j++) printf("%d ",G->pA[i][j]); printf("\n"); } printf("遍历结果\n"); DFSTraverse(G); printf("访问次序\n"); for(i=0;i<G->num;i++) printf("%3s",G->pV[i]); printf("\n"); for(i=0;i<G->num;i++) printf("%3d",G->Visited[i]); printf("\n"); for(i=0;i<G->num;i++) printf("%3d",G->Low[i]); printf("\n");}

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题