第6次-圖的應(yīng)用實驗-實驗題目與報告書

1、精選優(yōu)質(zhì)文檔-傾情為你奉上淮海工學(xué)院計算機科學(xué)系實驗報告書課程名： 數(shù)據(jù)結(jié)構(gòu) 題 目： 實驗六：圖的應(yīng)用實驗 求關(guān)鍵路徑及其應(yīng)用 班 級： 網(wǎng)絡(luò)072 學(xué) 號： 姓 名： 田靜 評語：成績： 指導(dǎo)教師： 朱敏 批閱時間：2008 年11 月 17 日專心-專注-專業(yè)圖的應(yīng)用實驗報告要求1目的與要求:1）掌握AOE網(wǎng)的鄰接表存儲結(jié)構(gòu)表示及創(chuàng)建算法的c語言實現(xiàn)；2）理解AOE網(wǎng)的拓?fù)渑判蛩惴?算法7.12)的實現(xiàn)原理及應(yīng)用；3）掌握AOE網(wǎng)關(guān)鍵路徑的計算算法（算法7.13，7.14）及C語言實現(xiàn)與應(yīng)用；4）按照實驗題目要求獨立正確地完成實驗內(nèi)容（提交程序清單及相關(guān)實驗數(shù)據(jù)與運行結(jié)果）；5）認(rèn)真書寫

2、實驗報告,并按時提交。2 實驗內(nèi)容或題目題目： 圖的應(yīng)用實驗計算AOE網(wǎng)的關(guān)鍵路徑內(nèi)容：按照圖的“鄰接表”存儲結(jié)構(gòu)表示AOE網(wǎng)，實現(xiàn)求其關(guān)鍵路徑的算法，并驗證如下圖1所示AOE網(wǎng)的關(guān)鍵路徑。圖1 AOE網(wǎng)876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=43 實驗步驟與源程序#define INFINITY 32768 #define True 1#define False 0#define Error -1#define NULL 0#define Ok 1#define MAX_VERTEX_NUM 9 typedef enumDG

3、, DN, UDG, UDN GraphKind; typedef int VertexData;typedef struct ARCNNODEint adjvex; int weight; struct ARCNNODE *nextarc; typedef struct VERTEXNODEVertexData data; ArcNode *firstarc; VertexNode;typedef struct VertexNode vertexMAX_VERTEX_NUM; int vexnum,arcnum; GraphKind kind; AdjList; #include "

4、;AdjList.h"#include "STACK.h"#include <stdio.h>int veMAX_VERTEX_NUM; int VN9=3,1,1,1,2,1,1,1,0;int AN112=1,6, 2,4, 3,5, 4,1, 4,1, 5,2, 6,9, 7,7, 7,4, 8,2, 8,4;CreateAdjList(AdjList *G)int i,j;int arc=0;ArcNode *arcn,*pre;G->vexnum=9;for( i=0;i<G->vexnum;i+) G->vertex

5、i.data=i; G->vertexi.firstarc=NULL; if(VNi>0) arcn=(ArcNode*)malloc(sizeof(ArcNode); arcn->nextarc=NULL; arcn->adjvex=ANarc0; arcn->weight=ANarc1; G->vertexi.firstarc=arcn; pre=arcn; arc+; for(j=1;j<VNi;j+) arcn=(ArcNode*)malloc(sizeof(ArcNode); arcn->nextarc=NULL; arcn->a

6、djvex=ANarc0; arcn->weight=ANarc1; pre->nextarc=arcn; pre=arcn; arc+; printAdjList(AdjList *G)int i,j;int arc=0;ArcNode *arcn;printf("vexnum is %d: ",G->vexnum);for( i=0;i<G->vexnum;i+) printf("vertex%d's data is :%dn",i,G->vertexi.data); arcn=G->vertexi.

7、firstarc; while(arcn!=NULL) printf("%d->%d,weight:%d ",i,arcn->adjvex,arcn->weight); arcn=arcn->nextarc; printf("n");void FindID(AdjList G,int indegreeMAX_VERTEX_NUM) int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; for(i=0;i<G.vexnum;i+) p=G.vertexi.first

8、arc; while(p!=NULL) indegreep->adjvex+; p=p->nextarc; /* for */int TopoOrder(AdjList G,Stack *T) int count,i,j,k; ArcNode *p;int indegreeMAX_VERTEX_NUM; Stack S; InitStack(T); InitStack(&S); FindID(G,indegree); for(i=0;i<G.vexnum;i+) if(indegreei=0) Push(&S,i); count=0; for(i=0;i<

9、;G.vexnum;i+) vei=0; while(!IsEmpty(&S)Pop(&S,&j);Push(T,j);count+;p=G.vertexj.firstarc;while(p!=NULL) k=p->adjvex;if(-indegreek=0) Push(&S,k); if(vej+p->weight>vek) vek=vej+p->weight; p=p->nextarc; if(count<G.vexnum) return(Error); elsereturn(Ok);int CriticalPath(A

10、djList G) ArcNode *p; int i,j,k,dut,ei,li; char tag;int vlMAX_VERTEX_NUM; Stack T;if(!TopoOrder(G,&T) return(Error); for(i=0;i<G.vexnum;i+) vli=veG.vexnum-1; while(!IsEmpty(&T) Pop(&T,&j); p=G.vertexj.firstarc; while(p!=NULL) k=p->adjvex; dut=p->weight; if(vlk-dut<vlj) vl

11、j=vlk-dut; p=p->nextarc;for(j=0;j<G.vexnum;j+) p=G.vertexj.firstarc; while(p!=NULL) k=p->adjvex; dut=p->weight; ei=vej;li=vlk-dut; tag=(ei=li)?'*':' 'printf("%d,%d,%d,%d,%d,%cn",G.vertexj.data,G.vertexk.data,dut,ei,li,tag); p=p->nextarc; return(Ok); int main(

12、)AdjList G; CreateAdjList(&G);printAdjList(&G); CriticalPath(G);return 0;#include <malloc.h>#define OVERFLOW -1#define OK 0#define ERROR 1#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 1000#define STACKINCREMENT 10typedef int SElemType;typedef int Status;typedef struct STACK SEle

13、mType *base; SElemType *top; int stacksize;Stack;typedef struct STACK SqStack;typedef struct STACK *pSqStack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack *S);int StackLength(SqStack *S);SElemType GetTop(SqStack *S);Status Push(S

14、qStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status InitStack(SqStack *S) S->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S->base) return(OVERFLOW); S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK;Status DestroyStack(SqStack *S) free(S->bas

15、e); return OK;Status ClearStack(SqStack *S) S->top=S->base; return OK;Status IsEmpty(SqStack *S) if(S->top=S->base) return TRUE; else return FALSE;int StackLength(SqStack *S) int i; SElemType *p; i=0; p=S->top; while(p!=S->base) p+; i+; return i;SElemType GetTop(SqStack *S) if(S-&g

16、t;top=S->base) return ERROR; return *(S->top-1);Status Push(SqStack *S,SElemType e) *(S->top+)=e; return OK;Status Pop(SqStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*(-(S->top); return OK;4 測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）5 結(jié)果分析與實驗體會在對圖遍歷時，對于連通圖，無論是廣度優(yōu)先還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過程，即從任一頂點出發(fā)，便可以遍歷圖中的各個頂點。對于非連通圖，則需要多次調(diào)用搜索過程，而每次調(diào)用得到的頂點訪問序列恰為各連同分量中的頂點集。在圖的應(yīng)用問題中，常常需要找從一個頂點到另一個頂點的簡單