实验报告
2013-2014 学年第 1 学期 任课老师： 刘安丰 课程名称 实验名称 实验环境 C++ 实验目的和内容要求 数据结构 班级 学号 实验时间 姓名 12 月 5 号
实验三
图的操作算法
作算法
实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图 的最小生成树、拓扑排序、最短路径等。 二、实验目的 1．掌握图的基本存储方法。 2．掌握有关图的操作算法并用高级语言实现。 3．熟练掌握图的两种搜索路径的遍历方法。 4. 掌握图的有关应用。
G.arcs[j][i].adj = G.arcs[i][j].adj; } return OK; } int LocateVex(MGraph G,char ch) //确定节点 ch 在图 G.vexs 中的位置 { int a ; for(int i=0; i<G.vexnum; i++) { if(G.vexs[i] == ch) a=i; } return a; } //typedef struct Pnode //用于普利姆算法 //{ // char adjvex; //节点 // double lowcost; //权值 //}Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集 U 到 V-U 的代价最小的边的辅助数组定义 void MiniSpanTree_PRIM(MGraph G,char u)//普利姆算法求最小生成树 { int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; j<G.vexnum; j++) { if(j != k) { closedge[j].adjvex = u; closedge[j].lowcost = G.arcs[k][j].adj; } } closedge[k].lowcost = 0; for(i=1; i<G.vexnum; i++) { k = Minimum(G,closedge); cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl; closedge[k].lowcost = 0; for(j=0; j<G.vexnum; ++j) { if(G.arcs[k][j].adj < closedge[j].lowcost) { closedge[j].adjvex = G.vexs[k]; closedge[j].lowcost= G.arcs[k][j].adj; } } }
实验过程记录 1、最小生成树
Prim\Kruskal 算法
#include<stdio.h> #include<stdlib.h> #include<iostream> #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 using namespace std; typedef struct Arcell { double adj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集 U 到 V-U 的代价最小的边的辅助数组定义 typedef struct Knode //用于算法中存储一条边及其对应的 2 个节点 { char ch1; //节点 1 char ch2; //节点 2 double value;//权值 }Knode,Dgevalue[MAX_VERTEX_NUM]; //----------------------------------------------------------------------------------int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); //----------------------------------------------------------------------------------int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵 { int i,j,k; cout<<"请输入图中节点个数和边/弧的条数："; cin>>G.vexnum>>G.arcnum; cout<<"请输入节点："; for(i=0;i<G.vexnum;++i) cin>>G.vexs[i]; for(i=0;i<G.vexnum;++i)//初始化数组 { for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=MAX; } } cout<<"请输入一条边依附的定点及边的权值："<<endl; for(k=0;k<G.arcnum;++k) { cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value; i = LocateVex(G,dgevalue[k].ch1 ); j = LocateVex(G,dgevalue[k].ch2 ); G.arcs[i][j].adj = dgevalue[k].value;