实验报告
2013-2014学年第1 学期 任课老师： 刘安丰
课程名称 数据结构 实验名称 实验环境 C++ 实验目的和内容要求 实验三 图的操作算法 班级 学号 姓名 实验时间 12月5号 实验三 图的操作算法 一、实验要求与内容 实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图的最小生成树、拓扑排序、最短路径等。 二、实验目的 1．掌握图的基本存储方法。 2．掌握有关图的操作算法并用高级语言实现。 3．熟练掌握图的两种搜索路径的遍历方法。 4. 掌握图的有关应用。 实验过程记录 1、最小生成树 Prim\\Kruskal算法 #include #include #include #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.vexs[i]; for(i=0;i> 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; 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 dgevalue[j].value) { temp = dgevalue[i].value; dgevalue[i].value = dgevalue[j].value; dgevalue[j].value = temp; ch1 = dgevalue[i].ch1; dgevalue[i].ch1 = dgevalue[j].ch1; dgevalue[j].ch1 = ch1; ch2 = dgevalue[i].ch2; dgevalue[i].ch2 = dgevalue[j].ch2; dgevalue[j].ch2 = ch2; } } } } void main() { int i,j; MGraph G; char u; Dgevalue dgevalue; CreateUDG(G,dgevalue); cout<<\图的邻接矩阵为：\ for(i=0; i>u; cout<<\构成最小代价生成树的边集为：\\n\ MiniSpanTree_PRIM(G,u); cout<<\克鲁斯科尔算法=============\\n\ cout<<\构成最小代价生成树的边集为：\\n\ MiniSpanTree_KRSL(G,dgevalue); } 2、拓扑排序 #include \ #define MAX_VERTEX_NUM 20
