实验5 加权图

《实验5 加权图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验5加权图目标l利用一个结点列表和邻接矩阵创建一个加权图的实现程序l开发一个例程，查找图中每两个项点间的最小(或者最短)代价路径l增加顶点颜色，并且实现一个方法，测试一个图是否有正确的颜色l探讨四色原理，产生一个图，如果少于五种颜色，则无法为这个图创建一种正确颜色概述仅利用线性或者层次数据结构，有些关系不容易表达。在一个高速公路网络中，两个城市的连接关系就是这样一种关系。虽然在高速公路网络中，利用线性（例如，只有一条街道）或者层次（紧急通道和出口）结构，也可以描述城市之间的关系，但是，我们都多次在环形道上开过车，并

2、且已经知道大多数高速公路网络都不是线性和层次的。现在，我们所需要的就是一个数据结构，利用它，我们将每个城市和网络中其他任何城市连结起来。这种类型的数据结构就叫图。像树一样，一个图包含一系列节点(称为顶点)和一系列边。与树不一样的是，图中的边能连结任何两个顶点，而不仅是父节点和它的子节点。下图就表示一个简单的高速公路网络。在图中的每个顶点都有一个惟一的标签来标记一个特定的城市。每条边都有一个权值来标记经过相应路径的代价(根据距离、时间、或者金钱来衡量)。请记住图中的边是无向的；也就是说，如果有一条边连结顶点A和B，那么

3、这条边既可以从A指向B，也可以从B指向A。形成的这个加权的无向图就表示了在这条高速公路网络中，在两个城市间通过公路旅行的代价。在这个实验中，重点是加权无向图的实现和应用。加权图ADT数据项:图中的每个顶点都有一个标签(字串类型)，它是顶点的惟一标识符。顶点还可以包括其他数据。结构:在图中，利用一系列无向边来表示两个顶点之间的关系，每条边连结两个顶点。这些边共同定义了顶点间的一种对称关系。在加权图中，每条边都有一个权值，用来标记通过这条边的代价。运算InitWtGraph(intmaxNumber)要求：无结果：创建一

4、个空的图。为其分配足够的内存空间，它包含maxNumber个顶点的图。DeWtGraph()要求：无结果：释放(free)存储图占用的空间。voidinsertVertex(VertexnewVertex)要求：图不满。结果：添加newVertex到图中。如果这个顶点在图中已存在，则更新它。voidinsertEdge(char*v1,char*v2,intwt)要求：图包括顶点v1和v2。结果：添加一条连接v1和v2的无向边到图中。边的权值为wt,如果已经存在连接这两个顶点的边，则更新边的权值。boolretrie

5、veVetex(char*v,Vertex&vData)要求：无结果：在图中搜索顶点v。如果发现这个顶点，则复制这个顶点的数据到vData，然后返回true,否则返回false,vData值不确定。boolgetEdgeWeight(char*v1,char*v2,int&wt)要求：图包括顶点v1和v2。结果：在图中搜索连接v1和v2的无向边，如果发现这条边，则返回true,并且用wt返回这条边的权值，否则返回false,wt值不确定。voidremoveVertex(char*v)要求：图包括顶点v。结果：从图中

6、删除顶点v。voidremoveEdge(char*v1,char*v2)要求：图包括顶点v1和v2。结果：从图中删除连接v1和v2的无向边。voidclear()要求：无结果：删除图中的所有顶点和边。boolisEmpty()要求：无结果：如果图为空(无顶点)，则返回true，否则，返回false。boolisFull()要求：无结果：如果图为满，则返回true，否则，返回false。voidshowStructure()要求：无结果：以数组形式输出图的顶点，以邻接矩阵形式输出边(带权值)。如果图为空，则输出“Em

7、ptygraph”。这个运算只用于测试/调试目的。实验5作业单姓名小组____________________日期____________________请在教师布置的练习时应的已布置列上打一个钩（√）。在提交这个实验的一组材料前面附上这个作业单。练习已布置：打钩或列出练习编号已完成实验前练习过渡练习实验中练习1实验中练习2实验中练习3实验后练习1实验后练习2总计实验5实验前练习姓名小组____________________日期____________________可以用许多方式表示一个图。在这个实验中，使用数组

8、存储一系列顶点，并且使用邻接矩阵存储边。在邻接矩阵中下标(j,k)表示从顶点到顶点k的边。对于一个加权图来说，每个矩阵项包含相应边的权值。经过特定选择的权值可以用来表示图中不存在的边。下图显示了顶点列表和邻接矩阵。‘-’用来标记图中不存在的边。顶点列表邻接矩阵索引标记从/到0123401234ABCDE01234-50100--50--93-1