圖的基本操作實驗報告 PB12001046 向禹1. 題目要求及其分析 建立一個圖，將圖進行初始化，通過輸入圖的結點信息構建圖的鄰接鏈表，對圖的結構進行深度和廣度優(yōu)先遍歷，由此構建圖的最小生成樹。要求：輸入圖的各個結點信息建立圖的鄰接鏈表，以鄰接表為存儲結構，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列，同時以用戶指定的結點為起點，分別利用普利姆算法和克魯斯卡爾算法求圖的最小生成樹。2. 設計概要首先根據(jù)圖的存儲結構定義圖的鏈表結構（包括頂點關系類型，與弧或邊相關的信息，指向下一個結點的指針,圖的當前頂點數(shù)與邊數(shù)鄰接矩陣等），采用二維數(shù)組形式存儲圖的鄰接矩陣，以鄰接表來作為圖的鏈式存儲結構，每個結點由鄰接點域，鏈域和數(shù)據(jù)域組成，由此可構造圖G。圖的深度優(yōu)先遍歷：從某個頂點v出發(fā)訪問，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直到所有與v相鄰的頂點都被訪問到，若途中尚有頂點未被訪問，則另選途中一個未被訪問的電作為起始點，重復上述過程直到所有頂點被訪問到。圖的廣度優(yōu)先遍歷：從v出發(fā)，依次訪問v和v的未被訪問的鄰接點，然后從這些鄰接點出發(fā)訪問它們的鄰接點，直到所有已被訪問的頂點的鄰接點都被訪問到，若尚有未被訪問到的頂點，則選取一個頂點重復上述步驟，直到所有頂點被訪問到。最小生成樹：假設聯(lián)通網(wǎng)N=（V,E），則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,)，圖中每個分量自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則社區(qū)此邊額選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。3詳細設計（主要算法步驟描述） typedef struct ArcCell /VRtype是頂點關系類型，對無權圖，用1或0 VRType adj; /表示相鄰否；對帶權圖，則為權值類型 InfoType *info; /該弧相關信息的指針 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點向量 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當前頂點輸和弧數(shù)GraghKind kind; /圖的種類標志 Mgragh; Status CreateUDN(Mgragh &G) /采用數(shù)組（鄰接矩陣）表示法，構造無向網(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) /構造鄰接矩陣 scanf(&v1,&v2,&w); /輸入一條邊依附的頂點及權值 i=LocateVex(G,v1);j= LocateVex(G,v2); /確定v1,v2在G中的位置 G.arcij.adj=w; / 弧的權值 if(IncInfo)Input(*G.); /若弧含有相關信息，則輸入 G.arcsji=G.arcsij; return OK; typedef struct Arcnode int adjvex; /該弧指向的頂點位置 struct *nextarc; /指向下一條弧的指針 INfoType *info; /該弧相關信息的指針 Arcnode; typedef struct Vnode VertexType data; /頂點信息 ArcNode *firstarc; /指向第一條依附該頂點的弧的指針 VNode,AdjListMAX_VERTEX_NUM; Typedef struct AdjList vertices; int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù) int kind; /圖的種類標志 ALGragh； void DFS_traverse_Grapg(ALGraph G) /深度優(yōu)先遍歷int v ; for (v=0 ; vG.vexnum ; v+) Visitedv=FALSE ; /* 訪問標志初始化 */ 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個頂點開始構造圖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 ; /* 將頂點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的最小生成樹 */ 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) ; /* 對表按權值從小到大排序 */ j=0 ; k=0 ; while (kvexnum-1&jedgenum) s1=VsetG-edgelistj.vex1 ; s2=VsetG-edgelistj.vex2 ; /* 若邊的兩個頂點的連通分量編號不同, 邊加入到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 /* 最大頂點數(shù) */typedef int InfoType;typedef struct Node /10 int adjvex ; / 鄰接點在頭結點數(shù)組中的位置(下標) int info ; / 與邊或弧相關的信息, 如權值 struct Node *next ; / 指向下一個表結點EdgeNode;typedef struct Node char vertex; / 頂點信息 EdgeNode *firstarc ; / 指向第一個表結點 VNode; / 頂點結點類型定義typedef struct int vnum ; /20 int enum; VNode AdjListMAX_VEX ;ALGraph ; / 圖的結構定義 void Create_Graph(ALGraph &G) printf(“請輸入圖的頂點樹、邊數(shù)：”) ; scanf(“%d,%d”, &G.vnum,&G.enum) ; for(i=0;ivnum;i+) /建立頂點表 G.AdjListi.vertex =getchar( ); /讀入頂點信息 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 ; /* 置訪問標志，訪問頂點v */ p=G.AdjListv.firstarc; /* 鏈表的第一個結點 */ while (p!=NULL) /50 if (!Visitedp-adjvex) DFS(G, p-adjvex) ; /* 從v的未訪問過的鄰接頂點出發(fā)深度優(yōu) */ p=p-next ; void DFS_traverse_Grapg(ALGraph G) int v ; for (v=0 ; vG.vexnum ; v+) Visitedv=FALSE ; /* 訪問標志初始化 */ for (v=0 ; vG.vexnum ; v+) if (!Visitedv) DFS(G , v); /60 typedef struct Queue int elemMAX_VEX ; int front , rear ;Queue ; /* 定義一個隊列保存將要訪問頂點 */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 ; / 建立根結點 q=NULL ; p=G-AdjListv.firstarc ; while(p!=NULL) /100 w=p-adjvex ; if(!Visitedw) /* 子樹根結點 */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 ; / 建立根結點 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 ; /* 邊所依附的圖中兩個頂點 */ double weight ; /* 邊的權值 */MSTEdge ;#define INFINITY MAX_VAL /* 最大值 */ MSTEdge *Prim_MST(AdjGraph *G , int u) /* 從第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 ; /* 將頂點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的最小生成樹 */ 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) ; /* 對表按權值從小到大排序