2️⃣深度优先搜索
🍀（1）深度优先搜索介绍
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
深度优先搜索是一个递归的过程。
🍀（2）深度优先搜索图解
无向图的深度优先搜索
对上面的图G1进行深度优先遍历，从顶点A开始
第1步：访问A。
第2步：访问(A的邻接点)C。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步：访问(C的邻接点)B。 在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步：访问(C的邻接点)D。 在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步：访问(A的邻接点)F。 前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。
因此访问顺序是：A -> C -> B -> D -> F -> G -> E
有向图的深度优先搜索：
对上面的图G2进行深度优先遍历，从顶点A开始。
第1步：访问A。
第2步：访问B。 在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
第3步：访问C。在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
第4步：访问E。 接下来访问C的出边的另一个顶点，即顶点E。
第5步：访问D。 接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
第6步：访问F。 接下应该回溯"访问A的出边的另一个顶点F"。
第7步：访问G。
因此访问顺序是：A -> B -> C -> E -> D -> F -> G
🍀（3）深度优先搜索代码实现
public class Graph { /** * 定义顶点的抽象 * @param <T> */ public static class Vertex<T>{ // 要保存的数据 private T t; // 其他和我管理的邻接节点 private List<Vertex<T>> neighborList; private boolean visited = false; public Vertex(T t) { this.t = t; } } // dfs 深度优先遍历算法 public static <T> void dfs(Vertex<T> vertex){ // 1、定义一个临时存储的空间 Stack<Vertex<T>> stack = new Stack<>(); // 2、将第一个顶点放入栈中 stack.push(vertex); while (!stack.isEmpty()){ // 3、将栈顶的元素取出 Vertex<T> temp = stack.pop(); // 4、执行操作 if(!temp.visited){ System.out.println(temp.t); temp.visited = true; } // 5、将邻接节点压栈 if(temp.neighborList != null){ stack.addAll(temp.neighborList); } } } }
四、最小生成树
1️⃣最小生成树概念
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
2️⃣克鲁斯卡尔(Kruskal)算法
🍀（1）克鲁斯卡尔算法介绍
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想： 按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法： 首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
🍀（2）克鲁斯卡尔算法图解
以上图G4为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)。
第1步：将边<E,F>加入R中。 边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边<C,D>加入R中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边<D,E>加入R中。 上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边<B,F>加入R中。上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步：将边<E,G>加入R中。 上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边<A,B>加入R中。上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
🍀（3）克鲁斯卡尔算法代码实现
这里选取"邻接矩阵"对克鲁斯卡尔算法进行说明。
// 边的结构体 private static class EData { char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 public EData(char start, char end, int weight) { this.start = start; this.end = end; this.weight = weight; } }
// 邻接矩阵边对应的结构体 public class MatrixUDG { private int mEdgNum; // 边的数量 private char[] mVexs; // 顶点集合 private int[][] mMatrix; // 邻接矩阵 private static final int INF = Integer.MAX_VALUE; // 最大值 ... }
/* * 克鲁斯卡尔（Kruskal)最小生成树 */ public void kruskal() { int index = 0; // rets数组的索引 int[] vends = new int[mEdgNum]; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。 EData[] rets = new EData[mEdgNum]; // 结果数组，保存kruskal最小生成树的边 EData[] edges; // 图对应的所有边 // 获取"图中所有的边" edges = getEdges(); // 将边按照"权"的大小进行排序(从小到大) sortEdges(edges, mEdgNum); for (int i=0; i<mEdgNum; i++) { int p1 = getPosition(edges[i].start); // 获取第i条边的"起点"的序号 int p2 = getPosition(edges[i].end); // 获取第i条边的"终点"的序号 int m = getEnd(vends, p1); // 获取p1在"已有的最小生成树"中的终点 int n = getEnd(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 } } // 统计并打印"kruskal最小生成树"的信息 int length = 0; for (int i = 0; i < index; i++) length += rets[i].weight; System.out.printf("Kruskal=%d: ", length); for (int i = 0; i < index; i++) System.out.printf("(%c,%c) ", rets[i].start, rets[i].end); System.out.printf("\n"); }
3️⃣普里姆(Prim)算法
🍀（1）普里姆算法介绍
普里姆(Prim)算法，是用来求加权连通图的最小生成树的算法。
基本思想 ： 对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
🍀（2）普里姆算法图解
以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。
初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步：将顶点A加入到U中。 此时，U={A}。
第2步：将顶点B加入到U中。 上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步：将顶点F加入到U中。 上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步：将顶点E加入到U中。 上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步：将顶点D加入到U中。 上一步操作之后，U={A,B,F,E},V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步：将顶点C加入到U中。 上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步：将顶点G加入到U中。 上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。
此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。
🍀（3）普里姆算法代码实现
这里以"邻接矩阵"为例对普里姆算法进行说明。
// 邻接矩阵对应的结构体 public class MatrixUDG { private char[] mVexs; // 顶点集合 private int[][] mMatrix; // 邻接矩阵 private static final int INF = Integer.MAX_VALUE; // 最大值 ... }
/* * prim最小生成树 * * 参数说明： * start -- 从图中的第start个元素开始，生成最小树 */ public void prim(int start) { int num = mVexs.length; // 顶点个数 int index=0; // prim最小树的索引，即prims数组的索引 char[] prims = new char[num]; // prim最小树的结果数组 int[] weights = new int[num]; // 顶点间边的权值 // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。 prims[index++] = mVexs[start]; // 初始化"顶点的权值数组"， // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 for (int i = 0; i < num; i++ ) weights[i] = mMatrix[start][i]; // 将第start个顶点的权值初始化为0。 // 可以理解为"第start个顶点到它自身的距离为0"。 weights[start] = 0; for (int i = 0; i < num; i++) { // 由于从start开始的，因此不需要再对第start个顶点进行处理。 if(start == i) continue; int j = 0; int k = 0; int min = INF; // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。 while (j < num) { // 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。 if (weights[j] != 0 && weights[j] < min) { min = weights[j]; k = j; } j++; } // 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。 // 将第k个顶点加入到最小生成树的结果数组中 prims[index++] = mVexs[k]; // 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。 weights[k] = 0; // 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。 for (j = 0 ; j < num; j++) { // 当第j个节点没有被处理，并且需要更新时才被更新。 if (weights[j] != 0 && mMatrix[k][j] < weights[j]) weights[j] = mMatrix[k][j]; } } // 计算最小生成树的权值 int sum = 0; for (int i = 1; i < index; i++) { int min = INF; // 获取prims[i]在mMatrix中的位置 int n = getPosition(prims[i]); // 在vexs[0...i]中，找出到j的权值最小的顶点。 for (int j = 0; j < i; j++) { int m = getPosition(prims[j]); if (mMatrix[m][n]<min) min = mMatrix[m][n]; } sum += min; } // 打印最小生成树 System.out.printf("PRIM(%c)=%d: ", mVexs[start], sum); for (int i = 0; i < index; i++) System.out.printf("%c ", prims[i]); System.out.printf("\n"); }
五、拓扑排序
1️⃣拓扑排序介绍
拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
通过简单的例子进行说明：例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。
在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。
2️⃣拓扑排序的算法图解
拓扑排序算法的基本步骤：
1.构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；
2.把所有没有依赖顶点的节点放入Q；
3.当Q还有顶点的时候，执行下面步骤：
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；
3.2 对n每一个邻接点m(n是起点，m是终点)：
3.2.1 去掉边<n,m>;
3.2.2 如果m没有依赖顶点，则把m放入Q。
注：顶点A没有依赖顶点，是指不存在以A为终点的边。
以上图为例，来对拓扑排序进行演示。
第1步：将B和C加入到排序结果中。顶点B和顶点C都是没有依赖顶点，因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储，因此先访问B，再访问C。访问B之后，去掉边<B,A>和<B,D>，并将A和D加入到队列Q中。同样的，去掉边<C,F>和<C,G>，并将F和G加入到Q中。
(1) 将B加入到排序结果中，然后去掉边<B,A>和<B,D>；此时，由于A和D没有依赖顶点，因此并将A和D加入到队列Q中。
(2) 将C加入到排序结果中，然后去掉边<C,F>和<C,G>；此时，由于F有依赖顶点D，G有依赖顶点A，因此不对F和G进行处理。
第2步：将A,D依次加入到排序结果中。第1步访问之后，A,D都是没有依赖顶点的，根据存储顺序，先访问A，然后访问D。访问之后，删除顶点A和顶点D的出边。
第3步：将E,F,G依次加入到排序结果中。
因此访问顺序是：B -> C -> A -> D -> E -> F -> G
3️⃣拓扑排序的代码实现
拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。
// 邻接表对应的结构体 public class ListDG { // 邻接表中表对应的链表的顶点 private class ENode { int ivex; // 该边所指向的顶点的位置 ENode nextEdge; // 指向下一条弧的指针 } // 邻接表中表的顶点 private class VNode { char data; // 顶点信息 ENode firstEdge; // 指向第一条依附该顶点的弧 }; private VNode[] mVexs; // 顶点数组 ... }
/* * 拓扑排序 * * 返回值： * -1 -- 失败(由于内存不足等原因导致) * 0 -- 成功排序，并输入结果 * 1 -- 失败(该有向图是有环的) */ public int topologicalSort() { int index = 0; int num = mVexs.size(); int[] ins; // 入度数组 char[] tops; // 拓扑排序结果数组，记录每个节点的排序后的序号。 Queue<Integer> queue; // 辅组队列 ins = new int[num]; tops = new char[num]; queue = new LinkedList<Integer>(); // 统计每个顶点的入度数 for(int i = 0; i < num; i++) { ENode node = mVexs.get(i).firstEdge; while (node != null) { ins[node.ivex]++; node = node.nextEdge; } } // 将所有入度为0的顶点入队列 for(int i = 0; i < num; i ++) if(ins[i] == 0) queue.offer(i); // 入队列 while (!queue.isEmpty()) { // 队列非空 int j = queue.poll().intValue(); // 出队列。j是顶点的序号 tops[index++] = mVexs.get(j).data; // 将该顶点添加到tops中，tops是排序结果 ENode node = mVexs.get(j).firstEdge;// 获取以该顶点为起点的出边队列 // 将与"node"关联的节点的入度减1； // 若减1之后，该节点的入度为0；则将该节点添加到队列中。 while(node != null) { // 将节点(序号为node.ivex)的入度减1。 ins[node.ivex]--; // 若节点的入度为0，则将其"入队列" if( ins[node.ivex] == 0) queue.offer(node.ivex); // 入队列 node = node.nextEdge; } } if(index != num) { System.out.printf("Graph has a cycle\n"); return 1; } // 打印拓扑排序结果 System.out.printf("== TopSort: "); for(int i = 0; i < num; i ++) System.out.printf("%c ", tops[i]); System.out.printf("\n"); return 0; }
