图与网络
01基本概念
介绍:图分为无向图和有向图。一个无向图(undirected graph)G是由一个非空有限集合 V(G)和V(G)中某些元素的无序对集合E(G)构成的二元组,记为G=(V(G),E(G))。V(G)称为顶点集,E(G)称为边集。而有向图中边是有方向的。
网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说,算法的好坏与网络的具体表示方法,以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的 5 种常用表示方法:邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。
邻接矩阵表示法:
邻接矩阵表示法是将图以邻接矩阵(adjacency matrix)的形式存储在计算机中。图G=(V,A)的邻接矩阵定义如下:也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为 1;否则为 0。可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有2n 个元素中,只有 m个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络中查找弧的时间。
关联矩阵表示法:
关联矩阵表示法是将图以关联矩阵(incidence matrix)的形式存储在计算机中,图G=(V,A)的关联矩阵B是如下定义的:
也就是说,在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如果一个节点是一条弧的起点,则关联矩阵中对应的元素为1;如果一个节点是一条弧的终点,则关联矩阵中对应的元素为-1;如果一个节点与一条弧不关联,则关联矩阵中对应的元素为 0。对于简单图,关联矩阵每列只含有两个非零元(一个+1,一个-1)。可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有 nm 个元素中,只有2m个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质,因此它在网络优化中是非常重要的概念。
弧表表示法:
弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表,也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需2m个存储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对应地用额外的存储单元表示。
邻接表表示法:
邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。
星形表示法:
星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点,它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表示。也就是说,在该数组中首先存放从节点 1 出发的所有弧,然后接着存放从节点2出发的所有孤,依此类推,最后存放从节点 n 出发的所有孤。对每条弧,要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号,只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星形(forward star)表示法。
对于网络图的表示法:
① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如 FORTRAN 语言等)也容易实现。邻接表表示法对那些提供指针类型的语言(如 C 语言等)是方便的,且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工作量较大。
② 当网络不是简单图,而是具有平行弧(即多重弧)时,显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③ 上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有方向,因此可能需要做一些自然的修改。例如,可以在计算机中只存储邻接矩阵的一半信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0 和 +1,而不含有-1,因为此时不区分边的起点和终点。又如,在邻接表和星形表示法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。
02树
介绍:连通的无圈图叫做树,记之为T。若图G满足V(G)=V(T),
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)