北京师范大学数据结构教学资料 第8章——图.ppt
《北京师范大学数据结构教学资料 第8章——图.ppt》由会员分享,可在线阅读,更多相关《北京师范大学数据结构教学资料 第8章——图.ppt(146页珍藏版)》请在三一文库上搜索。
1、146-1,图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络,第八章 图,146-2,图的基本概念,图定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构: Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合; E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是顶点之间关系的有穷集合,也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。,146-3,有向图与无向图 在有向图中,顶点对 是有序的。在无向图中,顶点对
2、(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,146-4,邻接顶点 如果 (u, v) 是 E(G) 中的一条边,则称 u 与 v 互为邻接顶点。 子图 设有两个图G(V, E) 和G(V, E)。若V V 且EE, 则称图G是图G的子图。 权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。,子图,146-5,顶点的度 一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,
3、顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。 路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm,到达顶点vj。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于E的边。,146-6,路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。 简单
4、路径 若路径上各顶点 v1, v2, ., vm 均不 互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。,0,1,2,3,0,1,2,3,0,1,2,3,146-7,连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。
5、 生成树 一个连通图的生成树是其极小连通子图,在 n 个顶点的情形下,有 n-1 条边。,146-8,图的抽象数据类型,class Graph /对象: 由一个顶点的非空集合和一个边集合构成 /每条边由一个顶点对来表示。 public: Graph(); /建立一个空的图 void insertVertex (const T /在图中删除顶点v和所有关联到它的边,146-9,void removeEdge (int v1, int v2); /在图中删去边(v1,v2) bool IsEmpty(); /若图中没有顶点, 则返回true, 否则返回false T getWeight (int
6、v1, int v2); /函数返回边 (v1,v2) 的权值 int getFirstNeighbor (int v); /给出顶点 v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 ;,146-10,图的存储表示,图的模板基类 在模板类定义中的数据类型参数表 中,T是顶点数据的类型,E是边上所附数据的类型。 这个模板基类是按照最复杂的情况(即带权无向图)来定义的,如果需要使用非带权图,可将数据类型参数表 改为 。 如果使用的是有向图,也可以对程序做相应的改动。,146-11,图的模板基类,c
7、onst int maxWeight = ; /无穷大的值(=) const int DefaultVertices = 30; /最大顶点数(=n) template class Graph /图的类定义 protected: int maxVertices; /图中最大顶点数 int numEdges; /当前边数 int numVertices; /当前顶点数 int getVertexPos (T vertex); /给出顶点vertex在图中位置 public:,146-12,Graph (int sz = DefaultVertices); /构造函数 Graph(); /析构函数
8、 bool GraphEmpty () const /判图空否 return numEdges = 0; int NumberOfVertices () return numVertices; /返回当前顶点数 int NumberOfEdges () return numEdges; /返回当前边数 virtual T getValue (int i); /取顶点 i 的值 virtual E getWeight (int v1, int v2); /取边上权值 virtual int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点,146-13,virt
9、ual int getNextNeighbor (int v, int w); /取邻接顶点 w 的下一邻接顶点 virtual bool insertVertex (const T vertex); /插入一个顶点vertex virtual bool insertEdge (int v1, int v2, E cost); /插入边(v1,v2), 权为cost virtual bool removeVertex (int v); /删去顶点 v 和所有与相关联边 virtual bool removeEdge (int v1, int v2); /在图中删去边(v1,v2) ;,146-
10、14,邻接矩阵 (Adjacency Matrix),在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E) 是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn,定义:,146-15,无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。,146-16,在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度,统计第 j 列 1 的个数可得顶点 j 的入度。 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。,网络的邻接矩阵,146-17,用邻接矩阵表示的图的类定义,templa
11、te class Graphmtx : public Graph friend istream /输入,146-18,friend ostream public:,146-19,Graphmtx (int sz = DefaultVertices); /构造函数 Graphmtx () /析构函数 delete VerticesList; delete Edge; T getValue (int i) /取顶点 i 的值, i 不合理返回0 return i = 0 /取顶点 v 的第一个邻接顶点,146-20,int getNextNeighbor (int v, int w); /取 v
12、的邻接顶点 w 的下一邻接顶点 bool insertVertex (const T vertex); /插入顶点vertex bool insertEdge (int v1, int v2, E cost); /插入边(v1, v2),权值为cost bool removeVertex (int v); /删去顶点 v 和所有与它相关联的边 bool removeEdge (int v1, int v2); /在图中删去边(v1,v2) ;,146-21,template Graphmtx:Graphmtx (int sz) /构造函数 maxVertices = sz; numVertic
13、es = 0; numEdges = 0; int i, j; VerticesList = new TmaxVertices; /创建顶点表 Edge = (int *) new int *maxVertices; for (i = 0; i maxVertices; i+) Edgei = new intmaxVertices; /邻接矩阵 for (i = 0; i maxVertices; i+) /矩阵初始化 for (j = 0; j maxVertices; j+) Edgeij = (i = j) ? 0 : maxWeight; ,146-22,template int Gr
14、aphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol ,146-23,template int Graphmtx:getNextNeighbor (int v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 ,146-24,邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。 在邻接表中,同一个顶点发出的边链接在
15、同一个边链表中,每一个链结点代表一条边(边结点),结点中有另一顶点的下标 dest 和指针 link。对于带权图,边结点中还要保存该边的权值cost。 顶点表的第 i 个顶点中保存该顶点的数据,以及它对应边链表的头指针adj。,邻接表 (Adjacency List),146-25,无向图的邻接表,统计某顶点对应边链表中结点个数,可得该顶点的度。 某条边(vi, vj)在邻接表中有两个边结点,分别在第 i 个顶点和第 j 个顶点对应的边链表中。,146-26,有向图的邻接表和逆邻接表,146-27,网络 (带权图) 的邻接表,统计出边表中结点个数,得到该顶点的出度; 统计入边表中结点个数,得到
16、该顶点的入度。,146-28,在邻接表的边链表中,各个边结点的链入顺序任意,视边结点输入次序而定。 设图中有 n 个顶点,e 条边,则用邻接表表示无向图时,需要 n 个顶点结点,2e 个边结点;用邻接表表示有向图时,若不考虑逆邻接表,只需 n 个顶点结点,e 个边结点。 当 e 远远小于 n2 时,可以节省大量的存储空间。此外,把同一个顶点的所有边链接在一个单链表中,也使得图的操作更为便捷。,146-29,用邻接表表示的图的类定义,template struct Edge /边结点的定义 int dest; /边的另一顶点位置 E cost; /边上的权值 Edge *link; /下一条边链
17、指针 Edge () /构造函数 Edge (int num, E cost) /构造函数 : dest (num), weight (cost), link (NULL) bool operator != (Edge,146-30,template struct Vertex /顶点的定义 T data; /顶点的名字 Edge *adj; /边链表的头指针 ; template class Graphlnk : public Graph /图的类定义 friend istream /输出,146-31,private: Vertex *NodeTable; /顶点表 (各边链表的头结点)
18、int getVertexPos (const T vertx) /给出顶点vertex在图中的位置 for (int i = 0; i numVertices; i+) if (NodeTablei.data = vertx) return i; return -1; public: Graphlnk (int sz = DefaultVertices); /构造函数 Graphlnk(); /析构函数,146-32,T getValue (int i) /取顶点 i 的值 return (i = 0 ,146-33,template Graphlnk:Graphlnk (int sz) /
19、构造函数:建立一个空的邻接表 maxVertices = sz; numVertices = 0; numEdges = 0; NodeTable = new VertexmaxVertices; /创建顶点表数组 if (NodeTable = NULL) cerr “存储分配错!“ endl; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL; ,146-34,template Graphlnk:Graphlnk() /析构函数:删除一个邻接表 for (int i = 0; i *p = NodeTable
20、i.adj; while (p != NULL) NodeTablei.adj = p-link; delete p; p = NodeTablei.adj; delete NodeTable; /删除顶点表数组 ,146-35,template int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为 v 的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; /对应边链表第一个边结点 if (p != NULL) return p-dest; /存在, 返回第一
21、个邻接顶点 return -1; /第一个邻接顶点不存在 ,146-36,template int Graphlnk:getNextNeighbor (int v, int w) /给出顶点v的邻接顶点w的下一个邻接顶点的位置, /若没有下一个邻接顶点, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; while (p != NULL /下一邻接顶点不存在 ,146-37,邻接多重表 (Adjacency Multilist),在邻接多重表中, 每一条边只有一个边结点。为有关边的处理提供了方便。 无向图的情形 边结点的结构 其中, m
22、ark 是记录是否处理过的标记; vertex1和vertex2是该边两顶点位置。path1域是链接指针, 指向下一条依附顶点vertex1的边;path2 是指向下一条依附顶点vertex2的边链接指针。,146-38,需要时还可设置一个存放与该边相关的权值的域 cost。 顶点结点的结构 顶点信息的结点表以顺序表方式组织, 每一个顶点结点有两个数据成员:其中,data 存放与该顶点相关的信息,Firstout 是指示第一条依附该顶点的边的指针。 在邻接多重表中, 所有依附同一个顶点的边都链接在同一个单链表中。,146-39,从顶点 i 出发, 可以循链找到所有依附于该顶点的边,也可以找到它
23、的所有邻接顶点。,邻接多重表的结构,146-40,有向图的情形 在用邻接表表示有向图时, 有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表(十字链表)可把两个表结合起来表示。 边结点的结构 其中,mark是处理标记;vertex1和vertex2指明该有向边始顶点和终顶点的位置。path1是指向始顶点与该边相同的下一条边的指针;path2是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域cost。,146-41,顶点结点的结构 每个顶点有一个结点,它相当于出边表和入边表的表头结点:其中,数据成员data存放与该顶点相关的信息,指针Firstout 指示以该顶点为始顶点的出边表的第
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京师范大学数据结构教学资料 第8章图 北京师范大学 数据结构 教学 资料
链接地址:https://www.31doc.com/p-3102264.html