第6次-圖的應(yīng)用實(shí)驗(yàn)-實(shí)驗(yàn)題目與報(bào)告書

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

2、實(shí)驗(yàn)報(bào)告,并按時(shí)提交。2 實(shí)驗(yàn)內(nèi)容或題目題目： 圖的應(yīng)用實(shí)驗(yàn)計(jì)算AOE網(wǎng)的關(guān)鍵路徑內(nèi)容：按照?qǐng)D的“鄰接表”存儲(chǔ)結(jié)構(gòu)表示AOE網(wǎng)，實(shí)現(xiàn)求其關(guān)鍵路徑的算法，并驗(yàn)證如下圖1所示AOE網(wǎng)的關(guān)鍵路徑。圖1 AOE網(wǎng)876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=43 實(shí)驗(yàn)步驟與源程序#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 測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）5 結(jié)果分析與實(shí)驗(yàn)體會(huì)在對(duì)圖遍歷時(shí)，對(duì)于連通圖，無(wú)論是廣度優(yōu)先還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過(guò)程，即從任一頂點(diǎn)出發(fā)，便可以遍歷圖中的各個(gè)頂點(diǎn)。對(duì)于非連通圖，則需要多次調(diào)用搜索過(guò)程，而每次調(diào)用得到的頂點(diǎn)訪問(wèn)序列恰為各連同分量中的頂點(diǎn)集。在圖的應(yīng)用問(wèn)題中，常常需要找從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的簡(jiǎn)單