#include <stdio.h> #include <stdlib.h> #define MaxSize 20 typedef int VertexType; typedef int EdgeType; typedef int Elem ; typedef struct{ //邻接矩阵 VertexType Vex[MaxSize]; EdgeType Edge[MaxSize][MaxSize]; int vernum,edgenum; }MGraph; //邻接表 typedef struct ArcNode{ //边表 int adjvex; //边表中是顶点号!! struct ArcNode *next; }ArcNode; typedef struct VNode{ //主表 Elem num; //主表中是顶点值!! struct ArcNode *first; }VNode,AdjList[MaxSize]; typedef struct{ AdjList Ver; int vernum,edgenum; }Graph; //队列 typedef struct{ int data[MaxSize]; int front; int rear; }Queue; void InitQueue(Queue &Q) { Q.front=Q.rear=0; } bool isEmpty(Queue Q) { if(Q.front==Q.rear) return true; return false; } bool isFull(Queue Q) { if((Q.rear+1)%MaxSize==Q.front) return true; return false; } bool EnQueue(Queue &Q,int p) { if(isFull(Q)) return false; Q.data[Q.rear]=p; Q.rear=(Q.rear+1)%MaxSize; return true; } bool DeQueue(Queue &Q,int &p) { if(isEmpty(Q)) return false; p=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; } //图的基本操作 void CreateGraph(Graph &G) { G.vernum=G.edgenum=0; printf("请输入顶点数:"); scanf("%d",&G.vernum); printf("请输入主表顶点:\n"); int i,j; for(i=0;i<G.vernum;i++) scanf("%d",&G.Ver[i].num); printf("请输入边表顶点号:\n"); int x; for(i=0;i<G.vernum;i++) { G.Ver[i].first = (ArcNode*)malloc(sizeof(ArcNode)); G.Ver[i].first->next = NULL; printf("%d的边表\n",G.Ver[i].num); ArcNode *p=G.Ver[i].first; for(j=0;j<G.vernum;j++) { scanf("%d",&x); if(x==-1) break; else { ArcNode *node=(ArcNode*)malloc(sizeof(ArcNode)); node->adjvex=x; node->next=NULL; p->next=node; p=node; G.edgenum++; } } } } void displayGraph(Graph G) { int i,j; for(i=0;i<G.vernum;i++) { printf("%d ",G.Ver[i].num); ArcNode *p=G.Ver[i].first->next; while(p) { printf("-->%d",p->adjvex); p=p->next; } printf("\n"); } } int FirstNeighbor(Graph G,int x) { int i; for(i=0;i<G.vernum;i++) { if(G.Ver[i].num==x) return G.Ver[i].first->adjvex; } return -1; } int NextNeighbor(Graph G,int x,int y) { int i,j; for(i=0;i<G.vernum;i++) { if(G.Ver[i].num==x) { ArcNode *p=G.Ver[i].first; while(G.Ver[p->adjvex].num!=y&&p) { p=p->next; } if(p->next) return p->adjvex; else return -1; } } } bool visited[MaxSize]; void BFS(Graph G,int i) { int p,w; Queue Q; InitQueue(Q); printf("%d ",G.Ver[i].num); EnQueue(Q,i); while(!isEmpty(Q)) { DeQueue(Q,p); for(w=FirstNeighbor(G,G.Ver[p].num);w>=0;w=NextNeighbor(G,G.Ver[p].num,G.Ver[w].num)) { if(!visited[w]) { printf("%d ",G.Ver[w].num); visited[w]=true; EnQueue(Q,w); } } } } void BFSTraverse(Graph G) { int i; for(i=0;i<G.vernum;i++) visited[i]=false; for(i=0;i<G.vernum;i++) if(!visited[i]) BFS(G,i); } /* void transform(Graph G,MGraph &M) { int i,j; for(i=0;i<G.vernum;i++) M.Vex[i]=G.Ver[i].num; for(i=0;i<G.vernum;i++) for(j=0;j<G.vernum;j++) M.Edge[i][j]=0; for(i=0;i<G.vernum;i++) { ArcNode *p=G.Ver[i].first; while(p) { M.Edge[i][p->adjvex]=1; p=p->next; } } } void displayMGraph(MGraph M) { int i,j; printf("打印顶点表\n"); for(i=0;i<M.vernum;i++) printf("%d ",M.Vex[i]); printf("\n打印邻接矩阵\n"); for(i=0;i<M.vernum;i++) { for(j=0;j<M.vernum;j++) { printf("%d ",M.Edge[i][j]); } printf("\n"); } } */ int main() { Graph G; MGraph M; CreateGraph(G); printf("\n"); displayGraph(G); printf("\n"); BFSTraverse(G); // transform(G,M); // displayMGraph(M); return 0; }
标签:typedef,return,int,最后,MaxSize,printf,Ver From: https://www.cnblogs.com/simpleset/p/17854936.html