图的深度遍历和广度遍历以及最小生成树.docx

//本程序主要包含以下功能//采用邻接矩阵构造图//图的深度遍历和广度遍历//采用普里姆算法和克鲁斯卡尔算法构造最小生成树#includestdio.h#includestdlib.h #define INFINITY 999#define MAX_VERTEX_NUM 20#define OK 1#define ERROR -1typedef char VertexType;typedef char InfoType;typedef VertexType QElemType;bool visited[MAX_VERTEX_NUM];// 访问标志数组 typedef struct{ /*辅助数组*/ VertexType adjvex; int lowcost;}closedge[MAX_VERTEX_NUM];typedef struct {int begin;int end;int flag;int weight;}edge; edge edges[50];typedef struct ArcCell{int adj;InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;} MGraph;typedef struct QNode{QElemType 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) return ERROR;Q.front-next=NULL;return OK;}int DestroyQueue(LinkQueue Q){while(Q.front){Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;}return OK;}//DestroyQueueint EnQueue(LinkQueue Q,QElemType e){QueuePtr p; //p=(QueuePtr)malloc(sizeof(QNode));if(!p) return ERROR;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;}int DeQueue(LinkQueue Q,QElemType e){if(Q.front==Q.rear) return ERROR;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p) Q.rear=Q.front;free(p);return OK;}int QueueEmpty(LinkQueue Q){if(Q.rear==Q.front) return 1;else return 0;} int LocateVex(MGraph G,VertexType u){int i;for(i = 0; i G.vexnum; ++i)if( u==G.vexs[i] )return i;return -1;}int FirstAdjVex(MGraph G,int k){ if(k=0 kG.vexnum){ //k合理 for(int i=0;iG.vexnum;i++) if(G.arcs[k][i].adj!=INFINITY) return i; } return -1; } //图G中顶点i的第j个邻接顶点的下一个邻接顶点 int NextAdjVex(MGraph G,int i,int j){ if(i=0 iG.vexnum j=0 jG.vexnum){ //i,j合理 for(int k=j+1;kG.vexnum;k++) if(G.arcs[i][k].adj!=INFINITY) return k; } return -1; } int CreateUDN(MGraph G) {// 算法 7.2 // 采用数组（邻接矩阵）表示法，构造无向网G。 int i,j,k,w,p=0; VertexType v1,v2; printf