数据结构与算法设计（第二版）课件 第7章 图.pptx

第七章图西安科技大学计算机学院张小艳数据结构与算法设计

七桥问题7.1图--基本概念图论。欧拉把每一块陆地看成一个点，连接两块陆地的桥用联线表示。把它转化成一个几何问题。七桥问题就转化成了是否能用一笔不重复地画出过此七条线的图形？

142351234图--基本概念顶点边弧

图是一种网状数据结构，是由一个顶点的有穷非空集V(G)和一个弧或边的集合E(G)组成。通常记作二元组G?=?(V，E)其中G表示一个图，V是图G中顶点的集合，E是图G中的弧的集合。线性表可以没有元素，称之为空表；树中可以没有结点，称之为空树；图中不能没有顶点。图--图的定义

图分为无向图和有向图。(a)无向图对于无向图G?=?(V，E)，如果(vi，vj)是一条边，则称顶点vi，vj互为邻接点。边(vi，vj)依附于顶点(vi，vj)。注意：(vi，vj)和(vj，vi)是一条边。无向边用于表示“对称关系”，城市中的双行道可以用无向边表示。图(a)图可以表示为二元组?(V1，E)V1={1,2,3,4,5}E={（1,2）,(1,4),(2,3),(2,5),(3,5),(3,4)}图—图的分类14235

(b)有向图对于有向图G?=?(V，E)，如果?vi，vj?是一条弧，vi称为弧尾或起始点，vj称为弧头(head)或终端点。弧vi，vj?和?弧vj，vi?是两条不同的弧。有向边用于表示“非对称关系”。城市中的单行道用有向边表示。图(b)可以表示为G2??=(V2，A)V2={1,2,3,4}A={1,2,1,3,3,4,4,1,4,2}表示边的序偶用圆括号，表示弧的序偶用尖括号。图—图的分类1234

在一个无向图中，如果任意两个顶点都有一条直接边相邻接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。在一个有向图中，如果任意两个顶点之间都有方向互为相反的两条弧相邻接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。若一个图接近完全图，称为稠密图；反之称为稀疏图。(a)无向完全图(b)有向完全图图—完全图

加权边或加权弧。带权的图称为网或网络(network)。(a)无向网(b)有向网图—权值和网

图--顶点的度顶点的度(degree)是指依附于某顶点v的边数，通常记为TD(v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(v)；顶点v的出度是指以顶点v为始点的弧的数目，记为OD(v)。TD(v)?=?ID(v)?+?OD(v)。

顶点1的度是2，顶点2的度为3，顶点3的度为3，顶点4的度是2，顶点5的度为2，所有顶点的度加起来等12，图中有6条边。15432（a）无向图G1对于具有n个顶点、e条边的无向图：?顶点1的入度为?1，出度为?2；顶点2的入度为2，出度为0；顶点3的入度为1，出度为1；顶点4的入度为1，出度为2；所有顶点的入度之和与出度之和相等，就是边数。1432（b）有向图G2图--顶点的度

图--路径和回路无向图G?=?(V，E)中：从顶点v到顶点v?之间的路径(path)是一个顶点序列(v?=?vi1，vi2，…，vim?=?v)，其中，(vij，vij+1)是E中的一条边，1≤j＜m。路径上边或弧的数目称为路径长度。序列中顶点不重复出现的路径称为简单路径。V1V6V5V4V3V2132161189235712（a）无向网v1→v2→v3→v4v1→v6→v4路径长度分别为3和2，这两条路径都是简单路径。

v1→v2→v6→v5→v4是从顶点v1到顶点v4的一条路径，路径长度为4。v5→v1是从顶点v5到顶点v1的一条路径，路径长度为1。这两条路径都是简单路径。V3V1V6V5V4V289613215712（b）有向网图--路径和回路

无向网(a)中，v1→v2→v6→v5→v1是一条简单回路。有向网(b)中，v1→v2→v6→v5→v1也是一条简单回路。无向网(a)中的v1→v2→v6→v4→v2→v1路径中v2是重复的，就不是简单环了。V1V6V5V4V3V2132161189235712V3V1V6V5V4V289613215712（a）无向网（b）有向网路径中第一个顶点和最后一个顶点相同时称该路径为回路或者环(cycle)。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。图--路径和回路

图--子图对于图G?=?(V，E)，存在G?=?(V，E)，若存在V?是V