软件设计师 http://www.educity.cn/jiaocheng/zg7.html
V1且 E2E1,则称图G2是图G1的子图。
在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。
在图G=（V,E）中，如果存在顶点序列（V0,V1,…，Vk），其中V0=P,Vk=Q,且（V0,V1），（V1,V2），…，（Vk-1,Vk）都在E中，则称顶点P到顶点Q有一条路径，并用（V0,V1,…，Vk）表示这条路径，路径的长度是路径的边数，这条路径的长度为k.若G是有向图，则路径也是有向的。
在有向图G中，若对于V（G）中任意两个不同的顶点Vi和Vj,都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。
有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即其自身。非强连通的有向图有多个强连通分量。 2.图的存储结构
最常用的图的存储结构有邻接矩阵和邻接表。 1）邻接矩阵
邻接矩阵反映顶点间的邻接关系，设G=（V,E）是具有n（n≥1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i,j）或
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
对于无向图，其邻接矩阵第i行元素的和即为顶点i的度。对于有向图，其邻接矩阵第i行元素之和为顶点i的出度，而邻接矩阵第j列元素之和为顶点j的入度。
若将图的每条边都赋上一个权，则称这种带权图为网（络）。如果图G=（V,E）是一个网，若（i,j）或
在图的邻接表表示中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。例如，图1-10（a）和图1-10（b）的邻接表分别如图1-11（a）和图1-11（b）所示。
图1-11 图的邻接表表示
在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。 3.图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
1）深度优先遍历
在G中任选择一顶点V为初始出发点（源点），则深度优先遍历可以定义如下：首先，访问出发点V,并将其标记为已访问过；然后，依次从V出发搜索V的每个邻接点W.若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。 2）广度优先遍历
广度优先遍历的过程是：首先访问出发顶点V;然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,…，Wk-1;接着再依次访问与顶点W0,W1,…，Wk-1邻接的全部未被访问过的顶点。依此类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。
从广度优先搜索遍历过程知，若顶点V在顶点W之前被访问，则对V相邻顶点的访问就先于只与W相邻的那些顶点的访问。因此，需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问这些顶点相邻接的其他还未被访问过的顶点。
1.3.2 最小生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
一。从不同的顶点出发进行遍历，可以得到不同的生成树。
含有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）算法。 1.普里姆算法
设已知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（n2），与图中边数无关，所以适合于稠密图。 2.克鲁斯卡尔算法
设T的初始状态只有n个顶点而无边的森林T=（V,￠），按边长递增的顺序选择E中的n–1安全边（u,v）并加入T,生成最小生成树。所谓安全边，是指两个端点分别是森林T
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。
克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O（elog2e），与图中顶点数无关，所以较适合于稀疏图。
1.3.3 最短路径
带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边权值的总和。路径长度的具体含义取决于边上权值所代表的意义。
1.单源最短路径
已知有向带权图（简称有向网）G=（V,E），找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。
目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看成是已生成的源点到其自身的长度为0的路径）。
迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集（看成红点集），V-S是最短距离尚未确定的顶点集（看成蓝点集）。
（1）初始化：初始化时，只有源点s的最短距离是已知的（SD（s）=0），故红点集S={s},蓝点集为空。
（2）重复以下工作，按路径长度递增的次序产生各顶点的最短路径：在当前蓝点集中