图、邻接矩阵、邻接表、遍历、生成树.ppt

* 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 有向图(directed graph or digraph)——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头 无向图(Undirected graph)——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 8.1 图的定义（Definitions of Graphs） 例 2 4 5 1 3 6 G1 图G1中：V(G1)={1,2,3,4,5,6} E(G1)={1,2, 2,1, 2,3, 2,4, 3,5, 5,6, 6,3} 例 1 5 7 3 2 4 G2 6 图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} 有向完全图—n个顶点的有向图具有n(n-1)条弧 无向完全图—n个顶点的无向图具有n(n-1)/2条边 权——与图的边或弧相关的数叫~ 网——带权的图叫~ 子图(subgraph)——如果图G(V,E)和图G‘(V’,E‘),满足： V’?V E’?E 则称G‘为G的子图 顶点的度 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度，顶点的度为二者之和 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 例 2 1 3 2 1 3 有向完备图 无向完备图 3 5 6 例 2 4 5 1 3 6 图与子图 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4 例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 连通图——图中任意两个顶点都是连通的叫~ 连通分量——无向图中的极大连通子图 强连通图——有向图中，如果对每一对Vi, Vj?V, Vi?Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~ 强连通分量——有向图中的极大强连通子图称做有向图的强连通分量 连通图 例 2 4 5 1 3 6 强连通图 3 5 6 例 非连通图 强连通分量 例 2 4 5 1 3 6 图没有顺序存储结构 用如下的多重链表表示图也不采用 例 G1 2 4 1 3 例 1 5 3 2 4 G2 V1 V2 ^ ^ V4 ^ V3 ^ ^ V1 V2 V4 ^ V5 ^ V3 8.2 图的存储结构(Storage Structure of Graphs) 8.2.1 邻接矩阵(adjacency matrix) ——表示顶点间相联关系的矩阵 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵 例 G1 2 4 1 3 例 1 5 3 2 4 G2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 例 1 4 5 2 3 7 5 3 1 8 6 4 2 8.3.1 Definitions 从给定图中任意指定的顶点(称为初始点)出发,按照某种有哪些信誉好的足球投注网站方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。 根据有哪些信誉好的足球投注网站方法的不同,图的遍历方法有两种：一种叫做深度优先有哪些信誉好的足球投注网站法(depth-first search, DFS)；另一种叫做广度优先有哪些信誉好的足球投注网站法(breadth-first search, BFS)。 8.3 图的遍历(Graph Traversals) 8.3.2 深度