第7章图 7.1图的基本概念 人路共施图世 7.11图的定义 图G( Graph)由两个集合V Vertex)和E(Edge)组成,记为 G=(V,E),其中Ⅴ是顶点的有限集 记为v(G),E是连接V中两个不同顶 点(顶点对)的边的有限集合,记为 一幅图 E(G)
第7章 图 7.1 图的基本概念 7.1.1 图的定义 图G（Graph）由两个集合V （Vertex）和E（Edge）组成，记为 G=(V,E)，其中V是顶点的有限集合， 记为V(G)，E是连接V中两个不同顶 点（顶点对）的边的有限集合，记为 E(G)。 一幅图
抽象数据类型图的定义如下: ADT Grap h 数据对象: D={a11≤i≤n,n>0,a为int类型} /:为每个顶点的唯一编号 数据关系: R={ r=(,2|aa1∈D,1Kn,1≤n,其中a可以有零个或多个 前驱元素,可以有零个或多个后继元素} 基本运算 void CreateMGraph0:根据相关数据建立一个图。 string DispMgrapho:输出一个图 int Getn(:求图中顶点个数。 int Gete:求图中边数。 int Degree(intv):求顶点v的度。 DFS(ⅴ):从顶点v出发深度优先遍历图 BFS():从顶点v出发广度优先遍历图
抽象数据类型图的定义如下： ADT Graph { 数据对象： D={ai | 1≤i≤n,n≥0,ai为int类型} //ai为每个顶点的唯一编号 数据关系： R={r} r={<ai ,aj> | ai ,aj∈D,1≤i≤n，1≤j≤n，其中ai可以有零个或多个 前驱元素，可以有零个或多个后继元素} 基本运算： void CreateMGraph()：根据相关数据建立一个图。 string DispMGraph()：输出一个图。 int Getn()：求图中顶点个数。 int Gete()：求图中边数。 int Degree(int v)：求顶点v的度。 DFS(v)：从顶点v出发深度优先遍历图。 BFS(v)：从顶点v出发广度优先遍历图。 … }
说明:对于n个顶点的图,对每个顶点连续编号,即顶 点的编号为0-n-1。通过编号唯一确定一个顶点。 在图G中,如果代表边的顶点对是无序的,则称G为无向 图,无向图中代表边的无序顶点对通常用圆括号括起来,用 以表示一条无向边。 如果表示边的顶点对是有序的,则称G为有向图,在有向 图中代表边的顶点对通常用尖括号括起来
说明：对于n个顶点的图，对每个顶点连续编号，即顶 点的编号为0－n-1。通过编号唯一确定一个顶点。 在图G中，如果代表边的顶点对是无序的，则称G为无向 图，无向图中代表边的无序顶点对通常用圆括号括起来，用 以表示一条无向边。 如果表示边的顶点对是有序的，则称G为有向图，在有向 图中代表边的顶点对通常用尖括号括起来
图(a)是一个无向图G1,其顶点集合(G1)={0,1,2,3,4},边 集合E(G1)={(1,2)2(1,3,1,0)、2,3),(3,0),(2,4),(3,4),(4,0)} 图2(b)是一个有向图G2,其顶点集合v(G2)={0,1,2,3,4} 边集合E(G2)=(<1,2>,<1,3>,<0,1>,<23>,-0,3>,<2,4>,<4,3>,<4,0>}。 (a)一个无向图 (b)一个有向图
1 2 3 0 4 1 2 3 0 4 （a）一个无向图 （b）一个有向图 图（a）是一个无向图G1，其顶点集合V(G1 )={0,1,2,3,4}，边 集合E(G1 )={(1,2),(1,3),(1,0),(2,3),(3,0),(2,4),(3,4),(4,0)}。 图2（b）是一个有向图G2，其顶点集合V(G2 )={0,1,2,3,4}， 边集合E(G2 )={<1,2>,<1,3>,<0,1>,<2,3>,<0,3>,<2,4>,<4,3>,<4,0>}
712图的基本术语 1.端点和邻接点 在一个无向图中,着存在一条边 j,则称顶点和顶点为此边的两个端点, 并称它们互为邻接点。 在一个有向图中,若存在一条边< 户,则称此边是顶点)的一条出边,同时 也是顶忘一条入边;称顶点顶点 分别为此边的起始端点(简称为起点)(2 和终止端点(简称终点);称顶点和 顶忘互为邻接点
7.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中，若存在一条边(i， j)，则称顶点i和顶点j为此边的两个端点， 并称它们互为邻接点。 在一个有向图中，若存在一条边<i， j>，则称此边是顶点i的一条出边，同时 也是顶点j的一条入边；称顶点i和顶点j 分别为此边的起始端点（简称为起点） 和终止端点（简称终点）；称顶点i 和 顶点j 互为邻接点。 1 2 3 0 4 (a) 1 2 3 0 4 (b)