图的广度优先遍历和深度优先遍历.doc

《图的广度优先遍历和深度优先遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#defineTrue1#defineFalse0#defineError-1#defineOk1#defineINFINITY0#defineMAX_VERTEX_NUM10//最大顶点数#defineMAX_EDGE_NUM40//最大边数typedefenum{DG,DN,UDG,UDN}Graphkind;typedefcharVertexType;//顶点数据类型typedefstructArcCell{intadj;//无

2、权图，1或0表示相邻否；带权图则是权值。//int*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数。Graphkindkind;}MGraph;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;}ArcNo

3、de;typedefstructVNode{intdata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intLocateVex(MGraphG,VertexTypev1){inti;for(i=0;i

4、de*next;}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;intInitQueue(LinkQueue*Q){Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(True);}elsereturn(False);}intEnterQueue(Lin

5、kQueue*Q,intx){LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->data=x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return(True);}elsereturn(False);}intDeleteQueue(LinkQueue*Q,int*x){LinkQueueNode*p;if(Q->fro

6、nt==Q->rear)return(False);p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);return(True);}intIsEmpty(LinkQueue*Q){if(Q->front==Q->rear)return(True);elsereturn(False);}intvisited[MAX_VERTEX_NUM];intCreatDN(MGraph&G1,ALGraph&G2)//采用数组表示

7、法，构造有向网G{intb;ArcNode*p;VertexTypev1,v2;intw,j;cout<<"输入图的顶点数及弧数"<>G1.vexnum>>G1.arcnum;G2.vexnum=G1.vexnum;G2.arcnum=G1.arcnum;cout<<"输入顶点向量"<>G1.vexs[i];}for(i=0;i

8、INITY;}for(i=0;i