第八章 图 图的基本概念 图的存储结构 图的遍历与连通性 最小生成树 最短路径 活动网络 1
第八章 图 • 图的基本概念 • 图的存储结构 • 图的遍历与连通性 • 最小生成树 • 最短路径 • 活动网络 1
图的基本概念 图定义图是由顶点vertex)集合以及顶点 之间的关系集合组成的一种数据结构： G=(E) 其中V={xx∈某个数据对象} 是顶点的有穷非空集合： E={c,y)x,y∈V 或E={x,Jy>|x,Jy∈V&&Pth(化，y)} 是顶点之间关系的有穷集合，也叫做边 (edge)集合。Path (x,y)表示从x到y的一 条单向通路，它是有方向的。 2
图的基本概念 • 图定义 图是由顶点(vertex)集合以及顶点 之间的关系集合组成的一种数据结构： G＝( V, E ) 其中 V = { x | x 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y V } 或 E = { | x, y V && Path (x, y)} 是顶点之间关系的有穷集合，也叫做边 (edge)集合。Path (x, y)表示从 x 到 y 的一 条单向通路, 它是有方向的。 2
有向图与无向图； 在有向图中，顶点对是有序的。在无向图中，顶点对(x,y)是 无序的。 完全图若有n个顶点的无向图有nn-1)/2 条边，则此图为无向完全图。若有n个顶点 的有向图有nn-)条边，则此图为有向完全 图。 0 1 2 2 3
• 有向图与无向图 在有向图中，顶点对 是有序的。在无向图中，顶点对(x, y)是 无序的。 • 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为无向完全图。若有n 个顶点 的有向图有n(n-1) 条边, 则此图为有向完全 图。 3 0 0 0 0 1 1 1 2 1 2 3 3 4 5 6 2 2
邻接顶点 如果(w,y)是E(G)中的一条边， 则称u与v互为邻接顶点。 子图设有两个图G=(V,E)和G=(八，E)。 若V'sV且EcE,则称图G'是图G的子图。 子图 2 2 2 .权或权重(weigh)在某些图中，边具有与 它相关的数值，称为权重。带权图也叫作网 络(network)。 4
• 邻接顶点 如果 (u, v) 是 E(G) 中的一条边， 则称 u 与 v 互为邻接顶点。 • 子图 设有两个图G＝(V, E) 和G'＝(V', E')。 若V ' V 且E'E, 则称图G'是图G的子图。 • 权或权重(weight) 在某些图中，边具有与 它相关的数值, 称为权重。带权图也叫作网 络(network)。 4 子图 0 1 2 3 0 1 3 0 1 2 3 0 2 3
J顶点的度(degree) 一个顶点的度是与它相关联 的边的条数，记作deg(y)。 。 在有向图中，顶点v的入度是以v为终点的有向边 的条数，记作indeg(少；顶点v的出度是以v为始 点的有向边的条数，记作outdeg(y)。在有向图中， 顶点的度等于该顶点的入度与出度之和。 路径 在图G=(V,E)中，若从顶点y:出发，沿一 些边经过若干顶点%1,2，，pm,到达顶点， 则称顶点序列(，p1,p2,…,m,》为从顶点 到顶点y的一条路径。它经过的边(y%”1小、(， y2以小、、(ypm)都是来自于E的边。 5
• 顶点的度 (degree) 一个顶点v的度是与它相关联 的边的条数, 记作deg(v)。 • 在有向图中, 顶点 v 的入度是以 v 为终点的有向边 的条数, 记作 indeg(v); 顶点 v 的出度是以 v 为始 点的有向边的条数, 记作 outdeg(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。 • 路径 在图 G＝(V, E) 中, 若从顶点 vi出发, 沿一 些边经过若干顶点 vp1 , vp2 , …, vpm，到达顶点vj， 则称顶点序列 (vi , vp1 , vp2 , ... , vpm , vj ) 为从顶点vi 到顶点 vj 的一条路径。它经过的边(vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj ) 都是来自于E的边。 5
.路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 简单路径若路径上各顶点y1,y2,,ym均 不互相重复，则称这样的路径为简单路径。 回路 若路径上第一个顶点y,与最后一个 顶点ym重合，则称这样的路径为回路或环。 3 3 3 6
• 路径长度 非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 • 简单路径 若路径上各顶点 v1 , v2 , ..., vm 均 不互相重复, 则称这样的路径为简单路径。 • 回路 若路径上第一个顶点 v1 与最后一个 顶点vm 重合, 则称这样的路径为回路或环。 6 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量？ 在无向图中，若从顶点到顶 点y2有路径，则称顶点与2是连通的。如果图中 任意一对顶点都是连通的，则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中，若对于每 一对顶点y和y,都存在一条从到y和从y到y的 路径，则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树(spanning tree) 一个无向连通图的生成树 是其极小连通子图，在个顶点的情形下，有 n-1条边。若是有向图，则可能得到它的由若干 有向树组成的生成森林
• 连通图与连通分量 在无向图中, 若从顶点v1到顶 点v2有路径, 则称顶点v1与v2是连通的。如果图中 任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 • 强连通图与强连通分量 在有向图中, 若对于每 一对顶点vi和vj , 都存在一条从vi到vj和从vj到vi的 路径, 则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 • 生成树(spanning tree) 一个无向连通图的生成树 是其极小连通子图，在 n 个顶点的情形下，有 n-1 条边。若是有向图，则可能得到它的由若干 有向树组成的生成森林。 7
图的抽象数据类型 class Graph /对象：由一个非空顶点集合和一个边集合构成 /每条边由一个顶点对来表示。 public; GraphO); /建立一个空的图 void insert Vertex (const T&vertex); /插入一个顶点vertex,该顶点暂时没有入边 void insertEdge (int vl,int v2,int weight); /在图中插入一条边(V1,V2,w) yoid remove Vertex (int v); /在图中删除顶点V和所有关联到它的边 8
图的抽象数据类型 class Graph { //对象: 由一个非空顶点集合和一个边集合构成 //每条边由一个顶点对来表示。 public: Graph(); //建立一个空的图 void insertVertex (const T& vertex); //插入一个顶点vertex, 该顶点暂时没有入边 void insertEdge (int v1, int v2, int weight); //在图中插入一条边(v1, v2, w) void removeVertex (int v); //在图中删除顶点v和所有关联到它的边 8
void removeEdge (int v1,int v2); /在图中删去边(V1,V2) bool IsEmptyO; /若图中没有顶点，则返回tru,否则返回 false T getWeight (int v1,int v2); /函数返回边(V1,V2)的权值 int getFirstNeighbor (int v); /给出顶点V第一个邻接顶点的位置 int getNextNeighbor (int v,int w); /给出顶点V的某邻接顶点W的下一个邻 接顶点
void removeEdge (int v1, int v2); //在图中删去边(v1,v2) bool IsEmpty(); //若图中没有顶点, 则返回true, 否则返回 false T getWeight (int v1, int v2); //函数返回边(v1,v2) 的权值 int getFirstNeighbor (int v); //给出顶点v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); //给出顶点v 的某邻接顶点 w 的下一个邻 接顶点 }; 9
图的存储表示 图的模板基类 在模板类定义中的数据类 型参数表中，T是顶点数 据的类型，E是边上所附数据的类型。 这个模板基类是按照最复杂的情况（即带 权无向图)来定义的，如果需要使用非带 权图，可将数据类型参数表改为。 如果使用的是有向图，也可以对程序做相 应的改动。 10
图的存储表示 • 图的模板基类 在模板类定义中的数据类 型参数表 中，T是顶点数 据的类型，E是边上所附数据的类型。 • 这个模板基类是按照最复杂的情况（即带 权无向图）来定义的，如果需要使用非带 权图，可将数据类型参数表 改为 。 • 如果使用的是有向图，也可以对程序做相 应的改动。 10