资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
图的基本操作实验报告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 或 0VRType adj; /表示相邻否;对带权图,则为权值类型InfoType *info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点输和弧数GraghKind kind; /图的种类标志Mgragh;Status CreateUDN(Mgragh &G) /采用数组(邻接矩阵)表示法,构造无向网 Gscanf(&G.vexnum,&G.arcnum,&IncInfo); /IncInfo 为 0 则各弧不含其它信息for(i=0;i的权值if(IncInfo)Input(*G.arcsij.info); /若弧含有相关信息,则输入G.arcsji=G.arcsij;return OK;typedef struct Arcnodeint adjvex; /该弧指向的顶点位置struct *nextarc; /指向下一条弧的指针INfoType *info; /该弧相关信息的指针Arcnode;typedef struct VnodeVertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;Typedef structAdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGragh;void DFS_traverse_Grapg(ALGraph G) /深度优先遍历int v ;for (v=0 ; vadjvex)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 条边的数组指针 /150int 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+) /160if (closedgev.lowcost!=0& closedgev.Lowcostvexnum; 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 ; /20int enum;VNode AdjListMAX_VEX ;ALGraph ; / 图的结构定义 void Create_Graph(ALGraph &G) printf(“请输入图的顶点树、边数:”) ;scanf(“%d,%d”, &G.vnum,&G.enum) ;for(i=0;iadjvex=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 ; /40typedef 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) /50if (!Visitedp-adjvex) DFS(G, p-adjvex) ; /* 从 v 的未访问过的邻接顶点出发深度优 */p=p-next ; void DFS_traverse_Grapg(ALGraph G) int v ;for (v=0 ; vadjvex)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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号