数据结构算法与应用-c++语言描述012

《数据结构算法与应用-c++语言描述012》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载第12章图恭喜！你已经成功穿越了“树”的森林，下面要学习图这种数据结构。令人惊叹的是，图可以用来描述成千上万的实际问题，不过，我们仅研究其中的一小部分。本章的主要内容如下：¥图的若干术语：顶点，边，邻接，关联，度，回路，路径，连通构件，生成树。¥图的三种类型：无向图，有向图和加权的图。¥图的常用表示方法：邻接矩阵，邻接链表和邻接压缩表。¥图的标准搜索方法：宽度优先搜索和深度优先搜索。¥在图中寻找路径，在无向图中寻找连通构件以及在无向连通图中寻找生成树的算法。¥如何把抽象数据类型表示成一个抽象类。本章所使用的新的C++特征是：抽象类，虚函数和虚基类。12.1基本概念简单地说，图（gra

2、ph）是一个用线或边连接在一起的顶点或节点的集合。正式一点的说法是，图G=(V,E)是一个V和E的有限集合，元素V称为顶点（vertice,也叫作节点或点），元素E称为边（edge,也叫作弧或连线），E中的每一条边连接V中两个不同的顶点。可以用（i，j）来表示一条边，其中i和j是E所连接的两个顶点。一般来说，图是由回路和边组成，如图12-1所示。在图12-1中有些边是带方向的（带箭头），而有些边是不带方向的。带方向的边叫有向边（directededge），而不带方向的边叫无向边（undirectededge）。对无向边来说，(i,j)和(j,i)是一样的；而对有向边来说，它们是不同的。前

3、者的方向是从i到j，后者是从j到i。当且仅当(i,j)是图中的边时，顶点i和j是邻接的（adjacent）。边(i,j)关联（incident）于顶点i和j。图12-1a中的顶点1和2是邻接的，顶点1和3，1和4，2和3，3和4也是邻接的，除此之外，这个图中没有其他邻接的顶点。边（1，2）关联于顶点1和2，（2，3）关联于顶点2和3。a)b)c)图12-1图有些书中用{i,j}表示无向边，而用（i,j）表示有向边。还有一些书用（i,j）表示无向边，用表示有向边。本书对两种边使用同一符号（i,j），边有向与否可从上下文中看出。366第二部分数据结构下载在有向图中，有时候对邻接和关

4、联的概念作更精确的定义非常有用。有向边(i,j)是关联至（incidentto）顶点j而关联于（incidentfrom）顶点i。顶点i邻接至（adjacentto）顶点j，顶点j邻接于（adjacentfrom）顶点i。在图12-1c的图中，顶点2邻接于顶点1，而1邻接至顶点2。边（1，2）关联于顶点1而关联至顶点2。顶点4邻接至顶点3且邻接于顶点3。边（3，4）是关联于顶点3而关联至顶点4。对于无向图来说，“至”和“于”的含义是相同的。如果使用集合的表示方法，图12-1中的几个图可以用如下方法表示：G1=（V1，E1）；G2=（V2，E2）和G3=（V3，E3），其中：V={1,2,

5、3,4}；E={(1,2),(1,3),(2,3),(1,4),(3,4)}11V={1,2,3,4,5,6,7}；E={(1,2),(1,3),(4,5),(5,6),(5,7),(6,7)}22V={1,2,3,4,5}；E={(1,2),(2,3),(3,4),(4,3),(3,5),(5,4)}33如果图中所有的边都是无向边，那么该图叫作无向图（undirectedgraph），图12-1a和b都是无向图。如果所有的边都是有向的，那么该图叫作有向图（directedgraph），图12-1c是一个有向图。由定义知道，一个图中不可能包括同一条边的多个副本，因此，在无向图中的任意两个

6、顶点之间，最多只能有一条边。在有向图中的任意两个顶点之间，最多只能有一条边从顶点i到顶点j或从j到i。并且一个图中不可能包含自连边（self-edge），即(i,i)类型的边，自连边也叫作环（loop）。通常把无向图简称为图，有向图仍称为有向图（digraph）。在一些图和有向图的应用中，我们会为每条边赋予一个权或耗费，这种情况下，用术语加权有向图（weightedgraph）和加权无向图（weighteddigraph）来描述所得到的数据对象。术语网络（network）在这里是指一个加权有向图或加权无向图。实际上，这里定义的所有图的变化都可以看作网络的一种特殊情况——一个无向（有向）图

7、可以被看作是一个所有边具有相同权的无向（有向）网络。12.2应用无向图，有向图和网络常常用于电子网络的分析、化合物（特别是碳氢化合物）的分子结构研究、空中航线和通信网络的描述、项目策划、遗传研究、统计、社会科学及它各种领域。这一节将用图来阐述一些实际问题。例12-1[路径问题]城市中有许多街道，每一个十字路口都可以看作图中一个顶点，邻接两个十字路口之间的每一段街道既可以看作一条，也可以看作两条有向边。如果街道是双向的，就用两条有向边