用C++实现的无向图广度优先遍历.doc

用C+实现的实现无向图的广度优先遍历#include#includeusing namespace std;/图的邻接表存储表示#define MAX_NAME 5 / 顶点字符串的最大长度 #define MAX_VERTEX_NUM 20typedef char VertexTypeMAX_NAME;typedef struct ArcNode /表结点int adjvex;struct ArcNode *nextarc;int *info;ArcNode;typedef struct VNode /头结点VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct /图AdjList vertices;int vexnum,arcnum;string kind;ALGraph;/队列的链式存储结构P61(元素类型为整形)typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针QueuePtr rear; / 队尾指针LinkQueue;int InitQueue(LinkQueue &Q)/构造一个空队列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(-1);/存储分配失败Q.front-next=NULL;return 1;bool QueueEmpty(LinkQueue Q)/判空 if(Q.front=Q.rear)return true;return false;int EnQueue(LinkQueue &Q,int e)/队列的插入（尾） QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(-1); / 存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;/尾指针后移return 1;int DeQueue(LinkQueue &Q,int &e)/队列的删除（首） QueuePtr p;if(Q.front=Q.rear)return 0;/队列空，返回0p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front; /尾指针回送free(p);return 1;int LocateVex(ALGraph G,VertexType u) /返回顶点在图中的位置，无则返回-1 for(int i=0;iG.vexnum;+i)if(strcmp(u,G.verticesi.data)=0)return i;return -1;int CreateGraph(ALGraph &G)int w; / 权值VertexType va;VertexType vb;ArcNode *p;coutG.kind;coutG.vexnumG.arcnum;cout请输入各个顶点的值n;for(int i=0;iG.verticesi.data;G.verticesi.firstarc=NULL;if(G.kind=DN|G.kind=UDN) / 网cout请顺序输入每条弧(边)的弧尾、弧头及权值:n;else cout请顺序输入每条弧(边)的弧尾和弧头:n;for(int k=0;kvavbw;else cinvavb;int i=LocateVex(G,va); / 弧尾int j=LocateVex(G,vb); / 弧头p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=j;if(G.kind=DN|G.kind=UDN) p-info=(int *)malloc(sizeof(int);*(p-info)=w;elsep-info=NULL; p-nextarc=G.verticesi.firstarc; / 插在表头G.verticesi.firstarc=p;if(G.kind=UDG|G.kind=UDG) / 无向图或网,产生第二个表结点p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=i;if(G.kind=UDN) p-info=(int*)malloc(sizeof(int);*(p-info)=w;elsep-info=NULL; p-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=p;return 1;VertexType& GetVex(ALGraph G,int v) /返回v对应的顶点的值 if(v=G.vexnum|vadjvex;elsereturn -1;int NextAdjVex(ALGraph G,VertexType v,VertexType w) / 返回v的,相对于w的,下一个邻接顶点的序号 ArcNode *p;int posi_v,posi_w;posi_v=LocateVex(G,v); posi_w=LocateVex(G,w); p=G.verticesposi_v.firstarc;while(p&p-adjvex!=posi_w) / 指针p不空且所指表结点不是wp=p-nextarc;if(!p|!p-nextarc) / 没找到w或w是最后一个邻接点return -1;else return p-nextarc-adjvex; / 找到，返回int visitedMAX_VERTEX_NUM; / 访问标志数组，值为0或1void Visit(VertexType s)couts ;void BFSTraverse(ALGraph G) /按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visited for(int v=0;vG.vexnum;+v)visitedv=0; / 置初值LinkQueue Q;InitQueue(Q); / 置空的辅助队列Qint u,w;for(v=0;v=0;w=NextAdjVex(G,GetVex(G,u),GetVex(G,w)if(