《软件工程chapter3.3》由会员分享，可在线阅读，更多相关《软件工程chapter3.3（86页珍藏版）》请在金锄头文库上搜索。
1、计算机软件基础3.3 图一图的定义图G由两个集合V（G）和E（G）组成，记作G=（V，E）。其中V（G）是顶点的有穷非空集合，E（G）是边的有穷集合。若图G中的边没有方向，则称图G为无向图。若图G中的边有方向，则称图G为有向图。计算机软件基础G1即为一个无向图。无向图中顶点的无序对，即 无向边，通常用圆括号表示。如（Vi，Vj），也可 写作（Vj，Vi）。 G2即为一个有向图。有向图中顶点的有序对， 即有向边或弧，通常用尖括号表示。如 ，Vi为边的起点，也称弧尾，Vj为边的终点，也 称弧头。 1243123无向图G1 有向图G2计算机软件基础图G1的顶点集合和边集合分别为：V(G1)=V1,V
2、2,V3,V4 E(G1)=(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)图G2的顶点集合和边集合分别为：V(G2)=V1,V2,V3E(G2)=, 图的集合表示：计算机软件基础v 图的有关术语 邻接：在无向图中，若存在边（Vi,Vj），则称顶 点Vi邻接于Vj，或Vj邻接于Vi；在有向图中，若存在弧，则称顶点 Vj邻接于顶点Vi。 度：在无向图中，一个顶点的度是指与该顶点 相连的边数。在有向图中，度分为入度和出度。一个顶 点的入度是指以该顶点为终点的边数；出度则 是指以该顶点为起点的边数；一个顶点的度是 其入度和出度之和。计算机软件基础 路径：在无向图G中，从
3、顶点V到顶点V的路径是 一个顶点序列（V，Vi1，Vi2，Vin，V），其 中（V，Vi1），（Vi1，Vi2），（Vin，V） 均属于E（G）。若G是有向图，则路径也是有向的，顶点序 列应满足， 均属于E（G）。路径的长度是指路径上边或弧的 数目。1243123无向图G1 有向图G2计算机软件基础 连通图：在无向图中，若从顶点V到顶点V有 路径，则称V和V是连通的。如果对图G中任意 两个顶点Vi、VjV，Vi和Vj都是连通的，则称G 是连通图。 强连通图：在有向图G中，若对于每一对顶点 Vi、VjV ，从Vi到Vj和Vj到Vi都有路径，则称G 是强连通图。1243512435连 通 图 示
4、例强 连 通 图 示 例计算机软件基础 完全无向图：若一个具有n个顶点的无向图共有 n(n-1)/2条边，即每一对顶点之间都有边相连， 则称其为完全无向图。 完全有向图：若一个具有n个顶点的有向图共 有n(n-1)条边，即每一对顶点之间都有两条方向 不同的边相连，则称其为完全有向图。1243132 完全无向图完全有向图计算机软件基础 网：边或弧上带有权值的图称为网。权值是 与边或弧有关的数，可以表示从一顶点到另一 顶点的距离或耗费等。 二. 图的逻辑结构 分析：对于图中的任意顶点来说，都可以有 多条以其为起点的边，并且可以有多条以其 为终点的边。结论：图中顶点的逻辑关系是多对多的关系 ，体现在
5、顶点之间是否有边相连（邻接关系 ） 。 计算机软件基础三. 图的存储结构 注意：图存储时，既要存储图中各顶点的数据 信息，又要存储各顶点间的逻辑关系。 1. 顺序存储结构 通过两个数组来实现。（1）一维数组：用于存放各顶点数据信息；（2）二维数组：用于存放各顶点逻辑关系，也称为邻接矩阵。 计算机软件基础对于一个有n个顶点的图，其邻接矩阵为一个n阶方阵，方阵中只有0和1元素，通过某个位置上的元素是0还是1来表示对应的两个顶点之间有无邻接关系。方阵中的元素值按下式确定：v 邻接矩阵的构成：Aij =1 当顶点Vj邻接于Vi时(从Vi 到Vj有边相连) 0 当顶点Vj不邻接于Vi时(从Vi 到Vj无
6、边相连) 计算机软件基础例：写出下面无向图G5和有向图G6的邻接 矩阵。1324有向图G6 A6 =A5 =1243无向图G5计算机软件基础typedef struct graph int edgN+1N+1; /edg数组用于存放图的邻接矩阵char verN+1; /ver用于存放图中各顶点的数据值，这里假定 顶点的数据值为字符型*/ GRAPH; 计算机软件基础2. 链式存储结构 方法：为图中的每一个顶点建立一个相应的 单链表（邻接链表），顶点的数据信息存放在 单链表的头结点中，邻接顶点的序号分别存放 在单链表的各个表结点中。单链表的头结点和 表结点的结构如下所示：ver first a
7、djv next头结点表结点v 头结点：ver域用于存放该顶点的数据信息，first域 用于存放链表中第一个表结点的地址。v 表结点：adjv域用于存放该顶点的某个邻接顶点的 序号，next域用于存放链表中下一个表结点的地址。计算机软件基础V2132V12341 V31243V41341243无向图G5V212V1231 V3324 V4431324 有向图G6例：画出下面无向图G5和有向图G6的邻接 链表示意图。计算机软件基础struct adjnode int adjv；struct adjnode *next；struct vernode char ver；struct adjnode
8、*first； ;struct vernode adjlistN+1； 其中，adjnode为表结点类型，vernode为头结 点类型，N为顶点的个数。v 图的邻接链表数据类型定义如下：注意： 1. 这里假定顶点的数据值为字符型。 2. 为了与图中各顶点的序号相一致，可在adjlist 中不使用下标为0的元素。 计算机软件基础四. 图的遍历 图的遍历是指从图的某个顶点出发，沿着 一定的搜索路径，对图中各个顶点进行访问， 使每个顶点均被访问且仅访问一次。 图的遍历方法有两种，分别是深度优先搜 索和广度优先搜索。 深度优先搜索算法的主要特点：遍历时尽可 能向纵深的方向去搜索。 广度优先搜索算法的主
9、要特点：遍历时尽可 能向广的方向去横向搜索。 计算机软件基础难点一：由于图中顶点间的逻辑关系比树中结点间 的逻辑关系复杂得多。在访问了图某个顶点后 ，有可能沿着某条路径搜索时又回到该顶点。 如何避免同一顶点在遍历过程中被多次访问？难点二：如何确定遍历过程中顶点访问的先后次序 ？ v 算法实现中的难点：计算机软件基础v 解决办法：1. 在遍历算法中设置了一个辅助数组visited ，用它来记下每个顶点的访问状态。用0值 表示未访问，用1值表示已访问。遍历前， 数组的所有元素初始值均为0；遍历过程中 ，每访问一个顶点后就将其对应的数组元 素置为1。2. 在邻接矩阵或邻接链表中从前向后逐个搜 索需要
10、访问的邻接顶点 。计算机软件基础v 算法思想：访问Vi，并将其对应的访问标志位visitedi置为1；搜索出Vi的一个未访问过的邻接点Vj；从Vj出发，按以上步骤继续进行深度优先搜索，直至所有顶点均访问完毕。 1. 深度优先搜索算法（从Vi出发） 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V10 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从
11、顶点1出发） 深度优先搜索遍历序列为：V10 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V20 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V20 1 1
12、 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V20 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V2 V30 1 1 1 0 0 10 1 1 0 0 1 1 0
13、 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V2 V30 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V2 V30 1 1 1 0 0 10 1 1 0 0 1 1 0 1 0 1 11 1 1 0 1 0 20 0 0 1 0 0 30 0 1 0 0 0 计算机软件基础124356例：对如下顺序存储的无向图进行深度优先搜索 。（假定遍历从顶点1出发） 深度优先搜索遍历序列为：V1 V2 V3 V40 1 1 1 0 0 10
