圖的應(yīng)用及其實現(xiàn)

1、.實驗六 圖的應(yīng)用及其實現(xiàn)班級：軟件091 姓名：郭靖 學(xué)號：200900834126 一、實驗?zāi)康?進一步功固圖常用的存儲結(jié)構(gòu)。2熟練掌握在圖的鄰接表實現(xiàn)圖的基本操作。3理解掌握AOV網(wǎng)、AOE網(wǎng)在鄰接表上的實現(xiàn)以及解決簡單的應(yīng)用問題。二、實驗內(nèi)容 一.基礎(chǔ)題目：題目一：從鍵盤上輸入AOV網(wǎng)的頂點和有向邊的信息,建立其鄰接表存儲結(jié)構(gòu),然后對該圖拓?fù)渑判?并輸出拓?fù)湫蛄? 試設(shè)計程序?qū)崿F(xiàn)上述AOV網(wǎng)的類型定義和基本操作,完成上述功能。測試數(shù)據(jù)：教材圖7.28 題目二：從鍵盤上輸入AOE網(wǎng)的頂點和有向邊的信息,建立其鄰接表存儲結(jié)構(gòu),輸出其關(guān)鍵路徑和關(guān)鍵路徑長度。 試設(shè)計程序?qū)崿F(xiàn)上述AOE網(wǎng)類型定

2、義和基本操作,完成上述功能。 題目二連通 OR 不連通描述：給定一個無向圖，一共n個點，請編寫一個程序?qū)崿F(xiàn)兩種操作：D x y 從原圖中刪除連接x，y節(jié)點的邊。Q x y 詢問x，y節(jié)點是否連通 輸入第一行兩個數(shù)n,m（5=n=40000,1=m=100000）接下來m行，每行一對整數(shù) x y （x,y=n）,表示x,y之間有邊相連。保證沒有重復(fù)的邊。接下來一行一個整數(shù) q（q=100000）以下q行每行一種操作，保證不會有非法刪除。輸出按詢問次序輸出所有Q操作的回答，連通的回答C，不連通的回答D三、實驗步驟(一)、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述1、 題目一（1） status Topologi

3、calSort(MGraph G)/有向圖G采用鄰接表存儲結(jié)構(gòu)，若G無回路，則輸出G的定帶你的一個拓?fù)渑判蛐蛄胁⒎祷豋K，否則返回ERROR2、 題目二（1） status TopologcalOrder(MGraph G,SqStack &T)/有向網(wǎng)G采取鄰接表存儲，求個頂點時間最早發(fā)生時間ve，T為拓?fù)渑判蝽旤c棧，S為零入度頂點棧，若G無回路，則返回G的一個拓?fù)渑判?，函?shù)數(shù)值為OK，否則返回ERROR（2） status CriticalPath(MGraph G)/G為有向網(wǎng)，輸出G的各項關(guān)鍵活動3、 題目五(1) status Deleteside(MGraph &G,int x,i

4、nt y)/G為無向圖，x、y為圖中兩節(jié)點，刪除xy邊（3） void DFSearch(MGraph &G, int v, int s,char* PATH)/ G為無向圖，查找一條V到S的路徑，v為遍歷起點，PATH存放路徑結(jié)點（二）、函數(shù)調(diào)用及主函數(shù)設(shè)計主函數(shù)只是對函數(shù)調(diào)用，這里不再列出，詳見源碼（三）、程序調(diào)試及運行結(jié)果分析這里只對拓?fù)渑判蜻M行調(diào)試運行，其他只貼出結(jié)果。1、 運行程序，提示輸入定點數(shù)和邊數(shù)：2、 依次按要求輸入，得到程序結(jié)果：以下是題目三結(jié)果： 實驗總結(jié)四、主要算法流程圖及程序清單1、主要算法流程圖拓?fù)渑判騎opologicalSort算法流程圖開始結(jié)束T求出各頂點入度

5、將入讀為0的頂點入棧Count置0Count+；棧頂元素出棧，存入iP =G.verticesi.firstarc是否棧空？P！=null對i號頂點每個鄰接點減1將入讀為0的頂點入棧FFT2、程序清單 題目一源碼：#include using namespace std;#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE 50#define INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int s

6、tatus;typedef int ElemType;typedef struct ArcNode / 弧結(jié)點 int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置struct ArcNode *nextarc; /鏈域，指示依附于vi的下一條邊或弧的結(jié)點，ArcNode;typedef struct VNode /表頭結(jié)點 char vexdata; /存放頂點信息struct ArcNode *firstarc; /指示第一個鄰接點VNode,AdjListMAX_VERTEX_NUM;typedef struct /圖的結(jié)構(gòu)定義AdjList vertices; /頂

7、點向量int vexnum, arcnum; / GraphKind kind=0; / 圖的種類標(biāo)志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return -1;void CreateGraph(MGraph &G)/ 生成圖G的存儲結(jié)構(gòu)-鄰接表cout輸入頂點數(shù)、邊數(shù): G.vexnum G.arcnum ; / 輸入頂點數(shù)、邊數(shù)和圖類/G.vexnum=5;G.arcnum=7;cout輸入頂點:endl;for (int i=0; i

8、 G.verticesi.vexdata; / 輸入頂點G.verticesi.firstarc = NULL; cout輸入各邊:endl;for (int k=0; ksv tv; / 輸入一條邊（?。┑氖键c和終點i = LocateVex(G, sv); int j = LocateVex(G, tv);/ 確定sv和tv在G中位置，即頂點在G.vertices中的序號ArcNode * pi = new ArcNode; if (!pi)exit(-1);/ 存儲分配失敗pi - adjvex = j;/ 對弧結(jié)點賦鄰接點位置pi - nextarc = G.verticesi.fir

9、starc;/頭插法，將tv結(jié)點插入到第i個單鏈表中G.verticesi.firstarc = pi;/ 插入鏈表G.verticesi cout構(gòu)造成功!=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType);if (!S.base)return OVERFLOW;S.top=S.base+INCREMENT;S.stacksize+=INCREMENT;*S.top=e;S.top+;return OK;/出棧status Pop(SqStack &S,ElemType

10、&e)/獲得S棧頂元素,復(fù)制給eif (S.top=S.base) return ERROR;S.top-;e=*S.top;return OK;/判空status IsEmpty(SqStack &S)/判斷棧S是否為空if (S.top=S.base)return ERROR;elsereturn OK;/清空棧status Clearstack(SqStack &S)S.top=S.base;return OK;void FindInDegree(MGraph G,int *indegree)for (int i=0;iG.vexnum;i+) /初始化每個頂點入度為0indegreei

11、=0;for (i=0;iadjvex+;G.verticesi.firstarc=G.verticesi.firstarc-nextarc;/*-AOV拓?fù)渑判蛐蛄?*/status TopologicalSort(MGraph G)int indegree20;FindInDegree(G,indegree);SqStack S;InitStack(S);for (int i=0;iG.vexnum;i+)if (!indegreei)Push(S,i);int count=0;while(IsEmpty(S)Pop(S,i);coutG.verticesi.vexdatanextarc)

12、int k=p-adjvex;indegreek-;if (!indegreek)Push(S,k);if (countG.vexnum)return ERROR;else return OK;/*main()*/int main()MGraph G;CreateGraph(G);TopologicalSort(G);return 0;題目二源碼：#include using namespace std;#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE 50#defi

13、ne INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int status;typedef int ElemType;typedef struct ArcNode / 弧結(jié)點 int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置struct ArcNode *nextarc; /鏈域，指示依附于vi的下一條邊或弧的結(jié)點，int info;ArcNode;typedef struct VNode /表頭結(jié)點 char vexdata; /存放頂點信息struct ArcNode *firstarc; /指

14、示第一個鄰接點VNode,AdjListMAX_VERTEX_NUM;typedef struct /圖的結(jié)構(gòu)定義AdjList vertices; /頂點向量int vexnum, arcnum; / GraphKind kind=0; / 圖的種類標(biāo)志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return -1;void CreateGraph(MGraph &G)/ 生成圖G的存儲結(jié)構(gòu)-鄰接表cout輸入頂點數(shù)、邊數(shù): G.vexnum

15、 G.arcnum ; / 輸入頂點數(shù)、邊數(shù)和圖類/G.vexnum=5;G.arcnum=7;cout輸入頂點:endl;for (int i=0; i G.verticesi.vexdata; / 輸入頂點G.verticesi.firstarc = NULL; cout輸入各邊和權(quán)值:endl;for (int k=0; ksv tvpower; / 輸入一條邊（?。┑氖键c和終點i = LocateVex(G, sv); int j = LocateVex(G, tv);/ 確定sv和tv在G中位置，即頂點在G.vertices中的序號ArcNode * pi = new ArcNode

16、; if (!pi)exit(-1);/ 存儲分配失敗pi - adjvex = j;/ 對弧結(jié)點賦鄰接點位置pi - nextarc = G.verticesi.firstarc;/頭插法，將tv結(jié)點插入到第i個單鏈表中G.verticesi.firstarc = pi;/ 插入鏈表G.verticesi pi-info=power;cout構(gòu)造成功!=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType);if (!S.base)return OVERFLOW;S.top=S

17、.base+INCREMENT;S.stacksize+=INCREMENT;*S.top=e;S.top+;return OK;/出棧status Pop(SqStack &S,ElemType &e)/獲得S棧頂元素,復(fù)制給eif (S.top=S.base) return ERROR;S.top-;e=*S.top;return OK;/判空status IsEmpty(SqStack &S)/判斷棧S是否為空if (S.top=S.base)return ERROR;elsereturn OK;/清空棧status Clearstack(SqStack &S)S.top=S.base;

18、return OK;void FindInDegree(MGraph G,int *indegree)for (int i=0;iG.vexnum;i+) /初始化每個頂點入度為0indegreei=0;for (i=0;iadjvex+;G.verticesi.firstarc=G.verticesi.firstarc-nextarc;int ve20;int vl20;status TopologcalOrder(MGraph G,SqStack &T)int indegree20;FindInDegree(G,indegree);SqStack S;InitStack(S);for (i

19、nt i=0;iG.vexnum;i+)if (!indegreei)Push(S,i);InitStack(T);int count=0,j=0,k=0;for (i=0;inextarc)k=p-adjvex;indegreek-;if (indegree=0)Push(S,k);if (vej+p-infovek)vek=vej+p-info;if (countG.vexnum)return ERROR;elsereturn OK;status CriticalPath(MGraph G)SqStack T;if (!TopologcalOrder(G,T)return ERROR;fo

20、r (int i=0;inextarc)k=p-adjvex;dut=p-info;if (vlk-dutvlj)vlj=vlk-dut;for (j=0;jnextarc)k=p-adjvex;dut=p-info;int ee=vej;int el=vlk-dut;char tag=(ee=el)?*: ;coutjkduteeeltagendl;return OK;int main()MGraph G;CreateGraph(G);CriticalPath(G);return 0;題目三源碼：#include using namespace std;#define MAX_VERTEX_

21、NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE 50#define INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int status;typedef int ElemType;typedef struct ArcNode / 弧結(jié)點 int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置struct ArcNode *nextarc; /鏈域，指示依附于vi的下一條邊或弧的結(jié)點，ArcNode;typedef

22、struct VNode /表頭結(jié)點 char vexdata; /存放頂點信息struct ArcNode *firstarc; /指示第一個鄰接點VNode,AdjListMAX_VERTEX_NUM;typedef struct /圖的結(jié)構(gòu)定義AdjList vertices; /頂點向量int vexnum, arcnum; / GraphKind kind=0; / 圖的種類標(biāo)志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return

23、 -1;void CreateGraph(MGraph &G)/ 生成圖G的存儲結(jié)構(gòu)-鄰接表 無向圖cout輸入頂點數(shù)、邊數(shù): G.vexnum G.arcnum ; / 輸入頂點數(shù)、邊數(shù)和圖類/G.vexnum=5;G.arcnum=7;cout輸入頂點:endl;for (int i=0; i G.verticesi.vexdata; / 輸入頂點G.verticesi.firstarc = NULL; cout輸入各邊:endl;for (int k=0; ksv tv; / 輸入一條邊（?。┑氖键c和終點i = LocateVex(G, sv); int j = LocateVex(G,

24、 tv);/ 確定sv和tv在G中位置，即頂點在G.vertices中的序號ArcNode * pi = new ArcNode; ArcNode * pj = new ArcNode; if (!pi)exit(-1);if (!pj)exit(-1);pi - adjvex = j;/ 對弧結(jié)點賦鄰接點位置pi - nextarc = G.verticesi.firstarc;/頭插法，將tv結(jié)點插入到第i個單鏈表中G.verticesi.firstarc = pi;/ 插入鏈表G.verticesi pj - adjvex = i;pj - nextarc = G.verticesj.f

25、irstarc;G.verticesj.firstarc = pj;cout構(gòu)造成功!adjvex!=y)q=p;p=p-nextarc;if(!p)return 0;if (p=G.verticesx.firstarc)G.verticesx.firstarc=p-nextarc;elseq-nextarc=p-nextarc;delete p;p=G.verticesy.firstarc;q=G.verticesy.firstarc;while(p&p-adjvex!=x)q=p;p=p-nextarc;if(!p)return 0;if (p=G.verticesy.firstarc)G

26、.verticesy.firstarc=p-nextarc;elseq-nextarc=p-nextarc;delete p;return 1;typedef struct Nodeint data;struct Node *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;bool visited10;ArcNode *nextnode=NULL;/全局變量/得到i號頂點的第一個鄰接點int FirstAdjVex(MGraph &g,int i)ArcNode *p;p=g.verticesi.first