图图（ Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图结构中，对结点
（图中常称为顶点）的前趋和后继个数都是不加限制的，
即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、
电讯工程、计算机科学以及数学的其它分支中。
基本定义和术语
若图 G中的每条边都是有方向的，则称 G为 有向图
（ Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，＜ vi，
vj＞表示一条有向边,vi是边的始点（起点）,vj是边的终点。因此，＜ vi,vj＞和＜ vj,vi＞是两条不同的有向边。有向边也称为弧（ Arc），边的始点称为弧尾
（ Tail），终点称为弧头（ Head）。
图 G由两个集合 V和 E组成，记为 G＝ (V,E)，其中 v是顶点的有穷非空集合,E是 V中顶点偶对（称为边）的有穷集。通常，也将图 G的顶点集和边集分别记为 V(G)
和 E(G)。 E(G)可以是空集，若 E(G)为空，则图 G只有顶点而没有边，称为空图。
若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为 邻接点
(Adjacent)，或称 vi和 vj相邻接；称 (vi,vj)关联 (Incident)
于顶点 vi和 vj，或称 (vi,vj)与顶点 vi和 vj相关联 。如图 7-
1中 G2，与顶点 vl相邻接的顶点是 v2,v3和 v4，而关联于顶点 v2的边是 (vl,v2),(v2,v3)和 (v2,v4)。若＜ vi,vj
＞是一条有向边，则称顶点 vi邻接到 vj,顶点 vj邻接于顶点 vi,并称边＜ vi,vj＞关联于 vi和 vj或称＜ vi,vj＞与顶点 vi和 vj相关联。如图 7-1中 Gl，关联于顶点 v2的边是＜
v1,v2＞，＜ v2,vl＞和＜ v2,v3＞。
无向图中顶点 v的 度 (Degree)是关联于该顶点的边的数目，记为 D(v)。若 G为有向图，则把以顶点 v为终点的边的数目，称为 v的 人度 (1ndegree)，记为 ID(v)；把以顶点 v为始点的边的数目，称为 v的 出度 (outdegree)，记为 OD(v)；顶点 v的度则定义为该顶点的入度和出度之和，即 D(v)＝ ID(v)十 OD(v)。
在无向图 G中，若存在一个顶点序列 vp,vi1,vi2…,vin,vq，
使得 (vp,vil),(vi1,vi2),…,(vin,vq)均属于 E(G)，则称顶点 vp到 vq存在一条 路径 (Path)。若 G是有向图，则路径也是有向的，它由 E(G)中的有向边＜ vp,vil＞，＜
vil,vi2＞,…,＜ vin,vq＞组成。 路径长度 定义为该路径上边的数目。若一条路径上除了 vp和 vq可以相同外；
其余顶点均不相同，则称此路径为一条 简单路径 。起点和终点相同 (vp＝ vq)的简单路径称为 简单回路 或 简单环 (Cycle)。例如，在图 G2中顶点序列 vl,v2,v3,v4是一条从顶点 vl到顶点 v4的长度为 3的简单路径；顶点序列
vl,v2,v4,vl,v3是一条从顶点 vl到顶点 v3的长度为 4的路径，但不是简单路径；顶点序列 vl,v2,v4,vl是一个长度为 3的简单环。在有向图 Gl中，顶点序列 vl,v2，
vl是一个长度为 2的有向简单环。
在一个有向图中，若存在一个顶点 v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为 有根图,v称作图的 根 。
在无向图 G中，若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 )，则称 vi和 vj是 连通 的。若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 )，则称 G为 连通图 (Connected Graph)。例如，图 G2
和 G3是连通图。
无向图 G的极大连通子图称为 G的 连通分量 (connected Component)。
显然，任何连通图的连通分量只有一个，即是其自身，而非连通的无向图有多个连通分量。例如，图 7-4中的 G4是非连通图，它有两个连通分量 Hl和 H2。
在有向图 G中，若对于 V(G)中任意两个不同的顶点 vi和 vj，都存在从 vi到 vj以及从 vj到 vi的路径，则称 G是 强连通图 。有向图 G的极大强连通子图称为 G的 强连通分量 。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。例如图 7-1中的 Gl不是强连通图，因为 v3到 v2没有路径，但它有两个强连通分量，
若将图的每条边都赋上一个权，则称这种带权图为 网络 (Network)。通常权是具有某种意义的数,
它们可以表示两个顶点之间的距离，耗费等图的存储结构
邻接矩阵 (Adjacency
Matrix)是表示顶点之间相邻关系的矩阵 。
设 G＝ (V,E)是具有 n
个顶点的图,则 G的邻接矩阵是具有如下性质的 n阶方阵：
）中的边（不是）或：若（ ）中的边（是）或：若（ GEvvvv GEvvvv jiji jiji,,0,,1ji,A
用邻接矩阵表示法表示图,除了存储用于表示顶点间相邻关系的邻接矩阵外,通常还需要用一个顺序表来存储顶点信息 。 其形式说明如下：
# define n 6 / * 图的顶点数 * /
# define e 8 / * 图的边 （ 弧 ） 数 */
typedef char vextype； / * 顶点的数据类型 * /
typedef float adjtype； / * 权值类型 * /
typedef struct
{vextype vexs[n]；
adjtype arcs[n][n]；
}graph；
若图中顶点信息是 0至 n-1的编号,则仅需令权值为 1,存储一个邻接矩阵就可以表示图 。 若是网络,则 adjtype为权的类型 。 由于无向图或无向网络的邻接矩阵是对称的,故可采用压缩存储的方法,仅存储下三角阵 (不包括对角线上的元素 )中的元素即可 。 显然,邻接矩阵表示法的空间复杂度 S(n)＝ O(n2)。
CREATGRAPH(ga) ／ * 建立无向网络 * ／
Graph * ga；
{
int i,j,k；
float w；
for(i＝ 0； i＜ n； i++)
ga ->vexs[i]＝ getchar()；／ * 读入顶点信息,建立顶点表 *／
for(i＝ 0； i＜ n； i++)
for(j＝ 0； j＜ n； j++)
ga ->arcs[i][j]＝ 0； ／ * 邻接矩阵初始化 *／
for(k＝ 0； k＜ e； k++) ／ * 读入 e条边 *／
(scanf(”％ d％ d％ f”,&I,&j,&w)；／ *读入边 (vi,vj)上的权 w *／
ga ->arcs[i][j]＝ w；
ga - >arcs[j][i]＝ w；
}
}／ *CREATGRAPH *／
该算法的执行时间是 O(n+n2+e),其中 O(n2)的时问耗费在邻接矩阵的初始化操作上 。
因为 e＜ n2,所以,算法的时间复杂度是 O(n2)。
邻接表这种表示法类似于树的孩子链表表示法 。
对于图 G中的每个顶点 vi，该方法把所有邻接于 vi的顶点 vj链成一个单链表，这个单链表就称为顶点 vi的邻接表 (Adjacency List)。邻接表中每个表结点均有两个域，
其一是邻接点域 (Adjvex)，用以存放与 vi相邻接的顶点
vj的序号；其二是链域 (Next)，用来将邻接表的所有表结点链在一起。并且为每个顶点 vi的邻接表设置一个具有两个域的表头结点：一个是顶点域 (vertex)，用来存放顶点 vi的信息；另一个是指针域 (Link)，用于存入指向 vi的邻接表中第一个表结点的头指针。为了便于随机访问任一顶点的邻接表，将所有邻接表的表头结点顺序存储在一个向量中，这样，图 G就可以由这个表头向量来表示。
建立有向图的邻接表与此类似，只是更加简单，
每读入一个顶点对序号＜ i,j＞时，仅需生成十个邻接点序号为 j的边表结点，将其插入到 vi
的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。
值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。
邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。
在邻接表 (或逆邻接表 )表示中，每个边表对应于邻接矩阵的一行 (或一列 )，边表中结点个数等于一行 (或一列 )中非零元素的个数。对于一个具有 n个顶点 e条边的图 G，若 G是无向图，则它的邻接表表示中有 n个顶点表结点和 2e个边表结点；若 G是有向图，则它的邻接表表示或逆邻接表表示中均有 n个顶点表结点和 e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为 S(n,e)＝ O(n+e)。若图中边的数目远远小于 n2(即 e＜＜ n2)，此类图称作稀疏图 (Sparse
Graph)，这时用邻接表表示比用邻接矩阵表示节省存储空间；若 e接近于 n2 (准确地说，无向图 e接近于 n(n-1)／ 2，有向图 e接近于 n(n-1))，
此类图称作稠密图 (Dense Graph)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。
在无向图中求顶点的度,邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第 i行 (或第 i列 )上非零元素的个数即为顶点 vi的度；在邻接表表示中,顶点 vi的度则是第 i个边表中的结点个数 。
在有向图中求顶点的度 。 采用邻接矩阵表示比邻接表表示更方便：
邻接矩阵中的第 i行上非零元素的个数是顶点 vi的出度 OD(vi),第 i
列上非零元素的个数是顶点 vi的入度 ID(vi),顶点 vi的度即是二者之和；在邻接表表示中,第 i个边表 (即出边表 )上的结点个数是顶点 vi的出度,求 vi的入度较困难,需遍历各顶点的边表 。 若有向图采用逆邻接表表示,则与邻接表表示相反,求顶点的入度容易,
而求顶点出度较难 。
在邻接矩阵表示中,很容易判定 (vi,vj)或＜ vi,vj＞是否是图的一条边,只要判定矩阵中的第 i行第 j列上的那个元素是否为零即可；
但是在邻接表表示中,需扫描第 i个边表,最坏情况下要耗费 O(n)
时间 。
在邻接矩阵中求边的数目 e，必须检测整个矩阵，所耗费的时间是
0(n2)，与 e的大小无关；而在邻接表表示中，只要对每个边表的结点个数计数即可求得 e，所耗费的时间是 0(e+n)。因此，当 e＜＜ n2
时，采用邻接表表示更节省时间。
图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，
沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有顶点。然而，
图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量 visited[n]，它的初值为 false，一旦访问了顶点 vi，便将 visited[i-1]置为 TRUE。
深度优先搜索 (Depth-First-Search)遍历类似于树的前序遍历。假设给定图 G的初态是所有顶点均未访问过，在 G中任选一顶点 vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点 vi，并将其标记为已访问过，然后，依次从 vi出发搜索 vi的每一个邻接点
vj,若 vj未曾访问过，则以 vj为新的出发点继续进行深度优先搜索。
显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。例如，设 x是刚访问过的顶点，
按深度优先搜索方法，下一步将选择一条从 x出发的未检测过的边
(x,y)。若发现顶点 y已被访问过，则重新选择另一条从 x出发的未检测过的边。若发现顶点 y未曾访问过，则沿此边从 x到达 y，访问 y并将其标记为已访问过，然后从 y开始搜索，直到搜索完从 y出发的所有路径，才回溯到顶点 x，然后再选择一条从 x出发的未检测过的边。上述过程直至从 x出发的所有边都已检测过为止。此时，
若 x不是初始出发点，则回溯到在 x之前被访问过的顶点；若 x是初始出发点，则整个搜索过程结束。显然这时图 G中所有和初始出发点有路径相通的顶点都已被访问过。因此，若 G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图 G的遍历。
在该存储结构上执行 DFS算法的过程如下：设初始出发点是 v1，则
DFS（ 0）的执行结果是访问 v1，将其置上已访问标记，从 v1搜索到的第 1个邻接点是 v2，因 v2未曾访问过，故调用 DFS(1)。执行
DFS(1)，首先访问 v2，将其标记为已访问过，然后从 v2搜索到的第 1个邻接点是 vl，但 vl已访问过，故继续搜索到第 2个邻接点 v4，
v4未曾访过，因此调用 DFS(3)。类似地分析，访问 v4后调用
DFS(7)，访问 v：后调用 DPS(4)。执行 DFS(4)时，在访问 v5并作标记后，从 v5搜索到的两个邻接点依次是 v2和 v8，因为它们均已被访问过，所以 DFS(4)执行结束返回，回溯到 v8。又因为 v8的两个邻接点已搜索过，故 DFS(7)亦结束返回，回溯到 v4。类似地由 v4回溯到 v2。 V2的邻接点 vl和 v4已搜索过，但 v2的第 3个邻接点 v5还尚未搜索，故接下来由 v2搜索到 v5，但因为 v5已访问过，所以 DFS(1)
也结束返回，回溯到 vl。 vl的第 1个邻接点已搜索过，故继续从 v1
搜索到第 2个邻接点 v3，因为 v3未曾访问过，故调用 DFS(2)。类似地依次访问 v3,v6,v7后，又由 v7依次回溯到 v6,v3,vl。此时,vl
的所有邻接点都已搜索过，故 DFS(0)执行完毕。
宽度优先搜索法宽度优先搜索 (Breadth-First-Search)遍历类似于树的按层次遍历 。 设图 G的初态是所有顶点均未访问过,在 G中任选一顶点 2为初始出发点,则宽度优先搜索的基本思想是：首先访问出发点 Vi,接着依次访问 vi的所有邻接点 wl,w2,…,wt,然后,再依次访问与 wl，
w2,…,wt邻接的所有未曾访问过的顶点,依此类推,直至图中所有和初始出发点 v有路径相通的顶点都已访问到为止 。 此时,从
vi开始的搜索过程结束,若 G是连通图则遍历完成 。
显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为宽度优先搜索。设 x和 y是两个相继被访问过的顶点，若当前是以 x
为出发点进行搜索，则在访问 x的所有未曾访问过的邻接点之后，
紧接着是以 y为出发点进行横向搜索，并对搜索到的 y的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点亦先被访问。为此，需引进队列保存已访问过的顶点。
最小生成树图的生成树不是唯一的,从不同的顶点出发进行遍历,
可以得到不同的生成树 。 对于连通网络 G＝ (V,E),边是带权的,因而 G的生成树的各边也是带权的 。 我们把生成树各边的权值总和称为生成树的权,并把权最小的生成树称为 G的 最小生成树 (Minimun Spanning Tree)。
生成树和最小生成树有许多重要的应用。令图 G的顶点表示城市，边表示连接两个城市之间的通讯线路。 n个城市之间最多可设立的线路有 n(n-1)／ 2条，把 n个城市连接起来至少要有 n-1条线路，则图 G的生成树表示了建立通讯网络的可行方案。如果给图中的边都赋予权，
而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择 n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就是要构造该图的一棵最小生成树。
以下我们只讨论无向图的最小生成树问题。构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设 G＝ (V,E)是一个连通网络,U是顶点集 V的一个真子集。若 (u,v)是 G中所有的一个端点在 U(即 u∈ U)里、另一个端点不在 U(即
v∈ V-U)里的边中，具有最小权值的一条边，则一定存在 G的一棵最小生成树包含此边 (u,v)。这个性质称为
MST性质。 MST性质可用反证法证明：假设 G的任何一棵最小生成树中都不含边 (u,v)。设 T是 G的一棵最小生成树，但不包含边 (u,v)。由于 T是树，且是连通的，因此有一条从 u到 v的路径；且该路径上必有一条连接两个顶点集 U和 V-U的边 (u′,v′)，其中 u′∈ U，
v′∈ V-U，否则 u和 v不连通。当把边 (u,v)加入树 T时，
得到一个含有边 (u,v)的回路，见图 7-15。删去边 (u′，
v′)，上述回路即被消除，由此得到另一棵生成树 T′,T′
和 T的区别仅在于用边 (u,v)取代了 T中的边 (u′,v′)。
因为 (u,v)的权＜ (u′,v′)的权，故 T′的权＜ T的权，因此 T′也是 G的最小生成树，它包含边 (u,v)，与假设矛盾 !
假设 G＝ (V,E)是连通网络,为简单起见,我们用序号 1至 n来表示顶点集合,即 v＝ {1,2,…,n}。 设所求的最小生成树为 T＝ (U，
TE),其中 U是 T的顶点集,TE是 T的边集 。 并且将 G中边上的权看做是长度 。
Prim算法的基本思想是：首先从 v中任取一个顶点 u0,将生成树 T
置为仅有一个结点 u0的树,即置 U＝ {u0}；然后只要 U是 V的真子集,就在所有那些其一个端点 u己在 T(即 u∈ U),另一个端点 v还未在 T(即 v∈ V— U)的边中,找一条最短 (即权最小 )的边 (u,v),并把该条边 (u,v)和其不在 T中的顶点 v,分别并入 T的边集 TE和顶点集 U。 如此进行下去,每次往生成树里并入一个顶点和一条边,
直到把所有顶点都包括进生成树 T为止 。 此时,必有 U＝ V,TE中有 n-1条边 。 MST性质保证上述过程求得的 T＝ (U,TE)是 G的一棵最小生成树 。
显然,Prim算法的关键是如何找到连接 U和 V-U的最短边来扩充生成树 T。为直观解释方便，设想在构造过程中,T的顶点集 U中顶点和边集 TE中的边均被涂成红色,U之外的顶点集 V-U中的顶点均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么．最短紫边就是连接 U和 V-U的最短边。
最短路径交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?
交通网络可用带权图来表示 。 顶点表示城市名称,边表示两个城市有路连通,边上权值可表示两城市之间的距离,交通费或途中所花费的时间等 。 求两个顶点之间的最短路径,不是指路径上边数之和最少,而是指路径上各边的权值之和最小 。
另外，若两个顶点之间没有边，则认为两个顶点无通路，
但有可能有间接通路（从其他顶点达到 )）。路径上的开始顶点 (出发点 )称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。
所有顶点对之间的最短路径所有顶点对之间的最短路径是指：对于给定的有向网 G=(V,E)，要对 G中任意一对顶点有序对 V,W(V≠W)，找出 V到 W的最短距离和 W到 V的最短距离。解决此问题的一个有效方法是,轮流以每一个顶点为源点，重复执行迪杰斯特拉算法 n次，
即可求得每一对顶点之间的最短路径,总的时间复杂度为 O(n3)。
弗洛伊德算法 仍然使用 前面定义的 图的邻接 矩阵
cost[n+1][n+1]来存储带权有向图 。 算法的基本思想是,
设置一个 nxn的矩阵 A(k),其中除对角线的元素都等于 0
外,其他元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度,K
表示运算步骤 。 开始时,以任意两个顶点之间的有向边的权值作为路径长度,没有有向边时,路径长度为 ∞，
当 K=0时,A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其他顶点作为中间顶点，
如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。
具体做法为：第一步，让所有边上加入中间顶点 1，取
A[i][j]与 A[i][1]+A[1][j]中较小的值作 A[i][j]的值，完成后得到 A(1)，第二步，让所有边上加入中间顶点 2，取
A[i][j]与 A[i][2]+A[2][j]中较小的值，完成后得到 A(2)…,
如此进行下去，当第 n步完成后，得到 A(n),A(n)即为我们所求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离。
拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，
整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图 7-24给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须学完高等数学。在图 7-24（ b）中，我们用一种有向图来表示课程开设，在这种有向图中，
顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络 (Active On Vertices)简称为
AOV网。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，即
i活动必须完成后,j活动才可以开始，并称 i为 j的直接前驱,j为 i的直接后继。这种前驱与后继的关系有传递性，此外，任何活动 i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看,AOV网中不能出现有向回路（或称有向环）。在 AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程而言，将出现死循环。因此，对给定的 AOV网，应先判断它是否存在有向环。判断
AOV网是否有有向环的方法是对该 AOV网进行拓扑排序，将 AOV网中顶点排列成一个线性有序序列，若该线性序列中包含 AOV网全部顶点，则 AOV网无环，否则,AOV网中存在有向环，该 AOV网所代表的工程是不可行的。
本章小结图是一种复杂的非线性结构,具有广泛的应用背景 。 本章涉及到的基本概念有：
图,由两个集合 V和 E组成,记为 G＝ (V,E),其中 v是顶点的有穷非空集合,E是 V中顶点偶对 （ 称为边 ） 的有穷集 。 通常,也将图 G的顶点集和边集分别记为 V(G)和
E(G)。 E(G)可以是空集,若 E(G)为空,则图 G只有顶点而没有边,称为空图 。
有向图 （ Digraph）,若图 G中的每条边都是有方向的,则称 G为有向图 。
无向图 （ Undigraph）,若图 G中的每条边都是没有方向的,则称 G为无向图 。
无向完全图 (Undirected Complete Graph),恰好有 n(n-1)／ 2条边的无向图称为无向完全图 。
有向完全图 (DirectedComplete Graph)：恰有 n(n-1)条边的有向图称为有向完全图 。
邻接点 (Adjacent)：若 (vi,vj)是一条无向边,则称顶点 vi和 vj互为邻接点 。
度 (Degree)：无向图中顶点 v的度是关联于该顶点的边的数目 。
人度 (1ndegree)若 G为有向图,则把以顶点 v为终点的边的数目,称为 v的人度,记为
ID(v)。
出度 (outdegree)：把以顶点 v为始点的边的数目,称为 v的出度,记为 OD(v)。
子图 (Subgraph)：设 G＝ (V,E)是一个图，若 v′ 是 v的子集,E′ 是 E的子集，且 E′
中的边所关联的顶点均在 v′ 中，则 G′ ＝ (V′,E′ )也是一个图，并称其为 G的子图。
路径 (Path)：在无向图 G中,若存在一个顶点序列 vp,vi1,vi2…,vin,vq,使得 (vp,vil)，
(vi1,vi2),…,(vin,vq)均属于 E(G),则称顶点 vp到 vq存在一条路径 。
路径长度,该路径上边的数目 。
简单路径,若一条路径上除了 vp和 vq可以相同外,其余顶点均不相同,则称此路径为一条简单路径 。
简单回路或简单环 (Cycle)：起点和终点相同 (vp＝ vq)的简单路径称为简单回路或简单环 。
有根图,在一个有向图中,若存在一个顶点 v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图,v称作图的根 。
连通,在无向图 G中,若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 ),则称 vi和 vj是连通的 。
连通图 (Connected Graph)：若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 ),则称 G为连通图 。
连通分量 (connectedComponent)：无向图 G的极大连通子图称为 G的连通分量 。
强连通图,在有向图 G中,若对于 V(G)中任意两个不同的顶点 vi和 vj,都存在从 vi到 vj以及从 vj到 vi
的路径,则称 G是强连通图 。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量 。
网络 (Network)：若将图的每条边都赋上一个权,则称这种带权图为网络 。
生成树 (Spanning Tree)：连通图 G的一个子图如果是一棵包含 G的所有顶点的树,则该子图称为 G
的生成树 。
最小生成树 (MinimunSpanning Tree)：权最小的生成树称为 G的最小生成树 。
本章在介绍图的基本概念的基础上,还介绍了图的两种常用的存储结构,对图的遍历,最小生成树等问题做了较详细的讨论,给出了相应的求解算法,有的算法采用自顶向下,逐步求精的方法加以介绍,也许能便于读者理解它们 。
相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，
学会引用本章的有关内容。
（图中常称为顶点）的前趋和后继个数都是不加限制的，
即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、
电讯工程、计算机科学以及数学的其它分支中。
基本定义和术语
若图 G中的每条边都是有方向的，则称 G为 有向图
（ Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，＜ vi，
vj＞表示一条有向边,vi是边的始点（起点）,vj是边的终点。因此，＜ vi,vj＞和＜ vj,vi＞是两条不同的有向边。有向边也称为弧（ Arc），边的始点称为弧尾
（ Tail），终点称为弧头（ Head）。
图 G由两个集合 V和 E组成，记为 G＝ (V,E)，其中 v是顶点的有穷非空集合,E是 V中顶点偶对（称为边）的有穷集。通常，也将图 G的顶点集和边集分别记为 V(G)
和 E(G)。 E(G)可以是空集，若 E(G)为空，则图 G只有顶点而没有边，称为空图。
若 (vi,vj)是一条无向边，则称顶点 vi和 vj互为 邻接点
(Adjacent)，或称 vi和 vj相邻接；称 (vi,vj)关联 (Incident)
于顶点 vi和 vj，或称 (vi,vj)与顶点 vi和 vj相关联 。如图 7-
1中 G2，与顶点 vl相邻接的顶点是 v2,v3和 v4，而关联于顶点 v2的边是 (vl,v2),(v2,v3)和 (v2,v4)。若＜ vi,vj
＞是一条有向边，则称顶点 vi邻接到 vj,顶点 vj邻接于顶点 vi,并称边＜ vi,vj＞关联于 vi和 vj或称＜ vi,vj＞与顶点 vi和 vj相关联。如图 7-1中 Gl，关联于顶点 v2的边是＜
v1,v2＞，＜ v2,vl＞和＜ v2,v3＞。
无向图中顶点 v的 度 (Degree)是关联于该顶点的边的数目，记为 D(v)。若 G为有向图，则把以顶点 v为终点的边的数目，称为 v的 人度 (1ndegree)，记为 ID(v)；把以顶点 v为始点的边的数目，称为 v的 出度 (outdegree)，记为 OD(v)；顶点 v的度则定义为该顶点的入度和出度之和，即 D(v)＝ ID(v)十 OD(v)。
在无向图 G中，若存在一个顶点序列 vp,vi1,vi2…,vin,vq，
使得 (vp,vil),(vi1,vi2),…,(vin,vq)均属于 E(G)，则称顶点 vp到 vq存在一条 路径 (Path)。若 G是有向图，则路径也是有向的，它由 E(G)中的有向边＜ vp,vil＞，＜
vil,vi2＞,…,＜ vin,vq＞组成。 路径长度 定义为该路径上边的数目。若一条路径上除了 vp和 vq可以相同外；
其余顶点均不相同，则称此路径为一条 简单路径 。起点和终点相同 (vp＝ vq)的简单路径称为 简单回路 或 简单环 (Cycle)。例如，在图 G2中顶点序列 vl,v2,v3,v4是一条从顶点 vl到顶点 v4的长度为 3的简单路径；顶点序列
vl,v2,v4,vl,v3是一条从顶点 vl到顶点 v3的长度为 4的路径，但不是简单路径；顶点序列 vl,v2,v4,vl是一个长度为 3的简单环。在有向图 Gl中，顶点序列 vl,v2，
vl是一个长度为 2的有向简单环。
在一个有向图中，若存在一个顶点 v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为 有根图,v称作图的 根 。
在无向图 G中，若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 )，则称 vi和 vj是 连通 的。若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 )，则称 G为 连通图 (Connected Graph)。例如，图 G2
和 G3是连通图。
无向图 G的极大连通子图称为 G的 连通分量 (connected Component)。
显然，任何连通图的连通分量只有一个，即是其自身，而非连通的无向图有多个连通分量。例如，图 7-4中的 G4是非连通图，它有两个连通分量 Hl和 H2。
在有向图 G中，若对于 V(G)中任意两个不同的顶点 vi和 vj，都存在从 vi到 vj以及从 vj到 vi的路径，则称 G是 强连通图 。有向图 G的极大强连通子图称为 G的 强连通分量 。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。例如图 7-1中的 Gl不是强连通图，因为 v3到 v2没有路径，但它有两个强连通分量，
若将图的每条边都赋上一个权，则称这种带权图为 网络 (Network)。通常权是具有某种意义的数,
它们可以表示两个顶点之间的距离，耗费等图的存储结构
邻接矩阵 (Adjacency
Matrix)是表示顶点之间相邻关系的矩阵 。
设 G＝ (V,E)是具有 n
个顶点的图,则 G的邻接矩阵是具有如下性质的 n阶方阵：
）中的边（不是）或：若（ ）中的边（是）或：若（ GEvvvv GEvvvv jiji jiji,,0,,1ji,A
用邻接矩阵表示法表示图,除了存储用于表示顶点间相邻关系的邻接矩阵外,通常还需要用一个顺序表来存储顶点信息 。 其形式说明如下：
# define n 6 / * 图的顶点数 * /
# define e 8 / * 图的边 （ 弧 ） 数 */
typedef char vextype； / * 顶点的数据类型 * /
typedef float adjtype； / * 权值类型 * /
typedef struct
{vextype vexs[n]；
adjtype arcs[n][n]；
}graph；
若图中顶点信息是 0至 n-1的编号,则仅需令权值为 1,存储一个邻接矩阵就可以表示图 。 若是网络,则 adjtype为权的类型 。 由于无向图或无向网络的邻接矩阵是对称的,故可采用压缩存储的方法,仅存储下三角阵 (不包括对角线上的元素 )中的元素即可 。 显然,邻接矩阵表示法的空间复杂度 S(n)＝ O(n2)。
CREATGRAPH(ga) ／ * 建立无向网络 * ／
Graph * ga；
{
int i,j,k；
float w；
for(i＝ 0； i＜ n； i++)
ga ->vexs[i]＝ getchar()；／ * 读入顶点信息,建立顶点表 *／
for(i＝ 0； i＜ n； i++)
for(j＝ 0； j＜ n； j++)
ga ->arcs[i][j]＝ 0； ／ * 邻接矩阵初始化 *／
for(k＝ 0； k＜ e； k++) ／ * 读入 e条边 *／
(scanf(”％ d％ d％ f”,&I,&j,&w)；／ *读入边 (vi,vj)上的权 w *／
ga ->arcs[i][j]＝ w；
ga - >arcs[j][i]＝ w；
}
}／ *CREATGRAPH *／
该算法的执行时间是 O(n+n2+e),其中 O(n2)的时问耗费在邻接矩阵的初始化操作上 。
因为 e＜ n2,所以,算法的时间复杂度是 O(n2)。
邻接表这种表示法类似于树的孩子链表表示法 。
对于图 G中的每个顶点 vi，该方法把所有邻接于 vi的顶点 vj链成一个单链表，这个单链表就称为顶点 vi的邻接表 (Adjacency List)。邻接表中每个表结点均有两个域，
其一是邻接点域 (Adjvex)，用以存放与 vi相邻接的顶点
vj的序号；其二是链域 (Next)，用来将邻接表的所有表结点链在一起。并且为每个顶点 vi的邻接表设置一个具有两个域的表头结点：一个是顶点域 (vertex)，用来存放顶点 vi的信息；另一个是指针域 (Link)，用于存入指向 vi的邻接表中第一个表结点的头指针。为了便于随机访问任一顶点的邻接表，将所有邻接表的表头结点顺序存储在一个向量中，这样，图 G就可以由这个表头向量来表示。
建立有向图的邻接表与此类似，只是更加简单，
每读入一个顶点对序号＜ i,j＞时，仅需生成十个邻接点序号为 j的边表结点，将其插入到 vi
的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。
值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。
邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。
在邻接表 (或逆邻接表 )表示中，每个边表对应于邻接矩阵的一行 (或一列 )，边表中结点个数等于一行 (或一列 )中非零元素的个数。对于一个具有 n个顶点 e条边的图 G，若 G是无向图，则它的邻接表表示中有 n个顶点表结点和 2e个边表结点；若 G是有向图，则它的邻接表表示或逆邻接表表示中均有 n个顶点表结点和 e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为 S(n,e)＝ O(n+e)。若图中边的数目远远小于 n2(即 e＜＜ n2)，此类图称作稀疏图 (Sparse
Graph)，这时用邻接表表示比用邻接矩阵表示节省存储空间；若 e接近于 n2 (准确地说，无向图 e接近于 n(n-1)／ 2，有向图 e接近于 n(n-1))，
此类图称作稠密图 (Dense Graph)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。
在无向图中求顶点的度,邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第 i行 (或第 i列 )上非零元素的个数即为顶点 vi的度；在邻接表表示中,顶点 vi的度则是第 i个边表中的结点个数 。
在有向图中求顶点的度 。 采用邻接矩阵表示比邻接表表示更方便：
邻接矩阵中的第 i行上非零元素的个数是顶点 vi的出度 OD(vi),第 i
列上非零元素的个数是顶点 vi的入度 ID(vi),顶点 vi的度即是二者之和；在邻接表表示中,第 i个边表 (即出边表 )上的结点个数是顶点 vi的出度,求 vi的入度较困难,需遍历各顶点的边表 。 若有向图采用逆邻接表表示,则与邻接表表示相反,求顶点的入度容易,
而求顶点出度较难 。
在邻接矩阵表示中,很容易判定 (vi,vj)或＜ vi,vj＞是否是图的一条边,只要判定矩阵中的第 i行第 j列上的那个元素是否为零即可；
但是在邻接表表示中,需扫描第 i个边表,最坏情况下要耗费 O(n)
时间 。
在邻接矩阵中求边的数目 e，必须检测整个矩阵，所耗费的时间是
0(n2)，与 e的大小无关；而在邻接表表示中，只要对每个边表的结点个数计数即可求得 e，所耗费的时间是 0(e+n)。因此，当 e＜＜ n2
时，采用邻接表表示更节省时间。
图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，
沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有顶点。然而，
图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量 visited[n]，它的初值为 false，一旦访问了顶点 vi，便将 visited[i-1]置为 TRUE。
深度优先搜索 (Depth-First-Search)遍历类似于树的前序遍历。假设给定图 G的初态是所有顶点均未访问过，在 G中任选一顶点 vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点 vi，并将其标记为已访问过，然后，依次从 vi出发搜索 vi的每一个邻接点
vj,若 vj未曾访问过，则以 vj为新的出发点继续进行深度优先搜索。
显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。例如，设 x是刚访问过的顶点，
按深度优先搜索方法，下一步将选择一条从 x出发的未检测过的边
(x,y)。若发现顶点 y已被访问过，则重新选择另一条从 x出发的未检测过的边。若发现顶点 y未曾访问过，则沿此边从 x到达 y，访问 y并将其标记为已访问过，然后从 y开始搜索，直到搜索完从 y出发的所有路径，才回溯到顶点 x，然后再选择一条从 x出发的未检测过的边。上述过程直至从 x出发的所有边都已检测过为止。此时，
若 x不是初始出发点，则回溯到在 x之前被访问过的顶点；若 x是初始出发点，则整个搜索过程结束。显然这时图 G中所有和初始出发点有路径相通的顶点都已被访问过。因此，若 G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图 G的遍历。
在该存储结构上执行 DFS算法的过程如下：设初始出发点是 v1，则
DFS（ 0）的执行结果是访问 v1，将其置上已访问标记，从 v1搜索到的第 1个邻接点是 v2，因 v2未曾访问过，故调用 DFS(1)。执行
DFS(1)，首先访问 v2，将其标记为已访问过，然后从 v2搜索到的第 1个邻接点是 vl，但 vl已访问过，故继续搜索到第 2个邻接点 v4，
v4未曾访过，因此调用 DFS(3)。类似地分析，访问 v4后调用
DFS(7)，访问 v：后调用 DPS(4)。执行 DFS(4)时，在访问 v5并作标记后，从 v5搜索到的两个邻接点依次是 v2和 v8，因为它们均已被访问过，所以 DFS(4)执行结束返回，回溯到 v8。又因为 v8的两个邻接点已搜索过，故 DFS(7)亦结束返回，回溯到 v4。类似地由 v4回溯到 v2。 V2的邻接点 vl和 v4已搜索过，但 v2的第 3个邻接点 v5还尚未搜索，故接下来由 v2搜索到 v5，但因为 v5已访问过，所以 DFS(1)
也结束返回，回溯到 vl。 vl的第 1个邻接点已搜索过，故继续从 v1
搜索到第 2个邻接点 v3，因为 v3未曾访问过，故调用 DFS(2)。类似地依次访问 v3,v6,v7后，又由 v7依次回溯到 v6,v3,vl。此时,vl
的所有邻接点都已搜索过，故 DFS(0)执行完毕。
宽度优先搜索法宽度优先搜索 (Breadth-First-Search)遍历类似于树的按层次遍历 。 设图 G的初态是所有顶点均未访问过,在 G中任选一顶点 2为初始出发点,则宽度优先搜索的基本思想是：首先访问出发点 Vi,接着依次访问 vi的所有邻接点 wl,w2,…,wt,然后,再依次访问与 wl，
w2,…,wt邻接的所有未曾访问过的顶点,依此类推,直至图中所有和初始出发点 v有路径相通的顶点都已访问到为止 。 此时,从
vi开始的搜索过程结束,若 G是连通图则遍历完成 。
显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为宽度优先搜索。设 x和 y是两个相继被访问过的顶点，若当前是以 x
为出发点进行搜索，则在访问 x的所有未曾访问过的邻接点之后，
紧接着是以 y为出发点进行横向搜索，并对搜索到的 y的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点亦先被访问。为此，需引进队列保存已访问过的顶点。
最小生成树图的生成树不是唯一的,从不同的顶点出发进行遍历,
可以得到不同的生成树 。 对于连通网络 G＝ (V,E),边是带权的,因而 G的生成树的各边也是带权的 。 我们把生成树各边的权值总和称为生成树的权,并把权最小的生成树称为 G的 最小生成树 (Minimun Spanning Tree)。
生成树和最小生成树有许多重要的应用。令图 G的顶点表示城市，边表示连接两个城市之间的通讯线路。 n个城市之间最多可设立的线路有 n(n-1)／ 2条，把 n个城市连接起来至少要有 n-1条线路，则图 G的生成树表示了建立通讯网络的可行方案。如果给图中的边都赋予权，
而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择 n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就是要构造该图的一棵最小生成树。
以下我们只讨论无向图的最小生成树问题。构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设 G＝ (V,E)是一个连通网络,U是顶点集 V的一个真子集。若 (u,v)是 G中所有的一个端点在 U(即 u∈ U)里、另一个端点不在 U(即
v∈ V-U)里的边中，具有最小权值的一条边，则一定存在 G的一棵最小生成树包含此边 (u,v)。这个性质称为
MST性质。 MST性质可用反证法证明：假设 G的任何一棵最小生成树中都不含边 (u,v)。设 T是 G的一棵最小生成树，但不包含边 (u,v)。由于 T是树，且是连通的，因此有一条从 u到 v的路径；且该路径上必有一条连接两个顶点集 U和 V-U的边 (u′,v′)，其中 u′∈ U，
v′∈ V-U，否则 u和 v不连通。当把边 (u,v)加入树 T时，
得到一个含有边 (u,v)的回路，见图 7-15。删去边 (u′，
v′)，上述回路即被消除，由此得到另一棵生成树 T′,T′
和 T的区别仅在于用边 (u,v)取代了 T中的边 (u′,v′)。
因为 (u,v)的权＜ (u′,v′)的权，故 T′的权＜ T的权，因此 T′也是 G的最小生成树，它包含边 (u,v)，与假设矛盾 !
假设 G＝ (V,E)是连通网络,为简单起见,我们用序号 1至 n来表示顶点集合,即 v＝ {1,2,…,n}。 设所求的最小生成树为 T＝ (U，
TE),其中 U是 T的顶点集,TE是 T的边集 。 并且将 G中边上的权看做是长度 。
Prim算法的基本思想是：首先从 v中任取一个顶点 u0,将生成树 T
置为仅有一个结点 u0的树,即置 U＝ {u0}；然后只要 U是 V的真子集,就在所有那些其一个端点 u己在 T(即 u∈ U),另一个端点 v还未在 T(即 v∈ V— U)的边中,找一条最短 (即权最小 )的边 (u,v),并把该条边 (u,v)和其不在 T中的顶点 v,分别并入 T的边集 TE和顶点集 U。 如此进行下去,每次往生成树里并入一个顶点和一条边,
直到把所有顶点都包括进生成树 T为止 。 此时,必有 U＝ V,TE中有 n-1条边 。 MST性质保证上述过程求得的 T＝ (U,TE)是 G的一棵最小生成树 。
显然,Prim算法的关键是如何找到连接 U和 V-U的最短边来扩充生成树 T。为直观解释方便，设想在构造过程中,T的顶点集 U中顶点和边集 TE中的边均被涂成红色,U之外的顶点集 V-U中的顶点均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么．最短紫边就是连接 U和 V-U的最短边。
最短路径交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?
交通网络可用带权图来表示 。 顶点表示城市名称,边表示两个城市有路连通,边上权值可表示两城市之间的距离,交通费或途中所花费的时间等 。 求两个顶点之间的最短路径,不是指路径上边数之和最少,而是指路径上各边的权值之和最小 。
另外，若两个顶点之间没有边，则认为两个顶点无通路，
但有可能有间接通路（从其他顶点达到 )）。路径上的开始顶点 (出发点 )称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。
所有顶点对之间的最短路径所有顶点对之间的最短路径是指：对于给定的有向网 G=(V,E)，要对 G中任意一对顶点有序对 V,W(V≠W)，找出 V到 W的最短距离和 W到 V的最短距离。解决此问题的一个有效方法是,轮流以每一个顶点为源点，重复执行迪杰斯特拉算法 n次，
即可求得每一对顶点之间的最短路径,总的时间复杂度为 O(n3)。
弗洛伊德算法 仍然使用 前面定义的 图的邻接 矩阵
cost[n+1][n+1]来存储带权有向图 。 算法的基本思想是,
设置一个 nxn的矩阵 A(k),其中除对角线的元素都等于 0
外,其他元素 a(k)[i][j]表示顶点 i到顶点 j的路径长度,K
表示运算步骤 。 开始时,以任意两个顶点之间的有向边的权值作为路径长度,没有有向边时,路径长度为 ∞，
当 K=0时,A (0)[i][j]=arcs[i][j],
以后逐步尝试在原路径中加入其他顶点作为中间顶点，
如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。
具体做法为：第一步，让所有边上加入中间顶点 1，取
A[i][j]与 A[i][1]+A[1][j]中较小的值作 A[i][j]的值，完成后得到 A(1)，第二步，让所有边上加入中间顶点 2，取
A[i][j]与 A[i][2]+A[2][j]中较小的值，完成后得到 A(2)…,
如此进行下去，当第 n步完成后，得到 A(n),A(n)即为我们所求结果,A(n)[i][j]表示顶点 i到顶点 j的最短距离。
拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，
整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图 7-24给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须学完高等数学。在图 7-24（ b）中，我们用一种有向图来表示课程开设，在这种有向图中，
顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络 (Active On Vertices)简称为
AOV网。
在 AOV网中,<i,j>有向边表示 i活动应先于 j活动开始，即
i活动必须完成后,j活动才可以开始，并称 i为 j的直接前驱,j为 i的直接后继。这种前驱与后继的关系有传递性，此外，任何活动 i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看,AOV网中不能出现有向回路（或称有向环）。在 AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程而言，将出现死循环。因此，对给定的 AOV网，应先判断它是否存在有向环。判断
AOV网是否有有向环的方法是对该 AOV网进行拓扑排序，将 AOV网中顶点排列成一个线性有序序列，若该线性序列中包含 AOV网全部顶点，则 AOV网无环，否则,AOV网中存在有向环，该 AOV网所代表的工程是不可行的。
本章小结图是一种复杂的非线性结构,具有广泛的应用背景 。 本章涉及到的基本概念有：
图,由两个集合 V和 E组成,记为 G＝ (V,E),其中 v是顶点的有穷非空集合,E是 V中顶点偶对 （ 称为边 ） 的有穷集 。 通常,也将图 G的顶点集和边集分别记为 V(G)和
E(G)。 E(G)可以是空集,若 E(G)为空,则图 G只有顶点而没有边,称为空图 。
有向图 （ Digraph）,若图 G中的每条边都是有方向的,则称 G为有向图 。
无向图 （ Undigraph）,若图 G中的每条边都是没有方向的,则称 G为无向图 。
无向完全图 (Undirected Complete Graph),恰好有 n(n-1)／ 2条边的无向图称为无向完全图 。
有向完全图 (DirectedComplete Graph)：恰有 n(n-1)条边的有向图称为有向完全图 。
邻接点 (Adjacent)：若 (vi,vj)是一条无向边,则称顶点 vi和 vj互为邻接点 。
度 (Degree)：无向图中顶点 v的度是关联于该顶点的边的数目 。
人度 (1ndegree)若 G为有向图,则把以顶点 v为终点的边的数目,称为 v的人度,记为
ID(v)。
出度 (outdegree)：把以顶点 v为始点的边的数目,称为 v的出度,记为 OD(v)。
子图 (Subgraph)：设 G＝ (V,E)是一个图，若 v′ 是 v的子集,E′ 是 E的子集，且 E′
中的边所关联的顶点均在 v′ 中，则 G′ ＝ (V′,E′ )也是一个图，并称其为 G的子图。
路径 (Path)：在无向图 G中,若存在一个顶点序列 vp,vi1,vi2…,vin,vq,使得 (vp,vil)，
(vi1,vi2),…,(vin,vq)均属于 E(G),则称顶点 vp到 vq存在一条路径 。
路径长度,该路径上边的数目 。
简单路径,若一条路径上除了 vp和 vq可以相同外,其余顶点均不相同,则称此路径为一条简单路径 。
简单回路或简单环 (Cycle)：起点和终点相同 (vp＝ vq)的简单路径称为简单回路或简单环 。
有根图,在一个有向图中,若存在一个顶点 v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图,v称作图的根 。
连通,在无向图 G中,若从顶点 vi到顶点 vj有路径 (当然从 vj到 vi也一定有路径 ),则称 vi和 vj是连通的 。
连通图 (Connected Graph)：若 V(G)中任意两个不同的顶点 vi和 vj都连通 (即有路径 ),则称 G为连通图 。
连通分量 (connectedComponent)：无向图 G的极大连通子图称为 G的连通分量 。
强连通图,在有向图 G中,若对于 V(G)中任意两个不同的顶点 vi和 vj,都存在从 vi到 vj以及从 vj到 vi
的路径,则称 G是强连通图 。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量 。
网络 (Network)：若将图的每条边都赋上一个权,则称这种带权图为网络 。
生成树 (Spanning Tree)：连通图 G的一个子图如果是一棵包含 G的所有顶点的树,则该子图称为 G
的生成树 。
最小生成树 (MinimunSpanning Tree)：权最小的生成树称为 G的最小生成树 。
本章在介绍图的基本概念的基础上,还介绍了图的两种常用的存储结构,对图的遍历,最小生成树等问题做了较详细的讨论,给出了相应的求解算法,有的算法采用自顶向下,逐步求精的方法加以介绍,也许能便于读者理解它们 。
相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，
学会引用本章的有关内容。
