第八章图 图的基本概念 图的存储结构 图的遍历与连通性 最小生成树 最短路径 活动网络
第八章 图 • 图的基本概念 • 图的存储结构 • 图的遍历与连通性 • 最小生成树 • 最短路径 • 活动网络 1
图的基本概念 图定义图是由顶点 vertex)集合以及顶点 之间的关系集合组成的一种数据结构 G=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合 {(x,y)|x,y∈} 或E={x,少>|x,y∈V&&Pmh(x,y)} 是顶点之间关系的有穷集合,也叫做边 (edge)集合。Pmh(x,y)表示从x到y的一 条单向通路,它是有方向的
图的基本概念 • 图定义 图是由顶点(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个顶点的无向图有m(n-1)2 条边,则此图为无向完全图。若有n个顶点 的有向图有nm-1)条边,则此图为有向完全 图 2 3 3)(4)(5)(6 2
• 有向图与无向图 在有向图中，顶点对 是有序的。在无向图中，顶点对(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
邻接顶点如果{,v)是E(G)中的一条边, 则称u与ν互为邻接顶点。 子图设有两个图G=(,E)和G=(V,E) 若VcV且EcE,则称图G是图G的子图 0 子图 2 3 权或权重 weight)在某些图中,边具有与 它相关的数值称为权重。带权图也叫作网 络( network)
• 邻接顶点 如果 (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
顶点的度( degree)一个页点的度是与它相关联 的边的条数,记作deg(v) 在有向图中,顶点v的入度是以v为终点的有向边 的条数,记作 indeg(吵;顶点v的出度是以v为始 点的有向边的条数,记作 outdeg()。在有向图中 顶点的度等于该顶点的入度与出度之和。 路径在图G=(V,E中,若从顶点v出发,沿 些边经过若干顶点v,V,…,Vm,到达顶点v 则称页点序列(",V,V2,…,Vm,v为从顶点n 到顶点v的一条路径。它经过的边Vv)、(y, pms 以)都是来自于E的边
• 顶点的度 (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
路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 简单路径若路径上各顶点,V2…,V均 不互相重复,则称这样的路径为简单路径。 回路若路径上第一个顶点v与最后一个 顶点v重合,则称这样的路径为回路或环。 2)(1 3
• 路径长度 非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 • 简单路径 若路径上各顶点 v1 , v2 , ..., vm 均 不互相重复, 则称这样的路径为简单路径。 • 回路 若路径上第一个顶点 v1 与最后一个 顶点vm 重合, 则称这样的路径为回路或环。 6 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量在无向图中,若从顶点v到顶 点v有路径,则称顶点v与是连通的。如果图中 任意一对顶点都是连通的,则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量在有向图中,若对于每 对顶点和v都存在一条从到v和从v到p的 路径,则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树( spanning tree)一个无向连通图的生成树 是其极小连通子图,在n个顶点的情形下,有 n-1条边。若是有向图,则可能得到它的由若干 有向树组成的生成森林
• 连通图与连通分量 在无向图中, 若从顶点v1到顶 点v2有路径, 则称顶点v1与v2是连通的。如果图中 任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 • 强连通图与强连通分量 在有向图中, 若对于每 一对顶点vi和vj , 都存在一条从vi到vj和从vj到vi的 路径, 则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 • 生成树(spanning tree) 一个无向连通图的生成树 是其极小连通子图，在 n 个顶点的情形下，有 n-1 条边。若是有向图，则可能得到它的由若干 有向树组成的生成森林。 7
图的抽象数据类型 h class Grap 对象:由一个非空顶点集合和一个边集合构成 每条边由一个顶点对来表示。 public: Grapho; ∥/建立一个空的图 void insert Vertex(const T& vertex); /插入一个顶点 vertex该顶点暂时没有入边 void insertedge(int vl, int v2, int weight); ∥在图中插入一条边(vl,v2,w) void remove Vertex (int v) ∥/在图中删除顶点V和所有关联到它的边
图的抽象数据类型 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 remove Edge(int vl, int v2) ∥在图中删去边(v1,v2) bool is empty ∥若图中没有顶点,则返回true,否则返回 false T get Weight(int vl, 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是边上所附数据的类型。 这个模板基类是按照最复杂的情况(即带 权无向图)来定义的,如果需要使用非带 权图,可将数据类型参数表改为 如果使用的是有向图,也可以对程序做相 应的改动
图的存储表示 • 图的模板基类 在模板类定义中的数据类 型参数表 中，T是顶点数 据的类型，E是边上所附数据的类型。 • 这个模板基类是按照最复杂的情况（即带 权无向图）来定义的，如果需要使用非带 权图，可将数据类型参数表 改为 。 • 如果使用的是有向图，也可以对程序做相 应的改动。 10