图的基本操作实验报告 (2)
图的基本操作实验报告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
