下载掌阅APP，畅读海量书库
立即打开
在线性结构（例如队列和栈）中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的一个前驱和后继。在树形结构（如树和二叉树）中，除根结点没有前驱外，一个结点只有一个前驱，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数都是任意的。
图G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。
图分为有向图和无向图两种。如图1-10（a）所示是一个有向图，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。＜V i ,V j ＞表示一条有向边，V i 是边的始点（起点），V j 是边的终点，＜V i ,V j ＞和＜V j ,V i ＞是两条不同的有向边。例如，在图1-10（a）中，＜V 1 ,V 4 ＞和＜V 4 ,V 1 ＞是两条不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。
如图1-10（b）所示是一个无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图G中，如果i≠j，i、j∈V，(i,j)∈E，即i和j是G的两个不同的顶点，（i,j）是G中一条边，顶点i和顶点j是相邻的顶点，边（i,j）是与顶点i和j相关联的边。
如果限定任何一条边或弧的两个顶点都不相同，则有n个顶点的无向图最多有n(n–1)/2条边，这样的无向图称为无向完全图。一个有向图最多有n(n–1)条弧，这样的有向图称为有向完全图。
如果同为无向图或同为有向图的两个图G
1
=（V
1
,E
1
）和G
2
=(V
2
,E
2
)，满足
且
，则称图G
2
是图G
1
的子图。
在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。
在图G=（V,E）中，如果存在顶点序列（V 0 ,V 1 ,…,V k ），其中V 0 =P，V k =Q，且（V 0 ,V 1 ），（V 1 ,V 2 ），...，（V k -1 ,V k ）都在E中，则称顶点P到顶点Q有一条路径，并用（V 0 ,V 1 ,…,V k ）表示这条路径，路径的长度是路径的边数，这条路径的长度为k。若G是有向图，则路径也是有向的。
在有向图G中，若对于V(G)中任意两个不同的顶点V i 和V j ，都存在从V i 到V j 及从V j 到V i 的路径，则称G是强连通图。
有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即其自身。非强连通的有向图有多个强连通分量。
最常用的图的存储结构有邻接矩阵和邻接表。
邻接矩阵反映顶点间的邻接关系，设G=（V,E）是具有n(n≥1)个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i,j）或＜i,j＞∈E，则M[i][j]=1；否则，M[i][j]=0。例如，图1-10（a）和图1-10（b）的邻接矩阵分别如下。
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第i行元素的和即为顶点i的度。对于有向图，其邻接矩阵第i行元素之和为顶点i的出度，而邻接矩阵第j列元素之和为顶点j的入度。
若将图的每条边都赋上一个权，则称这种带权图为网（络）。如果图G=（V,E）是一个网，若（i,j）或＜i,j＞属于E，则邻接矩阵中的元素M[i][j]为（i,j）或＜i,j＞上的权。若（i,j）或＜i,j＞不属于E，则M[i][j]为无穷大，或为大于图中任何权值的实数。
在图的邻接表表示中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。例如，如图1-10（a）和图1-10（b）所示的邻接表分别如图1-11（a）和图1-11（b）所示。
图1-11 图的邻接表表示
在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。
和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
在G中任选择一顶点V为初始出发点（源点），则深度优先遍历可以定义如下：首先，访问出发点V，并将其标记为已访问过；然后，依次从V出发搜索V的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。
广度优先遍历的过程是：首先访问出发顶点V；然后访问与顶点V邻接的全部未被访问过的顶点W 0 ，W 1 ，…，W k -1 ；接着再依次访问与顶点W 0 ，W 1 ，…，W k -1 邻接的全部未被访问过的顶点。依此类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。
从广度优先搜索遍历过程知，若顶点V在顶点W之前被访问，则对V相邻顶点的访问就先于只与W相邻的那些顶点的访问。因此，需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问这些顶点相邻接的其他还未被访问过的顶点。
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。
含有n个顶点的连通图的生成树有n个顶点和n–1条边。对一个带权的图（网），在一棵生成树中，各条边的权植之和称为这棵生成树的代价。其中代价最小的生成树称为最小代价生成树（简称最小生成树）。
MST 性质 ：设G=(V,E)是一个连通网络，U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U（即v∈V–U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u,v)。
求连通的带权无向图的最小代价生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
设已知G=(V，E)是一个带权连通无向图，顶点V={0,1,2,…,n–1}。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时，U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合，初始时T为空。如果边(i,j)具有最小代价，且i∈U，j∈V–U，那么最小代价生成树应包含边（i,j）。把j加到U中，把（i,j）加到T中。重复上述过程，直到U等于V为止。这时，T即为要求的最小代价生成树的边的集合。
普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为O(n 2 )，与图中的边数无关，所以适合于稠密图。
设T的初始状态只有n个顶点，而无边的森林T=(V, φ )，按边长递增的顺序选择E中的n–1安全边(u,v)并加入T，生成最小生成树。所谓安全边，是指两个端点分别是森林T里两棵树中顶点的边。加入安全边，可以将森林中的两棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。
克鲁斯卡尔算法的特点，是当前形成的集 合 T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O(elog 2 e)，与图中的顶点数无关，所以较适合于稀疏图。
带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边权值的总和。路径长度的具体含义取决于边上权值所代表的意义。
已知有向带权图（简称有向网）G=(V,E)，找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。
目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看成是已生成的源点到其自身的长度为0的路径）。
迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集（看成红点集），V-S是最短距离尚未确定的顶点集（看成蓝点集）。
（1）初始化：初始化时，只有源点s的最短距离是已知的（SD(s)=0），故红点集S={s}，蓝点集为空。
（2）重复以下工作，按路径长度递增的次序产生各顶点的最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有的蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
需要注意的是：
（1）若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
（2）从源点s到终点v的最短路径简称为v的最短路径；从s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
根据按长度递增的次序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1，红点2，……，红点n，蓝点k
距离为：
源点到红点n最短距离 + ＜红点n，蓝点k＞的边长。
为求解方便，可设置一个向量D[0…n–1]，对于每个蓝点v∈V–S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V–S}，则D[k]=SD(k)。
初始时，每个蓝点v的D[c]值应为权w＜s,v＞，且从s到v的路径上没有中间点，因为该路径仅含一条边＜s,v＞。
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径P=＜s,…,k,j＞。且D[j]减小的新路径P只可能是由于路径＜s,…,k＞和边＜k,j＞组成。所以，当length(P)=D[k]+w＜k,j＞小于D[j]时，应该用P的长度来修改D[j]的值。
对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。
但更常用的是弗洛伊德（Folyd）提出的求每一对顶点之间的最短路径的算法。设G=（V,E）是有n个顶点的有向图，顶点集合V={0,1,…,n–1}。图用邻接矩阵M表示。Floyd算法的基本思想是递推地产生一个矩阵序列C 0 ,C 1 ,C 2 ,…,C n ，其中C 0 是已知的带权邻接矩阵a，C k (i，j)(0≤i，j＜n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n，有C k (i,j)= C 0 (i,j) = a[i][j]。递推地产生C 1 ,C 2 ,…,C n 的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。
设在第k次递推之前已求得C k -1 (i，j)(0≤i，j＜n)，为求C k (i，j)需考虑以下两种情况。
（1）如果从顶点i到顶点j的最短路径不经过顶点k，则由C k (i，j)定义知，从i到j中间的顶点序号不大于k的最短路径长度还是C k -1(i，j)即C k (i，j)=C k -1 (i，j)。
（2）如果从顶点i到顶点j的最短路径要经过顶点k，则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于C k -1 (i,k)和C k -1 (k,j)分别表示i到k和从k到j的中间顶点序号不大于k-1的最短路径长度，若C k -1 (i,k)+C k -1 (k,j)＜C k -1 (i,j)，C k -1 (i,k)+C k -1 (k,j)必定是i到j的中间顶点序号不大于是k的最短路径的长度，则C k (i,j)=C k -1 (i,k)+C k -1 (k,j)。