#include<stdio.h>
#include<stdlib.h> #include<conio.h> #include<string.h> int visited[10];/*访问标志数组*/ typedef struct ArcCell{ int adj;/*顶点关系类型,用1表示相邻,0表示不相邻*/ }ArcCell,**AdjMatrix;/*邻接矩阵*/ typedef struct type{ char data[3];/*顶点值*/ struct type *next;/*顶点的下一个指针*/ }VertexType; typedef struct{ VertexType *vexs;/*顶点向量*/ AdjMatrix arcs;/*邻接矩阵*/ int vexnum,arcnum;/*图的顶点数和边数*/ }MGraph; void InitGraph(MGraph *G)/*初始图*/ { int i,nu,mu; printf("输入顶点的个数和(边)弧的个数,空格隔开:"); scanf("%d%d",&nu,&mu); G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *)); for(i=0;i<nu;i++)/*分配邻接矩阵空间*/ G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell)); G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/ G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/ } void InsertGraph(MGraph *G,int i,VertexType e) { if(i<0||i>G->vexnum) return; G->vexs[i].next=e.next; strcpy(G->vexs[i].data,e.data); } int Locate(MGraph G,VertexType v1)/*确定v1在图顶点中的位置*/ { int i; for(i=0;i<G.vexnum;i++) if(strcmp(v1.data,G.vexs[i].data)==0) return i; return -1; } void CreateUND(MGraph *G)/*采用数组(邻接矩阵)和邻接表表示无向图*/ {int i,j,k,p[10],d; VertexType v1,v2,*q1,*q2,*q; for(i=0;i<10;i++) p[i]=0; for(i=0;i<G->vexnum;++i)/*初始邻接表*/ { for(j=0;j<G->vexnum;++j) G->arcs[i][j].adj=0;} for(k=0;k<G->arcnum;++k) {printf("\n输入第 %d 条(边)弧相对的两个顶点值,每输入一个,按回车:\n",k+1); d=0; scanf("%s%s",v1.data,v2.data);/*输入相邻的两个点值*/ i=Locate(*G,v1);j=Locate(*G,v2);/*用i 和j来确定它们的位置*/ G->arcs[i][j].adj=1; G->arcs[j][i].adj=G->arcs[i][j].adj; q1=(VertexType *)malloc(sizeof(VertexType));/*为q1和q2各分配空间*/ q2=(VertexType *)malloc(sizeof(VertexType)); strcpy(q1->data,G->vexs[i].data); strcpy(q2->data,G->vexs[j].data); q1->next=q2->next=NULL; if(p[i]==0) {G->vexs[i].next=q2;p[i]++;} else {q=&(G->vexs[i]); while(d!=p[i]) {d++;q=q->next;} p[i]++; q->next=q2;/*接在最后*/ } d=0;/*因为是无向图所以j顶点也要接*/ if(p[j]==0) {G->vexs[j].next=q1;p[j]++;}/*同上*/ else {q=&(G->vexs[j]); while(d!=p[j]) {d++;q=q->next;} p[j]++; q->next=q1; } } } void Pint(MGraph G)/*输出邻接矩阵*/ {int i,j; for(i=0;i<G.vexnum;i++) { for(j=0;j<G.vexnum;j++) printf("%d ",G.arcs[i][j].adj); printf("\n"); } } void DFS(MGraph G,int v)/*从第v个顶点出发递归遍历*/ { VertexType *ptr;/*是对图的邻接表作遍历*/ int i; visited[v]=1;printf(" ** %s ",G.vexs[v].data);/*访问第V个顶点*/ ptr=G.vexs[v].next;/*V顶点的第一个相邻点*/ while(ptr!=NULL)/*上面的顶点存在*/ {i=Locate(G,*ptr);/*求出它的位置*/ if(!visited[i]) DFS(G,i); ptr=ptr->next; } } void DFSTraverse(MGraph G)/*对图作深度遍历,画邻接表分析*/ {int i; for(i=0;i<G.vexnum;i++)/*如果图是连通的则一次就能遍历,否则对另一个连通的第一个顶点。。同上*/ if(!visited[i]) DFS(G,i); } void main() { MGraph G; VertexType e,*p; int i; InitGraph(&G); for(i=0;i<10;i++) visited[i]=0;/*初始为0,表示没被访问过*/ printf("顶点值,每输入一个,按回车: \n"); for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/ {scanf("%s",e.data);e.next=NULL;InsertGraph(&G,i,e);} CreateUND(&G);/*构造图结构*/ printf("邻接矩阵为:\n"); Pint(G);/*输出邻接矩阵*/ printf("邻接表为:\n"); for(i=0;i<G.vexnum;i++)/*输出邻接表*/ {printf(" *%s* ",G.vexs[i].data);p=G.vexs[i].next; while(p) {printf(" *%s* ",p->data);p=p->next;} printf("\n"); } printf("深度遍历结果为:\n"); DFSTraverse(G);/*深度遍历*/ getch(); } |
|