北京师范大学数据结构教学资料 第8章ppt课件

1、n图的根本概念图的根本概念n图的存储表示图的存储表示n图的遍历与连通性图的遍历与连通性 n最小生成树最小生成树n最短途径最短途径 n活动网络活动网络第八章第八章 图图图的根本概念图的根本概念n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的及顶点间的关系集合组成的一种数据构造：关系集合组成的一种数据构造：n Graph( V, E ) n其中其中 V = x | x 某个数据对象某个数据对象 n 是顶点的有穷非空集合；是顶点的有穷非空集合；n E = (x, y) | x, y V n或或 E = | x, y V & Path (x, y)n 是顶点之间关系的有穷集合，也

2、叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path (x, y)表示从表示从 x 到到 y 的一条的一条单向通路单向通路, 它是有方向的。它是有方向的。 n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x, y)是无序是无序的。的。n完全图完全图 假设有假设有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边, 那么此图为完全无向图。有那么此图为完全无向图。有 n 个顶点的个顶点的有向图有有向图有n(n-1) 条边条边, 那么此图为完全有向图。那么此图为完全有向图。000011

3、11222265433 n邻接顶点邻接顶点 假设假设 (u, v) 是是 E(G) 中的一条边，中的一条边，那么称那么称 u 与与 v 互为邻接顶点。互为邻接顶点。n子图子图 设有两个图设有两个图G(V, E) 和和G(V, E)。假设假设V V 且且EE, 那么称图那么称图G是图是图G的子的子图。图。n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数, 称之为权。称之为权。这种带权图叫做网络。这种带权图叫做网络。子图子图01230130123023n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的边的度是与它相关联的边的条数。记作的条数。记作TD(v)。在有向图中。在有向图中

4、, 顶点的度顶点的度等于该顶点的入度与出度之和。等于该顶点的入度与出度之和。n顶点顶点 v 的入度是以的入度是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度是以的出度是以 v 为始点的有为始点的有向边的条数向边的条数, 记作记作 OD(v)。n途径途径 在图在图 G(V, E) 中中, 假设从顶点假设从顶点 vi 出发出发, 沿一些边经过一些顶点沿一些边经过一些顶点 vp1, vp2, , vpm，到，到达顶点达顶点vj。那么称顶点序列。那么称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点为从顶点vi 到顶点到顶点 vj 的途径

5、。它经的途径。它经过的边过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应应是属于是属于E的边。的边。n途径长度途径长度 非带权图的途径长度是指此途径上非带权图的途径长度是指此途径上边的条数。带权图的途径长度是指途径上各边的条数。带权图的途径长度是指途径上各边的权之和。边的权之和。n简单途径简单途径 假设途径上各顶点假设途径上各顶点 v1, v2, ., vm 均均不不 相互反复相互反复, 那么称这样的途径为简单途径。那么称这样的途径为简单途径。n回路回路 假设途径上第一个顶点假设途径上第一个顶点 v1 与最后一个与最后一个顶点顶点vm 重合重合, 那么称这样的途径为回

6、路或环。那么称这样的途径为回路或环。012301230123n连通图与连通分量连通图与连通分量 在无向图中在无向图中, 假设从顶点假设从顶点v1到顶点到顶点v2有途径有途径, 那么称顶点那么称顶点v1与与v2是连通是连通的。假设图中恣意一对顶点都是连通的的。假设图中恣意一对顶点都是连通的, 那么那么称此图是连通图。非连通图的极大连通子图称此图是连通图。非连通图的极大连通子图叫做连通分量。叫做连通分量。n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中, 假设对假设对于每一对顶点于每一对顶点vi和和vj, 都存在一条从都存在一条从vi到到vj和从和从vj到到vi的途径的途径, 那么

7、称此图是强连通图。非强那么称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。连通图的极大强连通子图叫做强连通分量。n生成树生成树 一个连通图的生成树是其极小连通一个连通图的生成树是其极小连通子图，在子图，在 n 个顶点的情形下，有个顶点的情形下，有 n-1 条边。条边。图的笼统数据类型图的笼统数据类型class Graph /对象对象: 由一个顶点的非空集合和一个边集合构成由一个顶点的非空集合和一个边集合构成/每条边由一个顶点对来表示。每条边由一个顶点对来表示。public: Graph();/建立一个空的图建立一个空的图 void insertVertex (const T& ve

8、rtex); /插入一个顶点插入一个顶点vertex, 该顶点暂时没有入边该顶点暂时没有入边 void insertEdge (int v1, int v2, int weight); /在图中插入一条边在图中插入一条边(v1, v2, w) void removeVertex (int v); /在图中删除顶点在图中删除顶点v和一切关联到它的边和一切关联到它的边 void removeEdge (int v1, int v2); /在图中删去边在图中删去边(v1,v2) bool IsEmpty(); /假设图中没有顶点假设图中没有顶点, 那么前往那么前往true, 否那么前往否那么前往fa

9、lse T getWeight (int v1, int v2); /函数前往边函数前往边 (v1,v2) 的权值的权值 int getFirstNeighbor (int v); /给出顶点给出顶点 v 第一个邻接顶点的位置第一个邻接顶点的位置 int getNextNeighbor (int v, int w); /给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶点的下一个邻接顶点;图的存储表示图的存储表示n图的模板基类图的模板基类 在模板类定义中的数据类型在模板类定义中的数据类型参数表参数表 中，中，T是顶点数据的是顶点数据的类型，类型，E是边上所附数据的类型。是边上所

10、附数据的类型。n这个模板基类是按照最复杂的情况即带权这个模板基类是按照最复杂的情况即带权无向图来定义的，假设需求运用非带权图，无向图来定义的，假设需求运用非带权图，可将数据类型参数表可将数据类型参数表 改为改为 。n假设运用的是有向图，也可以对程序做相应假设运用的是有向图，也可以对程序做相应的改动。的改动。 图的模板基类图的模板基类 const int maxWeight = ; /无穷大的值无穷大的值(=)const int DefaultVertices = 30; /最大顶点数最大顶点数(=n)template class Graph /图的类定义图的类定义protected: int

11、maxVertices; /图中最大顶点数图中最大顶点数 int numEdges; /当前边数当前边数 int numVertices; /当前顶点数当前顶点数 int getVertexPos (T vertex); /给出顶点给出顶点vertex在图中位置在图中位置public: Graph (int sz = DefaultVertices); /构造函数 Graph();/析构函数 bool GraphEmpty () const /判图空否 return numEdges = 0; int NumberOfVertices () return numVertices; /前往当前顶

12、点数 int NumberOfEdges () return numEdges; /前往当前边数virtual T getValue (int i);/取顶点 i 的值 virtual E getWeight (int v1, int v2); /取边上权值 virtual int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点virtual int getNextNeighbor (int v, int w); /取邻接顶点取邻接顶点 w 的下一邻接顶点的下一邻接顶点 virtual bool insertVertex (const T vertex);

13、/插入一个顶点插入一个顶点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);邻接矩阵邻接矩阵 (Adjacency Matrix) (Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶在图的邻接矩阵表示中，有

14、一个记录各个顶点信息的顶点表，还有一个表示各个顶点之点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。间关系的邻接矩阵。n设图设图 A = (V, E) 是一个有是一个有 n 个顶点的图个顶点的图, 图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn，定义：，定义： , ),( , , .否否则则或或者者如如果果01EdgeAEjiEjijin无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵能够是不对称的。有向图的邻接矩阵能够是不对称的。0101101001011010A.edge0123012000101010A.edgen在有向图中在有向图中,

15、 统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的出度，统计第的出度，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的入的入度。度。n在无向图中在无向图中, 统计第统计第 i 行行 (列列) 1 的个数可得顶的个数可得顶点点i 的度。的度。网络的邻接矩阵网络的邻接矩阵jiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.edge068053290410A.edge863129542031用邻接矩阵表示的图的类定义用邻接矩阵表示的图的类定义template class Graphmtx : public Graph f

16、riend istream& operator ( istream& in, Graphmtx& G);/输入输入friend ostream& operator (ostream& out, Graphmtx& G);/输出输出private: T *VerticesList; /顶点表顶点表 E *Edge;/邻接矩阵邻接矩阵int getVertexPos (T vertex) /给出顶点给出顶点vertex在图中的位置在图中的位置 for (int i = 0; i = 0 & i = numVertices ? VerticesListi : NULL; E getWeight (i

17、nt v1, int v2) /取边(v1,v2)上权值 return v1 != -1 & v2 != -1 ? Edgev1v2 : 0; int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点 int getNextNeighbor (int v, int w); /取取 v 的邻接顶点的邻接顶点 w 的下一邻接顶点的下一邻接顶点 bool insertVertex (const T vertex); /插入顶点插入顶点vertex bool insertEdge (int v1, int v2, E cost); /插入边插入边(v1, v2),权值

18、为权值为cost bool removeVertex (int v); /删去顶点删去顶点 v 和一切与它相关联的边和一切与它相关联的边 bool removeEdge (int v1, int v2); /在图中删去边在图中删去边(v1,v2);template Graphmtx:Graphmtx (int sz) /构造函数构造函数 maxVertices = sz; numVertices = 0; numEdges = 0;int i, j;VerticesList = new TmaxVertices; /创建顶点表创建顶点表 Edge = (int *) new int *maxV

19、ertices;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; template int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为给出顶点位置为v的第一个邻接顶点的位置的第一个邻接顶点的位置, /假设找不到假设找不到, 那么函数前往那么函数前往-1

20、if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;template int Graphmtx:getNextNeighbor (int v, int w) /给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶点的下一个邻接顶点 if (v != -1 & w != -1) for (int col = w+1; col numVertices; col+) if (Edgevcol & Edgevcol ma

21、xWeight) return col; return -1;n邻接表是邻接矩阵的改良方式。为此需求把邻接表是邻接矩阵的改良方式。为此需求把邻接矩阵的各行分别组织为一个单链表。邻接矩阵的各行分别组织为一个单链表。n在邻接表中，同一个顶点发出的边链接在同在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边一个边链表中，每一个链结点代表一条边边结点，结点中有另一顶点的下标边结点，结点中有另一顶点的下标 dest 和指针和指针 link。对于带权图，边结点中还要保。对于带权图，边结点中还要保管该边的权值管该边的权值cost。n顶点表的第顶点表的第 i 个顶点中保管该顶点的数据，

22、个顶点中保管该顶点的数据，以及它对应边链表的头指针以及它对应边链表的头指针adj。 邻接表邻接表 (Adjacency List) (Adjacency List)ABCDdata adjABCD0123dest linkdest link 130210无向图的邻接表无向图的邻接表n统计某顶点对应边链表中结点个数，可得该顶统计某顶点对应边链表中结点个数，可得该顶点的度。点的度。n某条边某条边(vi, vj)在邻接表中有两个边结点，分别在邻接表中有两个边结点，分别在第在第 i 个顶点和第个顶点和第 j 个顶点对应的边链表中。个顶点对应的边链表中。data adjABC012dest linkde

23、st link 邻接表邻接表 (出边表出边表)data adjABC012dest link逆邻接表逆邻接表 (入边表入边表)102 011有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABCBACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 ( (带权图带权图) ) 的邻接表的邻接表n统计出边表中结点个数，得到该顶点的出度；统计出边表中结点个数，得到该顶点的出度；n统计入边表中结点个数，得到该顶点的入度。统计入边表中结点个数，得到该顶点的入度。n在邻接表的边链表中，各个边结点的链入顺序在邻接

24、表的边链表中，各个边结点的链入顺序恣意，视边结点输入次序而定。恣意，视边结点输入次序而定。n设图中有设图中有 n 个顶点，个顶点，e 条边，那么用邻接表表条边，那么用邻接表表示无向图时，需求示无向图时，需求 n 个顶点结点，个顶点结点，2e 个边结个边结点；用邻接表表示有向图时，假设不思索逆邻点；用邻接表表示有向图时，假设不思索逆邻接表，只需接表，只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时，可以节省大量的存储空时，可以节省大量的存储空间。此外，把同一个顶点的一切边链接在一个间。此外，把同一个顶点的一切边链接在一个单链表中，也使得图的操作更为

25、便利。单链表中，也使得图的操作更为便利。 用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边结点的定义边结点的定义 int dest; /边的另一顶点位置边的另一顶点位置 E cost; /边上的权值边上的权值 Edge *link; /下一条边链指针下一条边链指针 Edge () /构造函数构造函数 Edge (int num, E cost) /构造函数构造函数 : dest (num), weight (cost), link (NULL) bool operator != (Edge& R) const return dest != R.d

26、est; /判边等否判边等否;template 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); /输出输出private: Vertex *NodeTable; /顶点表顶点表 (

27、各边链表的头结点各边链表的头结点) 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, int v2, E cost);bool rem

28、oveEdge (int v1, int v2); int getFirstNeighbor (int v); int getNextNeighbor (int v, int w);template Graphlnk:Graphlnk (int sz) /构造函数：建立一个空的邻接表构造函数：建立一个空的邻接表 maxVertices = sz; numVertices = 0; numEdges = 0; NodeTable = new VertexmaxVertices;/创建顶点表数组创建顶点表数组 if (NodeTable = NULL) cerr 存储分配错！存储分配错！ endl

29、; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL;template 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; /删除顶点表数组删除顶点表数组template

30、int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为给出顶点位置为 v 的第一个邻接顶点的位置的第一个邻接顶点的位置, /假设找不到假设找不到, 那么函数前往那么函数前往-1 if (v != -1) /顶点顶点v存在存在 Edge *p = NodeTablev.adj;/对应边链表第一个边结点对应边链表第一个边结点if (p != NULL) return p-dest;/存在存在, 前往第一个邻接顶点前往第一个邻接顶点 return -1;/第一个邻接顶点不存在第一个邻接顶点不存在template int Graphlnk:getNextNeigh

31、bor (int v, int w) /给出顶点给出顶点v的邻接顶点的邻接顶点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; /下一邻接顶点不存在下一邻接顶点不存在邻

32、接多重表邻接多重表 (Adjacency Multilist) (Adjacency Multilist)n在邻接多重表中在邻接多重表中, 每一条边只需一个边结点。每一条边只需一个边结点。为有关边的处置提供了方便。为有关边的处置提供了方便。n无向图的情形无向图的情形n边结点的构造边结点的构造n其中其中, mark 是记录能否处置过的标志是记录能否处置过的标志; vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接域是链接指针指针, 指向下一条依靠顶点指向下一条依靠顶点vertex1的边；的边；path2 是指向下一条依靠顶点是指向下一条依靠顶点vertex2的

33、边链接的边链接指针。指针。 mark vertex1 vertex2 path1 path2n需求时还可设置一个存放与该边相关的权值的需求时还可设置一个存放与该边相关的权值的域域 cost。n顶点结点的构造顶点结点的构造n顶点信息的结点表以顺序表方式组织顶点信息的结点表以顺序表方式组织, 每一个顶每一个顶点结点有两个数据成员：其中，点结点有两个数据成员：其中，data 存放与该存放与该顶点相关的信息，顶点相关的信息，Firstout 是指示第一条依靠该是指示第一条依靠该顶点的边的指针。顶点的边的指针。n在邻接多重表中在邻接多重表中, 一切依靠同一个顶点的边都一切依靠同一个顶点的边都链接在同一个

34、单链表中。链接在同一个单链表中。 data Firstoutmark vtx1 vtx2 path1 path2 0 10 21 3e1e2e3data FoutABCD0123e1e2e3ABCDn从顶点从顶点 i 出发出发, 可以循链找到一切依靠于该顶可以循链找到一切依靠于该顶点的边，也可以找到它的一切邻接顶点。点的边，也可以找到它的一切邻接顶点。邻接多重表的构造邻接多重表的构造n有向图的情形有向图的情形n在用邻接表表示有向图时在用邻接表表示有向图时, 有时需求同时运用有时需求同时运用邻接表和逆邻接表。用有向图的邻接多重表邻接表和逆邻接表。用有向图的邻接多重表(十字链表十字链表)可把两个表

35、结合起来表示。可把两个表结合起来表示。n边结点的构造边结点的构造n其中，其中，mark是处置标志；是处置标志；vertex1和和vertex2指指明该有向边始顶点和终顶点的位置。明该有向边始顶点和终顶点的位置。path1是是指向始顶点与该边一样的下一条边的指针；指向始顶点与该边一样的下一条边的指针；path2是指向终顶点与该边一样的下一条边的是指向终顶点与该边一样的下一条边的指针。需求时还可有权值域指针。需求时还可有权值域cost。 mark vertex1 vertex2 path1 path2u顶点结点的构造顶点结点的构造u每个顶点有一个结点，它相当于出边表和入每个顶点有一个结点，它相当于

36、出边表和入边表的表头结点：其中，数据成员边表的表头结点：其中，数据成员data存放存放与该顶点相关的信息，指针与该顶点相关的信息，指针Firstout 指示以指示以该顶点为始顶点的出边表的第一条边，该顶点为始顶点的出边表的第一条边，Firstin 指示以该顶点为终顶点的入边表的指示以该顶点为终顶点的入边表的第一条边。第一条边。 data Firstin Firstoutmark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表的构造邻接多重表的构造画

37、出在以下图所表示的有向图中画出在以下图所表示的有向图中删除顶点删除顶点V3V3后的十字链表存储构造后的十字链表存储构造图。图。图的遍历与连通性图的遍历与连通性n从已给的连通图中某一顶点出发，沿着一些边从已给的连通图中某一顶点出发，沿着一些边访遍图中一切的顶点，且使每个顶点仅被访问访遍图中一切的顶点，且使每个顶点仅被访问一次，就叫做图的遍历一次，就叫做图的遍历 (Graph Traversal)。n图中能够存在回路，且图的任一顶点都能够与图中能够存在回路，且图的任一顶点都能够与其它顶点相通，在访问完某个顶点之后能够会其它顶点相通，在访问完某个顶点之后能够会沿着某些边又回到了曾经访问过的顶点。沿着

38、某些边又回到了曾经访问过的顶点。n为了防止反复访问，可设置一个标志顶点能否为了防止反复访问，可设置一个标志顶点能否被访问过的辅助数组被访问过的辅助数组 visited 。n辅助数组辅助数组visited 的初始形状为的初始形状为 0, 在图的遍在图的遍历过程中历过程中, 一旦某一个顶点一旦某一个顶点 i 被访问被访问, 就立刻就立刻让让visitedi为为 1, 防止它被多次访问。防止它被多次访问。n图的遍历的分类图的遍历的分类:n深度优先搜索深度优先搜索 n DFS (Depth First Search)n广度优先搜索广度优先搜索 n BFS (Breadth First Search)深

39、度优先搜索深度优先搜索DFS (Depth First Search)DFS (Depth First Search)n深度优先搜索的例如深度优先搜索的例如ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树nDFS 在访问图中某一同始顶点在访问图中某一同始顶点 v 后后, 由由 v 出发出发, 访问它的任一邻接顶点访问它的任一邻接顶点 w1; 再从再从 w1 出发出发, 访问访问与与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2; 然后再然后再从从 w2 出发出发, 进展类似的访问进展类

40、似的访问, 如此进展下去如此进展下去, 直至到达一切的邻接顶点都被访问过的顶点直至到达一切的邻接顶点都被访问过的顶点 u 为止。接着为止。接着, 退回一步退回一步, 退到前一次刚访问过退到前一次刚访问过的顶点的顶点, 看能否还有其它没有被访问的邻接顶看能否还有其它没有被访问的邻接顶点。假设有点。假设有, 那么访问此顶点那么访问此顶点, 之后再从此顶点之后再从此顶点出发出发, 进展与前述类似的访问进展与前述类似的访问; 假设没有假设没有, 就再就再退回一步进展搜索。反复上述过程退回一步进展搜索。反复上述过程, 直到连通直到连通图中一切顶点都被访问过为止。图中一切顶点都被访问过为止。图的深度优先搜

41、索算法图的深度优先搜索算法template void DFS (Graph& G, const T& v) /从顶点从顶点v出发对图出发对图G进展深度优先遍历的主过程进展深度优先遍历的主过程 int i, loc, n = G.NumberOfVertices(); /顶点个数顶点个数 bool *visited = new booln; /创建辅助数组创建辅助数组 for (i = 0; i n; i+) visited i = false; /辅助数组辅助数组visited初始化初始化loc = G.getVertexPos(v); DFS (G, loc, visited); /从顶点从

42、顶点0开场深度优先搜索开场深度优先搜索 delete visited; /释放释放visitedtemplatevoid DFS (Graph& G, int v, bool visited) cout G.getValue(v) ; /访问顶点访问顶点v visitedv = true; /作访问标志作访问标志 int w = G.getFirstNeighbor (v); /第一个邻接顶点第一个邻接顶点 while (w != -1) /假设邻接顶点假设邻接顶点w存在存在 if ( !visitedw ) DFS(G, w, visited); /假设假设w未访问过未访问过, 递归访问顶点

43、递归访问顶点w w = G.getNextNeighbor (v, w); /下一个邻接顶点下一个邻接顶点 广度优先搜索广度优先搜索BFS (Breadth First Search)BFS (Breadth First Search)n广度优先搜索的例如广度优先搜索的例如广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树ACDEGBFIHACDEGBFH123456789123456789InBFS在访问了起始顶点在访问了起始顶点 v 之后之后, 由由 v 出发出发, 依依次访问次访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1, w2, , wt, 然后再顺

44、序访问然后再顺序访问 w1, w2, , wt 的的一切还未被访问过的邻接顶点。再从这些访一切还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的一切还未被问过的顶点出发，再访问它们的一切还未被访问过的邻接顶点，访问过的邻接顶点， 如此做下去，直到图如此做下去，直到图中一切顶点都被访问到为止。中一切顶点都被访问到为止。n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程, 每向前每向前走一步能够访问一批顶点走一步能够访问一批顶点, 不像深度优先搜索不像深度优先搜索那样有往回退的情况。因此那样有往回退的情况。因此, 广度优先搜索不广度优先搜索不是一个递归的过程。是一个递归

45、的过程。n为了实现逐层访问为了实现逐层访问, 算法中运用了一个队列算法中运用了一个队列, 以以记忆正在访问的这一层和上一层的顶点记忆正在访问的这一层和上一层的顶点, 以便以便于向下一层访问。于向下一层访问。n为防止反复访问为防止反复访问, 需求一个辅助数组需求一个辅助数组 visited ，给被访问过的顶点加标志。给被访问过的顶点加标志。ntemplate nvoid BFS (Graph& G, const T& v) n int i, w, n = G.NumberOfVertices(); n /图中顶点个数图中顶点个数图的广度优先搜索算法图的广度优先搜索算法 bool *visited

46、 = new booln; for (i = 0; i n; i+) visitedi = false; int loc = G.getVertexPos (v);/取顶点号 cout G.getValue (loc) ; /访问顶点v visitedloc = true; /做已访问标志 Queue Q; Q.EnQueue (loc); /顶点进队列, 实现分层访问 while (!Q.IsEmpty() ) /循环, 访问一切结点 Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一个邻接顶点 while (w != -1) /假设邻接顶点

47、w存在 if (!visitedw) /假设未访问过 cout G.getValue (w) ;/访问访问 visitedw = true; Q.EnQueue (w); /顶点顶点w进队列进队列 w = G.getNextNeighbor (loc, w); /找顶点找顶点loc的下一个邻接顶点的下一个邻接顶点 /外层循环，判队列空否外层循环，判队列空否 delete visited;连通分量连通分量 (Connected component) (Connected component)n当无向图为非连通图时，从图中某一顶点出当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广

48、度优先搜索发，利用深度优先搜索算法或广度优先搜索算法不能够遍历到图中的一切顶点，只能访算法不能够遍历到图中的一切顶点，只能访问到该顶点所在最大连通子图连通分量问到该顶点所在最大连通子图连通分量的一切顶点。的一切顶点。n假设从无向图每一连通分量中的一个顶点出假设从无向图每一连通分量中的一个顶点出发进展遍历发进展遍历, 可求得无向图的一切连通分量。可求得无向图的一切连通分量。n例如，对于非连通的无向图，一切连通分量例如，对于非连通的无向图，一切连通分量的生成树组成了非连通图的生成森林。的生成树组成了非连通图的生成森林。ACDEBFGOIHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图

49、的连通分量确定连通分量的算法确定连通分量的算法template void Components (Graph& G) /经过经过DFS，找出无向图的一切连通分量，找出无向图的一切连通分量 int i, n = G.NumberOfVertices(); /图中顶点个数图中顶点个数 bool *visited = new booln; /访问标志访问标志数组数组 for (i = 0; i n; i+) visitedi = false; for (i = 0; i n; i+) /扫描一切顶点扫描一切顶点 if (!visitedi) /假设没有访问假设没有访问过过 DFS (G, i, vi

50、sited);/访问访问 OutputNewComponent(); /输出连通分量输出连通分量 delete visited; 例：以深度优先搜索方法从顶点例：以深度优先搜索方法从顶点 出发遍历图出发遍历图, 建建立深度优先生成森林。立深度优先生成森林。AABCDEFGABDECFGtemplate void DFS_Forest (Graph& G, Tree & F) TreeNode * rt, * subT; int n = G.NumberOfVertices(); static int *visited = new intn; /访问数组访问数组 for (int i = 0;

51、i n; i+) visited i = 0; for (i = 0; i n; i+) /遍历一切顶点遍历一切顶点 if (!visitedi) /顶点顶点 i 未访问过未访问过 if (F.IsEmpty() /F原为空生成森林原为空生成森林,建根建根 subT = rt = F.BuildRoot(G.GetValue(i); /顶点顶点 i 的值成为根的值成为根 rt 的值的值 else subT = F.InsertRightSibling (subT, G.GetValue(i); /顶点顶点 i 的值成为的值成为 subT 右兄弟的值右兄弟的值 DFS_Tree (G, F, s

52、ubT, i, visited); /从顶点从顶点 i 出发深度优先遍历出发深度优先遍历, 建子树建子树 template void DFS_Tree (Graph& G, Tree&F, TreeNode * rt, int v, int visited ) TreeNode * p; visitedv = 1; /顶点v作访问过标志 int w = G.GetFirstNeighbor (v); /取顶点v的第一个邻接顶点w int FirstChild = 1; /第一个未访问子女应是v的左子女 while ( w != -1 ) /邻接顶点w存在 if (! visited w) /w

53、未访问过, 将成为v的子女 if (FirstChild) p = F.InsertLeftChild (rt, G.GetValue(w); /p插入为rt的左子女 FirstChild = 0; /建右兄弟 else p = F.InsertRightSibling (p, G.GetValue(w); /p插入为 p 的左子女 DFS_Tree (G, F, p, w, visited); /递归建立 w 的以 p 为根的子树 /邻接顶点 w 处置完 w = G.GetNextNeighbor (v, w); /取 v 的下一个邻接顶点 w /回到 while 判邻接顶点 w 存在; 重

54、连通分量重连通分量 (Biconnected Component)(Biconnected Component)n在无向连通图在无向连通图G中中, 当且仅当删去当且仅当删去G中的顶点中的顶点v及一切依靠于及一切依靠于v的一切边后的一切边后, 可将图分割成两个可将图分割成两个或两个以上的连通分量，那么称顶点或两个以上的连通分量，那么称顶点v为关节为关节点。点。n没有关节点的连通图叫做重连通图。没有关节点的连通图叫做重连通图。n在重连通图上在重连通图上, 任何一对顶点之间至少存在有任何一对顶点之间至少存在有两条途径两条途径, 在删去某个顶点及与该顶点相关联在删去某个顶点及与该顶点相关联的边时的边时

55、, 也不破坏图的连通性。也不破坏图的连通性。n一个连通图一个连通图G假设不是重连通图，那么它可以假设不是重连通图，那么它可以包括几个重连通分量。包括几个重连通分量。n在一个无向连通图在一个无向连通图G中中, 重连通分量可以利用重连通分量可以利用深度优先生成树找到。深度优先生成树找到。n在图中各顶点旁标明的深度优先数在图中各顶点旁标明的深度优先数, 给出进展给出进展深度优先搜索时各顶点访问的次序。深度优先搜索时各顶点访问的次序。n深度优先生成树的根是关节点的充要条件是它深度优先生成树的根是关节点的充要条件是它至少有两个子女。至少有两个子女。n其它顶点其它顶点 u 是关节点的充要条件是它至少有一是

56、关节点的充要条件是它至少有一个子女个子女 w, 从从 w 出发出发, 不能经过不能经过 w、w 的子孙及的子孙及一条回边所组成的途径到达一条回边所组成的途径到达 u 的祖先。的祖先。ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有两根有两 个子女个子女最小生成树最小生成树 ( minimum cost spanning tree )( minimum cost spanning tree )n运用不同的遍历图的方法，可以得到不同的生运用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也能够得到不同的成树；从不同的顶点出发，也能够得到不同的生成树

57、。生成树。n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1条边。条边。n构造最小生成树构造最小生成树 假设有一个网络，用以表示假设有一个网络，用以表示 n 个城市之间架设通讯线路，边上的权值代表个城市之间架设通讯线路，边上的权值代表架设通讯线路的本钱。如何架设才干使线路架架设通讯线路的本钱。如何架设才干使线路架设的本钱到达最小？设的本钱到达最小？n构造最小生成树的准那么构造最小生成树的准那么n必需运用且仅运用该网络中的必需运用且仅运用该网络中的 n-1 条边来条边来结合网络中的结合网络中的 n 个顶点；个顶点；n不能运用

58、产生回路的边；不能运用产生回路的边；n各边上的权值的总和到达最小。各边上的权值的总和到达最小。北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉34764158312419253822221931394450北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉76241922221931北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉34764158312419253822221931394450克鲁斯卡尔克鲁斯卡尔 (Kruskal) (Kruskal) 算法算法n克鲁斯卡尔算法的根本思想：克鲁斯卡尔算法的根本思想：n设

59、有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N = V, E , 最初先构造一个只需最初先构造一个只需 n 个顶点个顶点, 没有边的没有边的非连通图非连通图 T = V, , 图中每个顶点自成一个图中每个顶点自成一个连通分量。当在连通分量。当在 E 中选到一条具有最小权值中选到一条具有最小权值的边时的边时, 假设该边的两个顶点落在不同的连通假设该边的两个顶点落在不同的连通分量上，那么将此边参与到分量上，那么将此边参与到 T 中中; 否那么将此否那么将此边舍去，重新选择一条权值最小的边。如此反边舍去，重新选择一条权值最小的边。如此反复下去复下去, 直到一切顶点在同一个连通分量上为直

60、到一切顶点在同一个连通分量上为止。止。KruskalKruskal算法的伪代码描画算法的伪代码描画 T = ;/T是最小生成树的边集合是最小生成树的边集合 /E是带权无向图的边集合是带权无向图的边集合while ( T 包含的边少于包含的边少于n-1 & E不空不空) 从从 E 中选一条具有最小代价的边中选一条具有最小代价的边 (v, w); 从从 E 中删去中删去(v, w); 假设假设(v, w)加到加到 T 中后不会产生回路中后不会产生回路, 那么将那么将 (v, w)参与参与T; 否那么放弃否那么放弃(v, w);if ( T 中包含的边少于中包含的边少于n-1条条) cout 不是最