无向网的构建及其遍历

1、#include stdio.h#iiiclude Hmalloc.hM#iiiclude Hstring.hn#include stdlib.h”#define MAX_VERTEX_NUM 20/ 最大顶点个数#define OK 1#define ERROR 0#define FALSE 0#define TRUE 1#define MAXQSIZE100typedef int QElemType;typedef float VRType;typedef float IiifbType;typedef char VertexTe;typedef char VexType;/=邻接矩阵的定

2、义typedef stmct (VRType adj;InfoType info; /该弧相关信息的指针(可无) Ar cCell, AdjMatnxMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef stmct (VeitexTe vexsMAX_VERTEX_NUM100; / 顶点向量AdjMatrix arcs; / 邻接矩阵mt vexiiuiiLaicnum; /图的当前顶点数和弧数 MGraph;/=邻接矩阵的定义邻接表的定义typedef stmct AicNode / 表结点int adjvex;/该弧所指向的顶点的位置stmct ArcNode *n

3、extarc; /指向下一条弧的指针float nifo;/网的权值指针 AicNode;typedef stmct/ 头结点VertexType data100;/ 顶点信息AicNode *firstarc;/第一个表结点的地址 VNode, AdjListMAX_VERTEX_NUM;typedef stmct (Adj List vertices;mt vexnum,arcnum;/图的当前顶点数和弧数ALGiaph;mt visited MAX_VERTEX_NUM;/=操作=/=操作队列定义和基本typedef struct QNodel 链队列的定义QElemType data;

4、stmct QNodel *next;QNode, *QueuePti:typedef stnict(QueuePtr front;QueuePtr rear;LnikQueue;LinkQueue IiiitQueue(LiiikQueue Q)Q.fiont=Q.reai-(QueuePti)nialloc(sizeof(QNode);exit(O);Q. fi ont-next=NULL;return Q;hit EnQueue(LnikQueue* Q, QElemType e)QueuePtr p;if( I (p=(QueuePti)nialloc(sizeof(QNode) re

5、turn ERROR;p-data = e;p-next = NULL;Q-iear-next = p;Q-iear = p;return OK;)hit DeQueue(LnikQueue *Q, QElemType *e) ( QueuePtr p;if( Q-fiont = Q-rear )return ERROR;p = Q-fiont-next;*e = p-data;Q-fiont-next = p-next;if(Q-iear = p) Q-reai = Q-fiont;free(p);return OK;)mt QueueEmpty(LinkQueue *Q) (if(Q-fi

6、ont =Q-rear) return 1;else return 0;hit DestioQueue( LuikQueue *Q )(wliile(Q-fiont) (Q-rear=Q-fiont-next;fiee(Q-fiont);Q-fiont=Q-iear;return OK;/=操作队列定义和基本/=操作队列定义和基本hit LocateVex(MGraph Qchar *vert)( mt i；fbr(i=O; iG.vexiium; i+)if(sticmp(Gvexs i,veil)=0)return i;return -1;hit Locate Vex 1 (ALGraph

7、 Qchar *vert)( mt i；fbr(i=O; iG.vexiium: i+)if(strcmp(G verticesi .data,vert)=O)return i;leturn -1;MGraph CreateMGraph.UDN( MGraph G)建立无向图 G 的邻接矩阵 int i,j,k;float w;VexTypevl100,v2100;pnntfC*输入顶点，边数：)；scanfV%d %d”，&Gvexnum, &G.arcnum);for(i=0; iG.vexiium; i+)/ 读入所有的顶点pnntf(输入第d个顶点的信息：,i+1);scanf(s”，

8、&Gvexsi);for(i=0; i G.vexiium; i+) 初始化邻接矩阵fbr(j=O; jG.vexiium; j+)Gaicsij.adj=O;foi(k=0; kG.arcnum; k+) (/ 输入所有的边pnntf(”输入第d条边依附的两个顶点和边上的权值二k+1);scanf(”s %s %f&vl, &v2, &w);/查询两个顶点在图中存储的位置i = LocateVex(G. vl);j = Locate Vbx(G, v2);lf(l=-l llj=-l)pnntf(”输入的边不正确n”); exit(O);)Garcsij.adj = w;Garcsji.ad

9、j = Garcsij.adj;return G;ALGraph CreateALGraph.UDN(ALGraph G )建立无向图 G 的邻接表mt i,j,k;float w;AicNode * p;VexTypevl100, v2100;pnntf(”输入顶点数，数边数：);scanf(n%d %d,&(Gvexiium).&(G.aicnum); /* 读入顶点数和边数 */for(i=0;iG.vexiium;i-H-) /*建立有n个顶点的顶点表*/(pnntf(“输入第d个顶点的信息：”,i+l);scanf(,%s,&(Gverticesi.data) ;/* 读入顶点信息

10、*/G.veilicesi.fu.starc=NULL; /*顶点的边表头指针设为空*/)fbr(k=O;kGarcnum;k+) /* 建立边表 */(pnntf(”输入一条边依附的两个顶点和边上的权值:“)；scanf(H%s %s %f&vl.&v2,&w); /* 读入边的顶点对应序号*/i = LocateVexl(G； vl);j = LocateVexl(G； v2);lf(l=-lprintf(”输入的边不正确n”); exit(O);)p=(ArcNode*)malloc(sizeof(ArcNode); /* 生成新边表结点 p */p-adjvexj;/*邻接点序号为j*

11、/p-infb =w;p-iiextarc=Gvenicesi.fiistarc; /*将新边表结点p插入到顶点Vi的链表头部*/ G vertices i. fiistarc=p;p=(ArcNode*)malloc(sizeof(ArcNode); /* 生成新边表结点 p */p-adjvex=i;/*邻接点序号为i */p-mfb =w; p-nextarc=Gvenices0.fiistarc; /*将新边表结点p插入到顶点Vj的链表头部*/ G vertices j . fhstarc=p;return G;VisitFunc(chai- *ch)输出顶点的信息(pimtf(H%s

12、 ”,ch);void DFS(ALGraph G, mt v) mt j；AicNode *p/表结点指针VisitFunc(G.verticesv.data);/ 访问第 v 个顶点visitedv=TRUE;/设置访问标志为TRUE(己访问)fbr(p=G. verticesv. fir stare; p ;p=p-nextarc) j=p-adjvex;if( !visitedj ) DFS(G j)；void DFSTiaveise( ALGraph G)图的深度优先遍历算法 mt v; fbr(v=O; vG.vexnum; v+)visitedv=FALSE; /访问标志数组初始

13、化(未被访问) fbr(v=O;vGvexiiuni;v+)/对尚未访问的顶点调用DFS/对尚未访问的顶点调用DFSDFS(Gv);void BFSTiaverse(ALGraph G) 图的广度优先遍历算法 int v,j,u ；AicNode *p;LnikQueue Q;Q=IiiitQueue(Q); 置空的辅助队列Q fbr(v=O; vG.vexiium; v+) visitedv=FALSE; / 置初值 fbr(v=O; vnextarc) j=p-adjvex; iR !visited。) visitedj=TRUE;VisitFunc(G.veiticesj.data);

14、EnQueue(&Q, j);DestroyQueue( &Q );实现建立有向网的邻接矩阵和邻接表的函数PrinCMGraph(MGraph G) 输出图的邻接矩阵表示fbi(i=O;iG.vexiium;i+) fbr(j=OjG.vexiium;j-H-),G.arcsi|j.adj); /*邻接矩阵*/ pnntffW);Print_ALGraph(ALGraph G) 输出图的邻接表表示mt i;AicNode *p;fdr(i=O; i%s,G.vemcesp-adjvex .data);p=p-nextaic ;/*顶点的边表头指针设为空*/pnntR”iT);main()MGraph Gl;ALGraph G2;无向网 G1无向网 G2 的邻接表无向网 G1无向网 G2 的邻接表* *瓦,，)G1 =CreateMGraph_UDN( G1);