最新北京师范大学数据结构教学资料 第8章——图精品课件.ppt
《最新北京师范大学数据结构教学资料 第8章——图精品课件.ppt》由会员分享,可在线阅读,更多相关《最新北京师范大学数据结构教学资料 第8章——图精品课件.ppt(147页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、146-146-2 2图的基本概念图的基本概念n图定义图定义 图是由顶点集合图是由顶点集合(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 的一条单向通的一条单向通路路, 它是有方向的
2、。它是有方向的。146-146-9 9 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 的下一个邻接顶点;146-146-1010图的存储表示图的存储表示n图
3、的模板基类图的模板基类 在模板类定义中的数据类型在模板类定义中的数据类型参数表参数表 中,中,T是顶点数据的是顶点数据的类型,类型,E是边上所附数据的类型。是边上所附数据的类型。n这个模板基类是按照最复杂的情况(即带权这个模板基类是按照最复杂的情况(即带权无向图)来定义的,如果需要使用非带权图,无向图)来定义的,如果需要使用非带权图,可将数据类型参数表可将数据类型参数表 改为改为 。n如果使用的是有向图,也可以对程序做相应如果使用的是有向图,也可以对程序做相应的改动。的改动。 146-146-11 11图的模板基类图的模板基类 const int maxWeight = ; /无穷大的值(=
4、)const int DefaultVertices = 30; /最大顶点数(=n)template class Graph /图的类定义protected: int maxVertices; /图中最大顶点数 int numEdges; /当前边数 int numVertices; /当前顶点数 int getVertexPos (T vertex); /给出顶点vertex在图中位置public: 146-146-1212 Graph (int sz = DefaultVertices); /构造函数 Graph();/析构函数 bool GraphEmpty () const /判图空
5、否 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-146-1313virtual int getNextNeighbor (int
6、 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-146-1414邻接矩阵邻接矩阵 (Adjacency Ma
7、trix)(Adjacency Matrix)n在图的邻接矩阵表示中,有一个记录各个顶在图的邻接矩阵表示中,有一个记录各个顶点信息的点信息的顶点表顶点表,还有一个表示各个顶点之,还有一个表示各个顶点之间关系的间关系的邻接矩阵邻接矩阵。n设图设图 A = (V, E) 是一个有是一个有 n 个顶点的图个顶点的图, 图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn,定义:,定义: , ),( , , .否否则则或或者者如如果果01EdgeAEjiEjiji146-146-1515n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能是不对称的。有向图的邻接
8、矩阵可能是不对称的。0101101001011010A.edge0123012000101010A.edge146-146-1616n在有向图中在有向图中, 统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度出度,统计第,统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入入度度。n在无向图中在无向图中, 统计第统计第 i 行行 (列列) 1 的个数可得顶的个数可得顶点点i 的的度度。网络的邻接矩阵网络的邻接矩阵jiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.edge146-146-171706805329
9、0410A.edge863129542031用邻接矩阵表示的图的类定义用邻接矩阵表示的图的类定义template class Graphmtx : public Graph friend istream& operator ( istream& in, Graphmtx& G);/输入146-146-1818friend ostream& operator (ostream& out, Graphmtx& G);/输出private: T *VerticesList; /顶点表 E *Edge;/邻接矩阵int getVertexPos (T vertex) /给出顶点vertex在图中的位置
10、 for (int i = 0; i = 0 & i = numVertices ? VerticesListi : NULL; E getWeight (int v1, int v2) /取边(v1,v2)上权值 return v1 != -1 & v2 != -1 ? Edgev1v2 : 0; int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点146-146-2020 int getNextNeighbor (int v, int w); /取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex (const T vertex)
11、; /插入顶点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-146-2121template Graphmtx:Graphmtx (int sz) /构造函数 maxVertices = sz; numVertices = 0; numEdges = 0;int i, j;VerticesList = ne
12、w 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-146-2222template int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻
13、接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;146-146-2323template int Graphmtx:getNextNeighbor (int v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 & w != -1) for (int col = w+1; col numVertices; col+) if (Edge
14、vcol & Edgevcol maxWeight) return col; return -1;146-146-2424n邻接表是邻接矩阵的改进形式。为此需要把邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。邻接矩阵的各行分别组织为一个单链表。n在邻接表中,同一个顶点发出的边链接在同在邻接表中,同一个顶点发出的边链接在同一个边链表中,每一个链结点代表一条边一个边链表中,每一个链结点代表一条边(边结点),结点中有另一顶点的下标(边结点),结点中有另一顶点的下标 dest 和指针和指针 link。对于带权图,边结点中还要保。对于带权图,边结点中还要保存该边的权值存该边的
15、权值cost。n顶点表的第顶点表的第 i 个顶点中保存该顶点的数据,个顶点中保存该顶点的数据,以及它对应边链表的头指针以及它对应边链表的头指针adj。 邻接表邻接表 (Adjacency List)(Adjacency List)146-146-2525ABCDdata adjABCD0123dest linkdest link 130210无向图的邻接表无向图的邻接表n统计某顶点对应边链表中结点个数,可得该顶统计某顶点对应边链表中结点个数,可得该顶点的度。点的度。n某条边某条边(vi, vj)在邻接表中有两个边结点,分别在邻接表中有两个边结点,分别在第在第 i 个顶点和第个顶点和第 j 个顶
16、点对应的边链表中。个顶点对应的边链表中。146-146-2626data adjABC012dest linkdest link 邻接表邻接表 (出边表出边表)data adjABC012dest link逆邻接表逆邻接表 (入边表入边表)102 011有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABC146-146-2727BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 ( (带权图带权图) ) 的邻接表的邻接表n统计出边表中结点个数,得到该顶点的出度;统计出边表中结点个数,得到该顶点
17、的出度;n统计入边表中结点个数,得到该顶点的入度。统计入边表中结点个数,得到该顶点的入度。146-146-2828n在邻接表的边链表中,各个边结点的链入顺序在邻接表的边链表中,各个边结点的链入顺序任意,视边结点输入次序而定。任意,视边结点输入次序而定。n设图中有设图中有 n 个顶点,个顶点,e 条边,则用邻接表表示条边,则用邻接表表示无向图时,需要无向图时,需要 n 个顶点结点,个顶点结点,2e 个边结点;个边结点;用邻接表表示有向图时,若不考虑逆邻接表,用邻接表表示有向图时,若不考虑逆邻接表,只需只需 n 个顶点结点,个顶点结点,e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时
18、,可以节省大量的存储空时,可以节省大量的存储空间。此外,把同一个顶点的所有边链接在一个间。此外,把同一个顶点的所有边链接在一个单链表中,也使得图的操作更为便捷。单链表中,也使得图的操作更为便捷。 146-146-2929用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边结点的定义 int dest; /边的另一顶点位置 E cost; /边上的权值 Edge *link; /下一条边链指针 Edge () /构造函数 Edge (int num, E cost) /构造函数 : dest (num), weight (cost), link (NU
19、LL) bool operator != (Edge& R) const return dest != R.dest; /判边等否;146-146-3030template struct Vertex /顶点的定义 T data; /顶点的名字Edge *adj; /边链表的头指针;template class Graphlnk : public Graph /图的类定义friend istream& operator (istream& in, Graphlnk& G); /输入friend ostream& operator (ostream& out, Graphlnk& G); /输出
20、146-146-3131private: Vertex *NodeTable; /顶点表 (各边链表的头结点) int getVertexPos (const T vertx) /给出顶点vertex在图中的位置 for (int i = 0; i = 0 & i NumVertices) ? NodeTablei.data : 0; E getWeight (int v1, int v2); /取边(v1,v2)权值bool insertVertex (const T& vertex); bool removeVertex (int v); bool insertEdge (int v1,
21、int v2, E cost);bool removeEdge (int v1, int v2); int getFirstNeighbor (int v); int getNextNeighbor (int v, int w);146-146-3333template Graphlnk:Graphlnk (int sz) /构造函数:建立一个空的邻接表 maxVertices = sz; numVertices = 0; numEdges = 0; NodeTable = new VertexmaxVertices;/创建顶点表数组 if (NodeTable = NULL) cerr 存储
22、分配错!存储分配错! endl; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL;146-146-3434template Graphlnk:Graphlnk() /析构函数:删除一个邻接表 for (int i = 0; i numVertices; i+ ) Edge *p = NodeTablei.adj; while (p != NULL) NodeTablei.adj = p-link; delete p; p = NodeTablei.adj; delete NodeTable; /删除顶点表数组1
23、46-146-3535template int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为 v 的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) /顶点顶点v存在存在 Edge *p = NodeTablev.adj;/对应边链表第一个边结点if (p != NULL) return p-dest;/存在, 返回第一个邻接顶点 return -1;/第一个邻接顶点不存在146-146-3636template int Graphlnk:getNextNeighbor (int v, int w) /给出顶点v的邻接顶点
24、w的下一个邻接顶点的位置,/若没有下一个邻接顶点, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; while (p != NULL & p-dest != w) p = p-link; if (p != NULL & p-link != NULL) return p-link-dest; /返回下一个邻接顶点 return - -1; /下一邻接顶点不存在146-146-3737邻接多重表邻接多重表 (Adjacency Multilist)(Adjacency Multilist)n在邻接多重表中在邻接多重表中, 每一条边只有一个
25、边结点。每一条边只有一个边结点。为有关边的处理提供了方便。为有关边的处理提供了方便。n无向图的情形无向图的情形u边结点的结构边结点的结构n其中其中, mark 是记录是否处理过的标记是记录是否处理过的标记; vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接域是链接指针指针, 指向下一条依附顶点指向下一条依附顶点vertex1的边;的边;path2 是指向下一条依附顶点是指向下一条依附顶点vertex2的边链接指针。的边链接指针。 mark vertex1 vertex2 path1 path2146-146-3838n需要时还可设置一个存放与该边相关的权值
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新北京师范大学数据结构教学资料 第8章图精品课件 最新 北京师范大学 数据结构 教学 资料 精品 课件
限制150内