試驗五圖的操作及應用

1、實驗五：圖的操作及應用實驗學時：4實驗類型：綜合型一、實驗目的.理解圖的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；.掌握圖的鄰接矩陣和鄰接表存儲表示的實現(xiàn)方法；.掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法的實現(xiàn)；.掌握拓撲排序算法的實現(xiàn)方法。二、實驗條件Visual C+ 6.0三、實驗原理及相關(guān)知識.圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)的描述；.圖的鄰接矩陣和鄰接表存儲表示的算法；.圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；.拓撲排序算法。四、實驗步驟.實現(xiàn)圖的鄰接矩陣的存儲表示。.實現(xiàn)圖的鄰接表存儲表示。.實現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。.實現(xiàn)拓撲排序算法。.調(diào)用以上函數(shù)實現(xiàn)以下操作：(1)建立圖。(2)輸出基于鄰接表存儲的深度優(yōu)先

2、和廣度優(yōu)先遍歷序列(3)輸出有向圖的拓撲排序序列。參考代碼：要求：補充完整以下代碼使其能夠運行通過。#include stdio.h#include malloc.h#include string.h#define INFINITY 10000/用整型最大值代替define MAX_VERTEX_NUM 20 / 最大頂點個數(shù)define OK 1define ERROR 0define FALSE 0define TRUE 1#define MAXQSIZE100typedef int QElemType;typedef float VRType;typedef float InfoType

3、;typedef char VertexType;typedef char VexType;/=鄰接矩陣的定義=typedef struct VRType adj;InfoType info; 該弧相關(guān)信息的指針（可無） ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM100; / 頂點向量AdjMatrix arcs; / 鄰接矩陣int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù) MGraph ;/=鄰接矩陣的定義=/=鄰接表的定義= typedef

4、 struct ArcNode / 表結(jié)點int adjvex;/該弧所指向的頂點的位置struct ArcNode *nextarc; / 指向下一條弧的指針float info;/網(wǎng)的權(quán)值指針 ArcNode;typedef struct/ 頭結(jié)點VertexType data100;/ 頂點信息ArcNode *firstarc;/第一個表結(jié)點的地址 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù)ALGraph;int visitedMAX_VERTEX

5、_NUM;/=鄰接表的定義=/=隊列定義和基本操作=typedef struct QNode1QElemType data;struct QNode1 *next;QNode, *QueuePtr;typedef struct /轆隊列的定義QElemType *base;int front;int rear; SqQueue;typedef structQueuePtr front;QueuePtr rear;LinkQueue;LinkQueue InitQueue(LinkQueue Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(

6、!Q.front)exit(1);Q.front-next=NULL;return Q;int EnQueue(LinkQueue* Q, QElemType e)QueuePtr p;if( !(p=(QueuePtr)malloc(sizeof(QNode) return ERROR;p-data = e;p-next = NULL;Q-rear-next = p;Q-rear = p;return OK;int DeQueue(LinkQueue *Q, QElemType *e) QueuePtr p;if( Q-front = Q-rear )3return ERROR;p = Q-

7、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-front =Q-rear) return 1; else return 0;int DestroyQueue( LinkQueue *Q ) while(Q-front) Q-rear=Q-front-next;free(Q-front);Q-front=Q-rear;:return OK;隊列定義和基本操作int LocateVex(M

8、Graph G,char *vert) int i;for(i=0; iG.vexnum; i+)if(strcmp(G.vexsi,vert)=0) return i;return -1;int LocateVex1(ALGraph G,char *vert) int i;for(i=0; iG.vexnum; i+)if(strcmp(G.verticesi.data,vert)=0)return i;return -1;MGraph CreateGraph_UDN( MGraph G )/ 建立無向網(wǎng) G 的鄰接矩陣 int i, j,k;float w;VexType v1100, v

9、2100;printf(輸入頂點數(shù)，數(shù)邊數(shù)：);scanf(%d %d”, &G .vexnum, &G.arcnum);for(i=0; iG.vexnum; i+)/ 讀入所有的頂點 printf(輸入第%d個頂點的信息：,i+1);scanf(%s, &G .vexsi);for(i=0; i G.vexnum; i+) 初始化鄰接矩陣for(j=0; jG .vexnum; j+)G.arcsij.adj=INFINITY;for(k=0; kG.arcnum; k+) / 輸入所有的邊printf(輸入第%d條邊依附的兩個頂點和邊上的權(quán)值:,k+1);scanf(%s %s %f”,

10、 &v1, &v2, &w);/查詢兩個頂點在圖中存儲的位置i = LocateVex(G v1);j = LocateVex(G, v2);if (i=-1 | j=-1)printf(輸入的邊不正確 n); return;G.arcsij.adj = w;G.arcsji.adj = G.arcsij.adj;return G;ALGraph CreateALGraph_UDN(ALGraph G )/ 建立無向網(wǎng) G 的鄰接表 int i,j,k;float w;ArcNode * p;VexType v1100, v2100;printf(輸入頂點數(shù)，數(shù)邊數(shù)：”);scanf(%d %

11、d”,&(G .vexnum),&(G.arcnum); /* 讀入頂點數(shù)和邊數(shù) */ for(i=0;iG.vexnum;i+) /*建立有n個頂點的頂點表 */ (printf(輸入第%d個頂點的信息：,i+1);scanf(%s”,&(G .verticesi.data) ;/* 讀入頂點信息 */G.verticesi.firstarc=NULL; /*頂點的邊表頭指針設(shè)為空*/ for(k=0;kG.arcnum;k+ ) /* 建立邊表 */ ( printf(輸入一條邊依附的兩個頂點和邊上的權(quán)值:);scanf(%s %s %f,&v1,&v2,&w) ;/* 讀入邊 的頂點對應

12、序號 */i = LocateVex1(G v1);j = LocateVex1(G v2); if (i=-1 | j=-1)printf(輸入的邊不正確 n); return; p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生成新邊表結(jié)點 p */ p-adjvex=j;/*鄰接點序號為j */p-info =w; p-nextarc=Gverticesi.firstarc; /*將新邊表結(jié)點p插入到頂點 Vi的鏈表 頭部*/G.verticesi.firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生

13、成新邊表結(jié)點 p */ p-adjvex=i;/*鄰接點序號為i */p-info =w; p-nextarc=Gverticesj.firstarc; /*將新邊表結(jié)點p插入到頂點Vj的鏈表 頭部*/ G.verticesj.firstarc=p; return G; /*CreateALGraph*/VisitFunc(char *ch)/輸出頂點的信息 printf(%s ,ch);void DFS(ALGraph G, int v ) int j;6ArcNode *p; VisitFunc(Gverticesv.data);/ 訪問第 v 個頂點visitedv=TRUE;/設(shè)置訪問

14、標志為 TRUE(已訪問)for(p=G.verticesv.firstarc; p;p=p-nextarc) j=p-adjvex; if( !visitedj ) DFS(G, j); void DFSTraverse( ALGraph G)圖的深度優(yōu)先遍歷算法 int v;for(v=0; vG.vexnum; v+) visitedv=FALSE; /訪問標志數(shù)組初始化(未被訪問)for(v=0;vG.vexnum;v+) if(!visitedv)DFS(G,v);/對尚未訪問的頂點調(diào)用 DFSvoid BFSTraverse(ALGraph G) 圖的廣度優(yōu)先遍歷算法 int v,

15、j,u ;ArcNode *p;LinkQueue Q;Q=InitQueue(Q); /置空的輔助隊列Q for(v=0; vG.vexnum; v+) visitedv=FALSE; / 置初值 for(v=0; vnextarc) j=p-adjvex; if( !visitedj)7visitedj=TRUE;VisitFunc(Gverticesj.data);EnQueue(&Q, j); DestroyQueue( &Q );實現(xiàn)建立有向網(wǎng)的鄰接矩陣和鄰接表的函數(shù)MGraph CreateGraph_DN( MGraph G )/ 建立有向網(wǎng) G 的鄰接矩陣 ALGraph Cr

16、eateALGraph_DN(ALGraph G )/ 建立有向網(wǎng) G 的鄰接表 Print_MGraph(MGraph G)/輸出圖的鄰接矩陣表示int i,j;for(i=0;iG.vexnum;i+) for(j=0;jG .vexnum;j+)printf(%f ,G .arcsij.adj ); /* 鄰接矩陣 */ printf(n);Print_ALGraph(ALGraph G) /輸出圖的鄰接表表示int i,j;ArcNode *p;for(i=0;i%s,G .verticesp-adjvex .data); p=p-nextarc ;/*頂點的邊表頭指針設(shè)為空*/pri

17、ntf(n); void FindInDegree(ALGraph G, int *indegree) (int i,k;ArcNode *p;for (i=0; inextarc) k = p-adjvex;indegreek+; /=拓撲排序= int TopologicalSort(ALGraph G) /有向圖G采用鄰接表存儲結(jié)構(gòu)。/若G無回路，則輸出G的頂點的一個拓撲序列并返回OK,否則ERRORint SqStackMAX_VERTEX_NUM,top=0;int count,k,i;ArcNode *p; int indegreeMAX_VERTEX_NUM; for (i=0;

18、iMAX_VERTEX_NUM;i+) indegreei=0;FindInDegree(G, indegree); / 對各頂點求入度 indegree0.vernum-1for (i=0; i , G .verticesi.data); +count; 輸出 i 號頂點并計數(shù)for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex;/對i號頂點的每個鄰接點的入度減 1if (!(-indegreek) SqStacktop=k;top+; 若入度減為 0, 入棧if (countG.vexnum) printf(存在回路！ );return ERROR; / 該有向圖有回路 else return OK; / TopologicalSort/=拓撲排序=main()MGraph G1,G3;ALGraph G2,G4;int PMAX_VERT