数据结构C语言-图的建立以及深度优先、广度优先遍历

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int status; typedef int ElemType; typedef int bool; #define true 1 #define false 0 //邻接矩阵 #define MaxInt 32767 #define MVNum 100 typedef char VerTexType; typedef int ArcType; typedef struct { VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; int LocateVex_AM(AMGraph G,VerTexType v) { int i=0; //while(i<G.vexnum&&v!=G.vexs[i]) //i++; for(;i<G.vexnum;i++) if(G.vexs[i]==v) break; return i; } status CreateUDN_AM(AMGraph *G,VerTexType *V) { int i,j,k; for(i=0;i<G->vexnum;i++) G->vexs[i]=V[i]; for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) G->arcs[i][j]=MaxInt; char v1,v2; for(k=0;k<G->arcnum;k++) { scanf("%c%c",&v1,&v2); getchar();//吃回车！！ int i=LocateVex_AM(*G,v1); int j=LocateVex_AM(*G,v2); G->arcs[i][j]=1; G->arcs[j][i]=G->arcs[i][j]; } return OK; } void printAMG(AMGraph G) { int i,j; for(i=0;i<G.vexnum;i++) { for(j=0;j<G.vexnum;j++) printf("] ",G.arcs[i][j]); printf("\n"); } } typedef int OtherInfo; //邻接表 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; OtherInfo info; }ArcNode; typedef struct VNode { VerTexType data; ArcNode *firstarc; }VNode,AdjList[MVNum]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; int LocateVex_AL(ALGraph G,VerTexType v) { int i=0; while(i<G.vexnum&&G.vertices[i].data!=v) i++; if(i>=G.vexnum) return ERROR; return i; } status CreateUDN_AL(ALGraph *G,VerTexType *V) { int i=0,k=0,j; for(;i<(*G).vexnum;i++)//G->就完事了! { G->vertices[i].data=V[i]; G->vertices[i].firstarc=NULL; } char v1,v2; for(;k<G->arcnum;k++) { scanf("%c%c",&v1,&v2); getchar(); int i=LocateVex_AL(*G,v1); int j=LocateVex_AL(*G,v2); ArcNode *p1=(ArcNode *)malloc(sizeof(ArcNode)); p1->adjvex=j; p1->nextarc=G->vertices[i].firstarc; G->vertices[i].firstarc=p1; ArcNode *p2=(ArcNode *)malloc(sizeof(ArcNode)); p2->adjvex=i; p2->nextarc=G->vertices[j].firstarc; G->vertices[j].firstarc=p2; } return OK; } bool visited[MVNum]; void DFS_AM(AMGraph G,int v) { printf("%c\n",G.vexs[v]); visited[v]=true; int w; for(w=0;w<G.vexnum;w++) if(G.arcs[v][w]<MaxInt&&!visited[w]) DFS_AM(G,w); } void DFS_AL(ALGraph G,int v) { printf("%c\n",G.vertices[v].data); visited[v]=true; ArcNode *p=G.vertices[v].firstarc; while(p!=NULL) { int w=p->adjvex; if(!visited[w]) DFS_AL(G,w); p=p->nextarc; } } void DFSTraverse_AM(AMGraph G) { int v=0; for(;v<G.vexnum;v++) visited[v]=false; for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS_AM(G,v); } //广度优先所用队列 #define MAXSIZE 100 typedef struct { ElemType base[MAXSIZE]; int front; int rear; }SqQueue; //循环队列 status InitQueue(SqQueue *Q) { Q->front=0; Q->rear=0; return OK; } status EnQueue(SqQueue *Q,ElemType e) { if((Q->rear+1)%MAXSIZE==Q->front) return ERROR; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXSIZE; return OK; } status DeQueue(SqQueue *Q,ElemType *e) { if(Q->front==Q->rear) return ERROR; *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return OK; } bool QueueEmpty(SqQueue Q) { return Q.front==Q.rear; } void BFS_AM(AMGraph G,int v) { int i=0; for(;i<G.vexnum;i++) visited[i]=false; printf("%c\n",G.vexs[v]); visited[v]=true; SqQueue Q; InitQueue(&Q); EnQueue(&Q,v); while(!QueueEmpty(Q)) { ElemType e; DeQueue(&Q,&e); int w; for(w=0;w<G.vexnum;w++) if(G.arcs[e][w]<MaxInt&&!visited[w]) { printf("%c\n",G.vexs[w]); visited[w]=true; EnQueue(&Q,w); } } } int main() { AMGraph G; G.vexnum=8; G.arcnum=9; VerTexType V[G.vexnum]; int i; for(i=0;i<G.vexnum;i++) V[i]=i+'A'; printf("Create AMGraph:\n"); CreateUDN_AM(&G,V); printAMG(G); printf("Depth First Search:\n"); DFSTraverse_AM(G); printf("Breadth First Search:\n"); BFS_AM(G,0); ALGraph G2; G2.vexnum=8; G2.arcnum=9; printf("Create ALGraph:\n"); CreateUDN_AL(&G2,V); printf("Depth First Search:\n"); for(i=0;i<G.vexnum;i++) visited[i]=false; DFS_AL(G2,0); return 0; }

代码这么长，可见多态有多重要 运行截图如下：