第八章 委图的基本概念 图的存储表示 圈的遍历与连通性 最小生成材 最短路径 活动网络
图的基本概念 图定义图是由顶点集合 vertex)及顶点间 的关系集合组成的一种数据结构: Graph=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合; E={(xy)|xy∈V 或E={x,y>|x,y∈v&&Pamh(x,y) 是顶点之间关系的有穷集合,也叫做边 (edge)集合。Pah(x,y)表示从x到y的 条单向通路,它是有方向的
(vertex) ：
有向图与无向图在有向图中,顶点对是有序的。在无向图中,顶点对(x,y)是 无序的。 完全图若有m个顶点的无向图有m(m-1)2 条边,则此图为完全无向图。有m个顶点 的有向图有m(m-1)条边,则此图为完全有向 (0 ①②①②2⑦ 6
0 0 0 0 1 1 1 2 1 2 3 3 4 5 6 2 2
邻接顶点如果(u)是B(G)中的一条边 则称与ν互为邻接顶点 子图设有两个图G=(VE和G=(V, E)。若VgV且E≌E,则称图G是图G 的子图。 0 子图 0 ①1②-①①②|② 3 3 3 权某些图的边具有与它相关的数,称之为 权。这种带权图叫做网络
。 0 1 2 3 子图 0 1 3 0 1 2 3 0 2 3
顶点的度一个顶点y的度是与它相关联的 边的条数。记作TD()。在有向图中,顶点 的度等于该顶点的入度与出度之和 顶点v的入度是以v为终点的有向边的条 数,记作ID吵)顶点p的出度是以v为始点 的有向边的条数,记作OD()。 路径在图G=(VE)中,若从顶点v出发, 沿一些边经过一些顶点v 9●9 到 达顶点则称顶点序列(vnv pin 为从顶点v到顶点的路径。它经过的边 (v咧)、(,v)、…、(m吵应是属于E 的边
路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权之和 简单路径若路径上各顶点v12y…,Vm均不 互相重复,则称这样的路径为简单路径。 回路若路径上第一个顶点v与最后一个 顶点Vm重合,则称这样的路径为回路或环。 好2①2 3 3
0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量在无向图中,若从顶点 1到顶点有路径,则称顶点v与2是连通 的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通 子图叫做连通分量。 强连通图与强连通分量在有向图中,若对 于每一对顶点和v都存在一条从w到和 从到w的路径则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量 生成树一个连通图的生成树是其极小连 通子图,在个顶点的情形下,有n-1条边
图的抽象数据类型 class graph i public Graph (); void Insert Vertex( Type vertex void InsertEdge( int vl, int v2, int weight ) void Remove Vertex( int v ) void RemoveEdge( int vI, int v2 ); int IsEmpty o Type Get Weight( int v1, int v2 ) int GetFirstNeighbor( int v ); int GetNextNeighbor( int vI, int v2)
class Graph { public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v2, int weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); }
图的存储表示 邻接矩阵( Adjacency Matrix) 在图的邻接矩阵表示中,有一个记录各个 顶点信息的顶点表,还有一个表示各个顶 点之间关系的邻接矩阵。 口设图A=(V,E)是一个有m个顶点的图,图 的邻接矩阵是一个二维数组 Aeugenin, 定义: AE44=1如果()E或者(DB 0,.否则
, , , ( , ) . [ ][ ] 否则 如果 或者 0 1 A i j E i j E Edge i j
0 0101 ①2 Aedge= 1010 0101 ③3 1010 002 「010 A edge= 101 000 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的
0 1 2 3 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 A.edge 012 0 0 0 1 0 1 0 1 0 A.edge