圖的基本操作實(shí)驗(yàn)報告.doc

圖的基本操作實(shí)驗(yàn)報告 PB12001046 向禹1. 題目要求及其分析 建立一個圖，將圖進(jìn)行初始化，通過輸入圖的結(jié)點(diǎn)信息構(gòu)建圖的鄰接鏈表，對圖的結(jié)構(gòu)進(jìn)行深度和廣度優(yōu)先遍歷，由此構(gòu)建圖的最小生成樹。要求：輸入圖的各個結(jié)點(diǎn)信息建立圖的鄰接鏈表，以鄰接表為存儲結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列，同時以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別利用普利姆算法和克魯斯卡爾算法求圖的最小生成樹。2. 設(shè)計概要首先根據(jù)圖的存儲結(jié)構(gòu)定義圖的鏈表結(jié)構(gòu)（包括頂點(diǎn)關(guān)系類型，與弧或邊相關(guān)的信息，指向下一個結(jié)點(diǎn)的指針,圖的當(dāng)前頂點(diǎn)數(shù)與邊數(shù)鄰接矩陣等），采用二維數(shù)組形式存儲圖的鄰接矩陣，以鄰接表來作為圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個結(jié)點(diǎn)由鄰接點(diǎn)域，鏈域和數(shù)據(jù)域組成，由此可構(gòu)造圖G。圖的深度優(yōu)先遍歷：從某個頂點(diǎn)v出發(fā)訪問，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到所有與v相鄰的頂點(diǎn)都被訪問到，若途中尚有頂點(diǎn)未被訪問，則另選途中一個未被訪問的電作為起始點(diǎn)，重復(fù)上述過程直到所有頂點(diǎn)被訪問到。圖的廣度優(yōu)先遍歷：從v出發(fā)，依次訪問v和v的未被訪問的鄰接點(diǎn)，然后從這些鄰接點(diǎn)出發(fā)訪問它們的鄰接點(diǎn)，直到所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到，若尚有未被訪問到的頂點(diǎn)，則選取一個頂點(diǎn)重復(fù)上述步驟，直到所有頂點(diǎn)被訪問到。最小生成樹：假設(shè)聯(lián)通網(wǎng)N=（V,E），則令最小生成樹的初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V,)，圖中每個分量自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則社區(qū)此邊額選擇下一條代價最小的邊。依次類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。3詳細(xì)設(shè)計（主要算法步驟描述） typedef struct ArcCell /VRtype是頂點(diǎn)關(guān)系類型，對無權(quán)圖，用1或0 VRType adj; /表示相鄰否；對帶權(quán)圖，則為權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點(diǎn)向量 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)輸和弧數(shù)GraghKind kind; /圖的種類標(biāo)志 Mgragh; Status CreateUDN(Mgragh &G) /采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無向網(wǎng)G scanf(&G.vexnum,&G.arcnum,&IncInfo); /IncInfo為0則各弧不含其它信息 for(i=0;iG.vexnum;+i); /初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL;/adj,info for(k=0;kG.arcnum;+K) /構(gòu)造鄰接矩陣 scanf(&v1,&v2,&w); /輸入一條邊依附的頂點(diǎn)及權(quán)值 i=LocateVex(G,v1);j= LocateVex(G,v2); /確定v1,v2在G中的位置 G.arcij.adj=w; / 弧的權(quán)值 if(IncInfo)Input(*G.); /若弧含有相關(guān)信息，則輸入 G.arcsji=G.arcsij; return OK; typedef struct Arcnode int adjvex; /該弧指向的頂點(diǎn)位置 struct *nextarc; /指向下一條弧的指針 INfoType *info; /該弧相關(guān)信息的指針 Arcnode; typedef struct Vnode VertexType data; /頂點(diǎn)信息 ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧的指針 VNode,AdjListMAX_VERTEX_NUM; Typedef struct AdjList vertices; int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; /圖的種類標(biāo)志 ALGragh； void DFS_traverse_Grapg(ALGraph G) /深度優(yōu)先遍歷int v ; for (v=0 ; vG.vexnum ; v+) Visitedv=FALSE ; /* 訪問標(biāo)志初始化 */ for (v=0 ; vG.vexnum ; v+) if (!Visitedv) DFS(G , v); /60 void BFS (ALGraph G, int k) /廣度優(yōu)先遍歷int v ,w; LinkNode *p ; Queue Q ; Q.front=Q.rear=0 ; /* 建立空隊列并初始化 */ for (w=0 ; wadjvex) Visit(p-adjvex) ; Visitedp-adjvex=TRUE ; /80 Q.elem+Q.rear=p-adjvex ; p=p-nextarc ; /* end while */MSTEdge *Prim_MST(AdjGraph *G , int u) /* 從第u個頂點(diǎn)開始構(gòu)造圖G的最小生成樹 */ MSTEdge TE; / 存放最小生成樹n-1條邊的數(shù)組指針 /150 int j , k , v , min ; for (j=0; jvexnum; j+) closedgej.adjvex=u; closedgej.lowcost=G-adjju ; /* 初始化數(shù)組closedgen */ closedgeu.lowcost=0 ; /* 初始時置U=u */ TE=(MSTEdge *)malloc(G-vexnum-1)*sizeof(MSTEdge) ; for (j=0; jvexnum-1; j+) min= INFINITY ; for (v=0; vvexnum; v+) /160 if (closedgev.lowcost!=0& closedgev.Lowcostmin) min=closedgev.lowcost ; k=v ; TEj.vex1=closedgek.adjvex ; TEj.vex2=k ;TEj.weight=closedgek.lowcost ;closedgek.lowcost=0 ; /* 將頂點(diǎn)k并入U中 */for (v=0; vvexnum; v+) if (G-adjvkadjvk ; closedgev.adjvex=k ; /* 修改數(shù)組closedgen的各個元素的值 */return(TE) ; /* 求最小生成樹的Prime算法 MSTEdge *Kruskal_MST(ELGraph *G) /* 用Kruskal算法構(gòu)造圖G的最小生成樹 */ MSTEdge TE ; int j, k, v, s1, s2, Vset ; WeightType w ; Vset=(int *)malloc(G-vexnum*sizeof(int) ; for (j=0; jvexnum; j+) Vsetj=j ; /* 初始化數(shù)組Vsetn */ sort(G-edgelist) ; /* 對表按權(quán)值從小到大排序 */ j=0 ; k=0 ; while (kvexnum-1&jedgenum) s1=VsetG-edgelistj.vex1 ; s2=VsetG-edgelistj.vex2 ; /* 若邊的兩個頂點(diǎn)的連通分量編號不同, 邊加入到TE中 */ if(s1!=s2) TEk.vex1=G-edgelistj.vex1 ; TEk.vex2=G-edgelistj.vex2 ; TEk.weight=G-edgelistj.weight ; k+ ; for(v=0; vvexnum; v+) if (Vsetv=s2) Vsetv=s1 ; j+ ; free(Vset) ; return(TE) ; /* 求最小生成樹的Kruskal算法 */4.源程序代碼#include#includetypedef MAX 20typedef struct ArcCellint adj; char *info; ArcCell,AdjMatrix;#define MAX_VEX 30 /* 最大頂點(diǎn)數(shù) */typedef int InfoType;typedef struct Node /10 int adjvex ; / 鄰接點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的位置(下標(biāo)) int info ; / 與邊或弧相關(guān)的信息, 如權(quán)值 struct Node *next ; / 指向下一個表結(jié)點(diǎn)EdgeNode;typedef struct Node char vertex; / 頂點(diǎn)信息 EdgeNode *firstarc ; / 指向第一個表結(jié)點(diǎn) VNode; / 頂點(diǎn)結(jié)點(diǎn)類型定義typedef struct int vnum ; /20 int enum; VNode AdjListMAX_VEX ;ALGraph ; / 圖的結(jié)構(gòu)定義 void Create_Graph(ALGraph &G) printf(“請輸入圖的頂點(diǎn)樹、邊數(shù)：”) ; scanf(“%d,%d”, &G.vnum,&G.enum) ; for(i=0;ivnum;i+) /建立頂點(diǎn)表 G.AdjListi.vertex =getchar( ); /讀入頂點(diǎn)信息 G.AdjListi.firstarc=NULL; /邊表頭指針置空 /30 for (k=0 ; kadjvex=j; p-next=G.AdjListi.firstarc; G.AdjListi.firstarc=p ; p=(EdgeNode*)malloc(sizeof(EdgeNode); p-adjvex=i; p-next=G.AdjListj.firstarc; G.AdjListj.firstarc=p ; /40 typedef emnu FALSE , TRUE BOOLEAN ;BOOLEAN VisitedMAX_VEX ;void DFS(ALGraph G , int v) LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置訪問標(biāo)志，訪問頂點(diǎn)v */ p=G.AdjListv.firstarc; /* 鏈表的第一個結(jié)點(diǎn) */ while (p!=NULL) /50 if (!Visitedp-adjvex) DFS(G, p-adjvex) ; /* 從v的未訪問過的鄰接頂點(diǎn)出發(fā)深度優(yōu) */ p=p-next ; void DFS_traverse_Grapg(ALGraph G) int v ; for (v=0 ; vG.vexnum ; v+) Visitedv=FALSE ; /* 訪問標(biāo)志初始化 */ for (v=0 ; vG.vexnum ; v+) if (!Visitedv) DFS(G , v); /60 typedef struct Queue int elemMAX_VEX ; int front , rear ;Queue ; /* 定義一個隊列保存將要訪問頂點(diǎn) */void BFS (ALGraph G, int k) int v ,w; LinkNode *p ; Queue Q ; Q.front=Q.rear=0 ; /* 建立空隊列并初始化 */ for (w=0 ; wadjvex) Visit(p-adjvex) ; Visitedp-adjvex=TRUE ; /80 Q.elem+Q.rear=p-adjvex ; p=p-nextarc ; /* end while */ typedef struct CSNode ElemType data ; struct CSNode *firstchild , *nextsibling ;CSNode ; /90CSNode *DFStree(ALGraph *G , int v) /DFStree算法CSNode *T , *ptr , *q ; LinkNode *p ; int w ; Visitedv=TRUE ; T=(CSNode *)malloc(sizeof(CSNode) ; T-data=G-AdjListv.data ; T-firstchild=T-nextsibling=NULL ; / 建立根結(jié)點(diǎn) q=NULL ; p=G-AdjListv.firstarc ; while(p!=NULL) /100 w=p-adjvex ; if(!Visitedw) /* 子樹根結(jié)點(diǎn) */ptr=DFStree(G,w) ; if(q=NULL) T-firstchild=ptr ; else q-nextsibling=ptr ; q=ptr ; p=p-nextarc ; return(T) ; /110 CSNode *BFStree(ALGraph *G ,int v) CSNode *T , *ptr , *q ; LinkNode *p ; Queue *Q ; int w , k ; Q=(Queue *)malloc(sizeof(Queue) ; Q-front=Q-rear=0 ; /*建立空隊列并初始化*/ Visitedv=TRUE; T=(CSNode *)malloc(sizeof(CSNode) ; T-data=G-AdjListv.data ; /120 T-firstchild=T-nextsibling=NULL ; / 建立根結(jié)點(diǎn) Q-elem+Q-rear=v ; /* v入隊 */ while (Q-front!=Q-rear) w=Q-elem+Q-front ; q=NULL ; p=G-AdjListw.firstarc ; while (p!=NULL)k=p-adjvex ; if(!Visitedk) Visitedk=TRUE; /130 ptr=(CSNode *)malloc(sizeof(CSNode) ; ptr-data=G-AdjListk.data ; ptr-firstchild=T-nextsibling=NULL ; if (q=NULL) T-firstchild=ptr ; else q-nextsibling=ptr ; q=ptr ; Q-elem+Q-rear=k ; /* k入對 */ /* end if */ p=p-nextarc ; /* end while p */ /140 /* end whil Q */ return(T);typedef struct MSTEdge int vex1, vex2 ; /* 邊所依附的圖中兩個頂點(diǎn) */ double weight ; /* 邊的權(quán)值 */MSTEdge ;#define INFINITY MAX_VAL /* 最大值 */ MSTEdge *Prim_MST(AdjGraph *G , int u) /* 從第u個頂點(diǎn)開始構(gòu)造圖G的最小生成樹 */ MSTEdge TE; / 存放最小生成樹n-1條邊的數(shù)組指針 /150 int j , k , v , min ; for (j=0; jvexnum; j+) closedgej.adjvex=u; closedgej.lowcost=G-adjju ; /* 初始化數(shù)組closedgen */ closedgeu.lowcost=0 ; /* 初始時置U=u */ TE=(MSTEdge *)malloc(G-vexnum-1)*sizeof(MSTEdge) ; for (j=0; jvexnum-1; j+) min= INFINITY ; for (v=0; vvexnum; v+) /160 if (closedgev.lowcost!=0& closedgev.Lowcostmin) min=closedgev.lowcost ; k=v ; TEj.vex1=closedgek.adjvex ; TEj.vex2=k ;TEj.weight=closedgek.lowcost ;closedgek.lowcost=0 ; /* 將頂點(diǎn)k并入U中 */for (v=0; vvexnum; v+) if (G-adjvkadjvk ; closedgev.adjvex=k ; /* 修改數(shù)組closedgen的各個元素的值 */return(TE) ; /* 求最小生成樹的Prime算法 */ MSTEdge *Kruskal_MST(ELGraph *G) /* 用Kruskal算法構(gòu)造圖G的最小生成樹 */ MSTEdge TE ; int j, k, v, s1, s2, Vset ; WeightType w ; Vset=(int *)malloc(G-vexnum*sizeof(int) ; for (j=0; jvexnum; j+) Vsetj=j ; /* 初始化數(shù)組Vsetn */ sort(G-edgelist) ; /* 對表按權(quán)值從小到大排序