邻接表存储,广度优先遍历.doc

#include#include#define OK 1#define ERROR -1#define FALSE 0#define TRUE 1typedef int status;/-存储类别，邻接表-#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeint data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;ALGraph;/-队列定义-typedef int status;typedef struct Qnodeint data;struct Qnode *next;Qnode, *queueptr;typedef structqueueptr front;queueptr rear;linkqueue; /-初始化队列-status initqueue(linkqueue &Q)Q.front=Q.rear=(queueptr)malloc(sizeof(Qnode);if(!Q.front)exit(0);Q.front-next=NULL;return OK;/-插入-void EnQueue(linkqueue &Q,int e)Qnode *p;p=(queueptr)malloc(sizeof(Qnode);if(!p)exit(0);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;/return OK;/-判定是否为空-status QueueEmpty(linkqueue Q)if(Q.front=Q.rear)return OK;else return !OK;/-删除-status DeQueue(linkqueue &Q,int &u)if(Q.front=Q.rear)return ERROR;queueptr p;p=Q.front-next;u=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;/-定位，返回下标-status LocateVex(ALGraph G,int vex)for(int i=0;iG.vexnum;i+)if(G.verticesi.data=vex)break;return i;/-图创建，输入-status CreatAL(ALGraph &G)printf(输入该图中顶点和弧的个数n);scanf(%d %d,&G.vexnum,&G.arcnum);printf(n输入顶点n);for(int i=0;iG.vexnum;i+)scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL;printf(n输入弧n);int v1,v2;for(int j=0;jadjvex=temp_2;p_1-nextarc = G.verticestemp_1.firstarc;G.verticestemp_1.firstarc=p_1;p_2=(ArcNode*)malloc(sizeof(ArcNode);p_2-adjvex=temp_1;p_2-nextarc=G.verticestemp_2.firstarc;G.verticestemp_2.firstarc=p_2;return OK;/- 广度优先遍历-status visit(int v)printf(%d ,v);return OK;status BFSTraverse(ALGraph G,linkqueue Q,status visit(int v)int visitedMAX_VERTEX_NUM;int v;for(v=0;vG.vexnum;v+)visitedv=FALSE;for(v=0;vnextarc)int w=LocateVex(G,temp-adjvex);if(!visitedw)visitedw=TRUE;visit(temp-adjvex);EnQueue(Q,w); return OK;/int main()ALGraph G;linkqueue Q;if(