第七章摘录

    图（Gaph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。
在图中的数据元素通常称做顶点（Vertex），V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若<v,w>∈VR，则〈v，w〉表示从v到的一条弧（Arc），且称v为弧尾（Tail）或初始点（Initial node），称w为弧头（Head）或终端点（Terminal node），此时的图称为有向图（Digraph）。若<v，w>∈VR必有<w，v>∈VR，即VR是对称的，则以无序对（v，w）代替这两个有序对，表示v和之间的一条边（Edge），此时的图称为无向图。
    我们用n表示图中顶点数目，用e表示边或弧的数目。在下面的讨论中，我们不考虑顶点到其自身的弧或边……那么，对于无向图，e的取值范围是0到n（n-1）/2。有n（n-1）/2条边的无向图称为完全图（Completed graph）。对于有向图，e的取值范围是0到n（n一1）。具有n（n-1）条弧的有向图称为有向完全图。有很少条边或弧（如e<nlogn）的图称为稀疏图（Sparse graph），反之称为稠密图（Dense graph）。
    有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网（Network）。
无向图G=(V,{E})中从顶点v到顶点v'的路径(Path)是一个顶点序列……如果G是有向图，则路径也是有向的……路径的长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
所谓连通分量（Connected Component），指的是无向图中的极大连通子图。
若有向图中任一对顶点之间都存在路径，则称该图为强连通。有向图中的极大强连通子图，称作有向图的强连通分量。
一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。
    如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
    邻接表（Adjacency List）是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v_i的边（对有向图是以顶点v_i为尾的弧）。每个结点由3个域组成，其中邻接点域指示与顶点邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点，数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设有链域（firstarc）指向链表中第一个结点之外，还设有存储顶点v_i的名或其他有关信息的数据域（data）。
有时，为了便于确定顶点的入度或以顶点v_i为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点v_i建立一个链接以v_i为头的弧的表……
在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O（n十e），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n·e）
十字链表是有向图的一种链式存储结构:
在弧结点中有5个域：其中尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，而链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的孤也在同链表上。它们的头结点即为顶点结点，它由3个域组成：其中data域存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。
    邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是，在邻接表中每一条边……有两个结点，分别在第i个和第j个链表中，这给某些图的操作带来不便。例如在某些图的应用问题中需要对边进行某种操作，如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。
表示每一条边的结点有六个字段: mark, ivex, ilink, jvex, jlink, info:
其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。
而每一顶点的节点有两字段:data, firstedge:
其中，data域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边。
在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中，可见，对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。
这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree）（简称为最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。
    分析算法7.9，假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。其中有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1：其二是重新选择具有最小代价的边，其频度为n。由此，普里姆算法的时间复杂度为O（n^2）与网中的边数无关，因此适用于求边稠密的网的最小生成树。
    而克鲁斯卡尔算法恰恰相反，它的时间复杂度为O（eloge）（e为网中边的数目），因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
克鲁斯卡算法之方法:
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推……
    假若在删去顶点v以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图的一个关节点（articulation point），一个没有关节点的连通图称为是重连通图（biconnected graph）。在重连通图上，任意一对顶点之间至少存在两条路径，则在删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性。若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。关节点和重连通在实际中有较多应用。显然，一个表示通信网络的图的连通度越高，其系统越可靠，无论是哪一站点出现故障或遭到外界破坏，都不影响系统的正常工作；又如，一个航空网若是重连通的，则当某条航线因天气等某种原因关闭时，旅客仍可从别的航线绕道而行；再如，若将大规模集成电路的关键线路设计成重连通的话，则在某些元件失效的情况下，整个片子的功能不受影响，反之，在战争中，若要摧毁敌方的运输线，仅需破坏其运输网中的关节点即可。
    什么是拓扑排序（Topological Sort）？简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
    当有向图中无环时，也可利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先搜索遍历时，最先退出DFS函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。
然而有环的图存在拓扑排序吗？