有向图及无向图的比较研究.ppt

《有向图及无向图的比较研究.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有向图及无向图的比较研究知识结构图的定义无向图与有向图无向图与有向图异同点图图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。一图的定义图G由两个集合构成，记作G=(V,E)其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。G1=(V1,E1)V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；

2、V0V4V3V1V2例G1图示G2图示有序对：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；V0V1V2V3G2=V2={v0v1,v2,v3}E2={,,,}有向图和无向图在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。表示从顶点x发向顶点y的边，x为始点，y为终点。V0V4V3V

3、1V2V0V1V2V3有向图：无向图：完全图:图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图图的应用举例：例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系V0V4V3V1V2V0V1V2V3异同点证明：若是

4、完全有向图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1)证明：从①可以直接推论出无向完全图的边数——因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。②完全无向图有n(n-1)/2条边。①完全有向图有n(n-1)条边。12341234图的邻接表表示图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：边表和顶点表。边表是单链表，用来存放边的信息；顶点表是数组，主要用来存放顶点本身的数据信息和该顶点邻接点的位置。adjvexweightnext边结点顶点结点1无向图的邻接表顶点：通常按编号

5、顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储该结点表示边（ViVj）,其中的1是Vj在一维数组中的位置例V0V4V3V1V2201234m-1V0V1V2V3V413422110034下标编号link2有向图的邻接表和逆邻接表1）有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储下标编号linkV0V1V2V312300123m-1例V0V1V2V32）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存

6、储V0V1V2V30123m-10023类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储例V0V1V2V32．从无向图的邻接表可以得到如下结论1）在G邻接表中，同一条边对应两个结点，所有链表中结点数目的一半为图中边数；2）顶点v的度：等于v对应线性链表的长度；3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点4）在G中增减边：要在两个单链表插入、删除结点；5）设存储顶点的一维数组大小为m(m图的顶点数n),图的边数为e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；3．从有向图的邻接表可以得到如下结

7、论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。适用于边稀疏的图邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50101010101010111010101110分析1：无向图的邻接矩阵是对称的；分析2：顶点Vi的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。顶点表：无向图的邻接矩阵如何表示？v1v2v3v5v4v4A000000000

8、00000000000000000101010101