1、图的基本概念 2、图的存储结构 3、图的遍历与连通性

Presentation on theme: "1、图的基本概念 2、图的存储结构 3、图的遍历与连通性"— Presentation transcript:

1 1、图的基本概念 2、图的存储结构 3、图的遍历与连通性
十五、图 1、图的基本概念 2、图的存储结构 3、图的遍历与连通性

2 4、图的遍历及其应用 深度优先遍历

3 广度优先遍历 广度优先遍历的基本思想

4 利用深度优先遍历算法或广度优先遍历算法可以求得非连通图的 连通分量。
连通性问题 利用深度优先遍历算法或广度优先遍历算法可以求得非连通图的 连通分量。 H K A B C D E I L M N J O F G A K H B C D E I L M N F G J O

5 连通性问题(续) 存储映象图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J K
1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J K L M N O 4 3 2 1 ∧ 5 ∧ ∧ ∧ 6 5 ∧ 6 4 1 ∧ 5 4 ∧ 9 8 ∧ 9 7 ∧ 8 7 ∧ 13 12 11 ∧ 14 10 ∧ 14 10 ∧ 10 ∧ 12 1 ∧

6 连通分量算法 void Graph∷Component( ) { visited = new int [grahsize]; // 初始化，所有的顶点都没有访问 for ( int i = 0; i<graphsize; i + +) visited[i] = 0; for ( i = 0; i<graphsize; i + +) if (! visited[i]) { visited[i] = 1; DFSearch( i ); }

7 在有向图中，任二个顶点间存在有向路径，则称为强连通图。 有向图的极大强连通子图称为强连通分量。 例：强连通分量 A、B、C D、F、G E
强连通分量的定义 在有向图中，任二个顶点间存在有向路径，则称为强连通图。 有向图的极大强连通子图称为强连通分量。 例：强连通分量 A、B、C D、F、G E A C B E D F G

8 拓扑排序 AOV网(Activity On Vertices) 顶点表示活动，顶点间的有向边表示<vi, vj>表示活动vi应先于活动vj进行。 课程编号 课程名称 先修课程 C 程序设计基础 无 C 离散数学 C1 C 数据结构 C1、C2 C 汇编语言 C1 C 计算机组成 C3、C4 C 计算机原理 C11 C 编译原理 C5、C3 C 操作系统 C3、C6 C 高等数学 无 C 线性代数 C9 C 普通物理 C9 C 数值分析 C9、C10、C1

9 对AOV网构造它的拓扑有序序列，使各个顶点排列成一个线性有 序序列，且使网络中存在的前驱和后继关系都能得到满足，这种 运算叫拓扑排序。
拓扑排序(续) 对AOV网构造它的拓扑有序序列，使各个顶点排列成一个线性有 序序列，且使网络中存在的前驱和后继关系都能得到满足，这种 运算叫拓扑排序。 现有 两个拓扑排序序列： C1、C2、C3、C4、C5、C7、C9、C10、C11、C6、C12、C8 C9、C10、C11、C6、C1、C12、C4、C2、C3、C5、C7、C8 C4 C5 C2 C1 C7 C3 C12 C9 C10 C8 C6 C11

10 算法思想：⑴在有向图中选择一个没有前驱的顶点且输出之。 ⑵从图中删除该顶点及所有以它为尾的弧。
拓扑排序算法 算法思想：⑴在有向图中选择一个没有前驱的顶点且输出之。 ⑵从图中删除该顶点及所有以它为尾的弧。 重复上述两步，直至全部顶点输出，或者当前图中不存在无 前驱的顶点为止。 data 入度 v1 v2 V1 V2 2 ∧ V3 1 V4 V5 3 V6 4 3 2 ∧ v4 v3 5 2 ∧ 5 ∧ v6 v5 5 4 ∧

11 拓扑排序算法(续) void Graph∷TopologicalSort( ) {
int top = -1; int num = 0; // 入度为零顶点栈初始化 for (int i = 0; i<n; i + +) if ( Nodetable [i] .indegree = = 0) {Nodetable [i] .indegree = top; top = i; } // 构造入度为零的栈 while (!( top = = -1))&&(num<graphsize) if ( num<graphsize) { cout << “Network has a cycle”<<endl; return;} else int j = top; top = Nodetable [top] .indegree ; // “删除入度为零的顶点” cout << j <<endl; num + +; // 输出该顶点，计数器加1 p = Nodetable [j] .firstarc; while (!( p = =Null) ) // “删除有关的弧” int k = p->adjvex; if ( - - Nodetable [k] .indegree = = 0) // 入度减1，新的入度为零 {Nodetable [k] .indegree = top; top = k;} // 的顶点进栈 p = p->nextarc; }} }

12 入度为零的顶点栈 入度为零的顶点栈的变化图 初始化 top = -1 top=0 top=1 top=2 top=3 top=5
v6、v1、v3、v2、v4、v5 2 1 3 -1 2 1 3 -1 2 1 -1 1 3 2 -1 3 1 -1 3 1

13 最短路径 从单源点到其余各顶点的最短路径 sVertex表示路径起点， eVertex表示路径终点，PathInfo表示待选 择的路径信息。 最短路径算法思想： ⑴生成第一个路径信息，startV=sVertex， endV=sVertex ，代价为 0，并插入优先队列。若sVertex就是指定的终点，过程结束。否则， ⑵从endV出发，求出endV所有的邻接点，建立从startV开始的与 与每个顶点的PathInfo，已输出的顶点除外，并输入优先队列； ⑶从优先队列中删除一个对象，若endV=eVertex ，过程结束。否 则，转⑵。 说明： 每一个生成的对象是迭代而成的，包含了以前的信息； 删除的对象的endV存放于专门的数组，以备检查是否为eVertex， 或已经找到从sVertex出发的最短路径的顶点。

14 最短路径的例 求图G中顶点A到D的最短路径 最短路径为 A、B、D，代价为12。 输出表L：A 代价：0 4 4 2 4 6 6 6 12
E A B 2 4 6 6 6 12 10 8 12 F D C 20 14 A至A A至B 4 A至E 4 A至C 12

15 输出表L：A、B、E 代价：A－>B 4, A－>E 4
最短路径的例(续) 输出表L：A、B 代价：A－>B 4 输出表L：A、B、E 代价：A－>B 4, A－>E 4 输出表L：A、B、E、C 代价：A－>B 4, A－>E 4 A－>B －>C 10 A至C已有最短路径，优先队列中的A－>C 舍去 输出表L：A、B、E、C、D 代价：A－>B 4, A－>E 4 A－>B －>D 12 A至E 4 A至C 12 B至C 10 B至D 12 B至C 10 A至C 12 B至D 12 E至D 14 A至C 12 B至D 12 E至D 14 C至D 24 B至D 12 E至D 14 C至D 24

16 所有顶点间的最短路径 方法一：对每个顶点作为源点，调用上述算法。 方法二：Floyd算法 基本思想：用邻接矩阵A(k)存放带权有向图，其元素A(k)[i][j](i≠j) 表示顶点vi到顶点vj的有向路径长度，k表示运算步骤。 初始时，任意两个顶点间若有有向边，则以该有向边的权值作为 它们间的最短路径长；否则用∞作为它们间的最短路径长。 因此， A(-1) = edge。 此后，每次在顶点vi和顶点vj插入标号不超过k的顶点vk，比较 A(k－1)[i][j]和顶点vi到顶点vk－1的当前最短路径与顶点vk－1到顶点vj 的当前最短路径之和的大小，若A(k－1)[i][j]仍然小保持不变，反之 改为插入顶点vk－1的新的路径，即有 A(k)[i][j] = min{A(k－1)[i][j]， A(k－1)[i][k] + A(k－1)[k][j]} 其中k = 0，1，2，· · ·，n－1。 当k = n－1时， A(n－1)[i][j] 即为顶点vi到顶点vj的最短路径。

17 用Floyd算法计算图G所有顶点对间的最短路径
Edge = 6 1 ∞ 4 9 2 3 5 8 6 2 3 8 2 9 3 5 4 1 1 A(－1) A(0) A(1) A(2) A(3) 1 ∞ 4 10 3 9 2 12 11 8 5 7 6 Path(－1) Path(0) Path(1) Path(2) Path(3)

18 Floyd算法 void Graph∷AllLengths(int n) {
for ( int i = 0; i < graphsize; i + +) for ( int j = 0; j < graphsize; j + +) { // 矩阵A和Path的初始化 A[i][j] = Edge[i][j]; if ( i<>j && A[i][j] <MAXMUM) Path[i][j] = i; // 有有向边，赋j前 else // 一顶点号 i Path[i][j] = 0; // 没有有向边 } for ( int k = 0; k < graphsize; k + +) // 产生A(k)和Path(k) for ( i = 0; i < graphsize; i + +) for ( j = 0; j < graphsize; j + +) if (A[i][k] + A[k][j] < A[i][j] ) // 找到新的路径 A[i][j] = A[i][k] + A[k][j] ; // 修改路径长 Path [i][j] = Path[k][j] ; // 修改路径，绕过k到j

19 对图中任一对顶点vi和vj ，当且仅当从vi到vj有一条有向路径时， 称vj 自vi可及。
可及性 可及的定义 对图中任一对顶点vi和vj ，当且仅当从vi到vj有一条有向路径时， 称vj 自vi可及。 邻接矩阵A = 可及矩阵：R是一个n×n的矩阵，且满足 1，当vi到vj至少存在一条非零长度的路径，i≠j R[i][j] = 0，当vi到vj不存在一条非零长度的路径，i≠j 1， i＝j 1 1 2 3

20 可及矩阵的计算 邻接矩阵A，以及A2、A3、· · ·、An的含义 对A[i][j]表示vi到vj存在长度为1的路径。 A2 [i][j]表示vi到vj存在长度为2的路径，因为 A2 [i][j] = A[i][1] A[1][j] + A[i][2] A[2][j] + · · · + A[i][n] A[n][j] 当且仅当A[i][k] 与A[k][j]均不为零时， A[i][k] A[k][j]才不等于零， 而A[i][k] A[k][j]不等于零意味着vi到vj间存在一条长度为2的路径。 假设n = m时命题成立，现证n = m+1时，命题亦成立。 首先， Am+1 = Am ×A Am+1[i][j] = Am[i][1] A[1][j] + Am[i][2] A[2][j] + · · · + Am[i][n] A[n][j] 当且仅当Am[i][k] 与A[k][j]均不为零时，Am[i][k] A[k][j]才不为零， 而Am[i][k] A[k][j]不为零，表示vi到vj间存在一条通过vk长度为m+1 的路径。 R = I + A + A2 + A3 + · · · + An R = I + A ∨ A2 ∨ A3 ∨ · · · ∨ An

21 可及矩阵的例 A = A2 = A3 = A4 = I = R = 1 1 1 1 1 1 2

22 在有权网络中，使各边权值总和达到最小的支撑生成树叫最小生 成树。 1、Kruskal算法 ⑴从E集中选权最小的边(vi, vj)；
最小生成树 最小生成树的定义 在有权网络中，使各边权值总和达到最小的支撑生成树叫最小生 成树。 1、Kruskal算法 ⑴从E集中选权最小的边(vi, vj)； ⑵从E集删去该边(vi, vj)； ⑶如果vi和vj在同一个分量中将(vi, vj)舍去，否则就将两个分量合 并。 ⑷如果选中的边数达到n－1，结束，否则转第一步继续进行。 28 1 10 16 14 2 5 6 24 18 12 25 22 4 3

23 friend class MinSpanTree; private: int tail, head, cost; };
最小生成树的类说明 边结点的构造 class MSTEdgeNode { friend class MinSpanTree; private: int tail, head, cost; }; Class MinSpanTree protected: MSTEdgedNode *edgevalue; int MaxSize, n; public: MinSpanTree( Graph<AdjacencyLists> & g); Insert (MSTEdgeNode & item); } tail(边的顶点位置) head(边的顶点位置) cost(边的权值)

24 Kruskal算法 Void Graph∷KruskalAlgorithm(MinSpanTree &T) { MSTEdgeNode e;
Heap< MSTEdgedNode> H(CurrentEdges); UFSets F(graphsize); for (int u = 0; u<graphsize; u + +) for ( int v = u + 1; v < graphsize; v + +) if (Edge[u][v] != MAXINT) e.tail = u; e.head = v; e.cost = Edge[u][v]; H.Insert(e); } int count = 1; while (count < graphsize) e = H..Delete( ); u = F.Find(e.tail); v = F.Find(e.head) if (u! = v) F.Union( u, v); T.Insert(e); count + +;

25 Prim算法 Prim算法的基本思想 从连通网络N = {V, E}中某一个顶点u0出发，选择与它关联的具有 最小权值的边(u0, v)，将其顶点加入到生成树的顶点集U中。 此后，每次从一个顶点在U中，另一个顶点不在U中的边子集中， 选择权值最小的边(u, v)。如此进行下去，直到网络中所有的顶点 都加入到生成树的顶点集U中为止。

26 Prim算法 Void Graph∷PrimAlgorithm(MinSpanTree & T) { lowcost = new int[graphsize]; nearvex = new int[graphsize]; for ( int i =1; i < graphsize; i + +) lowcost = Edge[0][i]; nearvex[I] = 0; } nearvex[0] = -1; // U中加入第一个顶点 MSTEdgeNode e; for ( I =1; I < graphsize; I + +) int min = MAXINT; int v = 0; for ( int j =0; j<graphsize; j + +) if (nearvex[j] != -1 &&lowcost[j] < min) {v = j; min = lowcost[j];} // 生成候选的边子集

27 Prim算法 if (v) { e.tail = nearvex[v]; e.head = v; e.cost = lowcost[v]; T.Insert(e); nearvex[v] = -1; // 选中的v加入U for ( j =0; j<graphsize; j + +) // v加入U，修改候选边子集 if (nearvex[j] != -1 &&Edge[v][j]<lowcost[j]) {lowcost[j] = Edge[v][j]; nearvex = v;} }

28 作 业 书面作业 13.21 13.23 13.25 13.28 编写下述方法的代码 MinSpanTree和Insert