图的基本操作实验报告.doc

图的基本操作实验报告 PB12001046 向禹1. 题目要求及其分析 建立一个图，将图进行初始化，通过输入图的结点信息构建图的邻接链表，对图的结构进行深度和广度优先遍历，由此构建图的最小生成树。要求：输入图的各个结点信息建立图的邻接链表，以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列，同时以用户指定的结点为起点，分别利用普利姆算法和克鲁斯卡尔算法求图的最小生成树。2. 设计概要首先根据图的存储结构定义图的链表结构（包括顶点关系类型，与弧或边相关的信息，指向下一个结点的指针,图的当前顶点数与边数邻接矩阵等），采用二维数组形式存储图的邻接矩阵，以邻接表来作为图的链式存储结构，每个结点由邻接点域，链域和数据域组成，由此可构造图G。图的深度优先遍历：从某个顶点v出发访问，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到所有与v相邻的顶点都被访问到，若途中尚有顶点未被访问，则另选途中一个未被访问的电作为起始点，重复上述过程直到所有顶点被访问到。图的广度优先遍历：从v出发，依次访问v和v的未被访问的邻接点，然后从这些邻接点出发访问它们的邻接点，直到所有已被访问的顶点的邻接点都被访问到，若尚有未被访问到的顶点，则选取一个顶点重复上述步骤，直到所有顶点被访问到。最小生成树：假设联通网N=（V,E），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)，图中每个分量自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则社区此边额选择下一条代价最小的边。依次类推，直至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; /图的当前顶点输和弧数GraghKind kind; /图的种类标志 Mgragh; Status CreateUDN(Mgragh &G) /采用数组（邻接矩阵）表示法，构造无向网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; /图的当前顶点数和弧数 int kind; /图的种类标志 ALGragh； 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 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 */MSTEdge *Prim_MST(AdjGraph *G , int u) /* 从第u个顶点开始构造图G的最小生成树 */ MSTEdge TE; / 存放最小生成树n-1条边的数组指针 /150 int j , k , v , min ; for (j=0; jvexnum; j+) closedgej.adjvex=u; closedgej.lowcost=G-adjju ; /* 初始化数组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 ; /* 修改数组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 ; /* 初始化数组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 /* 最大顶点数 */typedef int InfoType;typedef struct Node /10 int adjvex ; / 邻接点在头结点数组中的位置(下标) 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(“请输入图的顶点树、边数：”) ; 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的未访问过的邻接顶点出发深度优 */ 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条边的数组指针 /150 int j , k , v , min ; for (j=0; jvexnum; j+) closedgej.adjvex=u; closedgej.lowcost=G-adjju ; /* 初始化数组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 ; /* 修改数组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 ; /* 初始化数组Vsetn */ sort(G-edgelist) ; /* 对表按权值从小到大排序