图的相关算法（一）（广度和深度优先遍历、拓扑排序）图的相关算法（一）：广度和

上一次我们介绍了图的相关的数据结构，今天我们来介绍图的有关算法。
接下来我将以如下的顺序介绍算法：1.图的遍历（广度和深度）外带解决拓扑排序 2.最小生成树 3.最短路径
一、图的遍历 1.基本思路

1).图的遍历：从图中某一个顶点出发遍历途中其余结点，每一个顶点仅仅被遍历一次。 2).基本思路（1）树有四种遍历方式，因为根结点只有一个。而图的复杂情况是顺着一个点向下寻找，很有可能又找回到自己，容易形成回路造成死循环。（2）所以要设置一个数组visited[n]，n是图中顶点的个数，初值为0，当该顶点被遍历后，修改数组元素值为1. （3）基于上面的思想，形成两个遍历方案：深度优先遍历和广度优先遍历。

2.深度优先遍历
深度优先遍历，就是从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先搜索的策略是首先访问第一个邻接结点，再以这个被访问的邻接结点作为初始结点，访问它的第一邻接结点。总结来说：每次访问当前结点后首先访问当前结点的第一个邻接结点。
这种策略是优先纵向深度，而不是对一个结点的邻接结点做横向访问。算法标识如下：

（1）访问初始结点，并标记结点v为已访问。
（2）查找结点v的第一个邻接结点w。
（3）若w存在，则继续执行4，否则算法结束。
（4）若w未被访问，对w进行深度优先递归（即把w当做另一个v，执行算法1，2，3）。
（5）查找v的w邻接结点的下一个邻接结点，转到步骤3。
例如下图，深度优先遍历的顺序是1->2->4->8->5->3->6->7

文章图片

深度优先算法代码和广度合在一起了，都在下面
3.广度优先遍历
广度优先遍历类似与一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按照这个顺序来访问这个结点的邻接结点。算法的表述如下：

（1）访问初始结点v并标记结点v为已访问。
（2）结点v入队列。
（3）当队列非空时，继续执行，否则算法结束。
（4）出队列，取得队头结点u。
（5）查找结点u的第一个邻接结点w。
（6）若结点u的邻接结点w不存在，则转到步骤3；否则执行下面3个步骤：
1）若结点w未被访问，则访问结点w并标记为已访问。
2）结点w入队列。
3）查找结点u的继w邻接结点后的下一个邻接结点，转到步骤6。
例如下图，广度优先遍历的顺序为：1->2->3->4->5->6->7->8

文章图片

深度，广度优先算法代码，这个代码用的邻接表

package com.xushu.Undirectedgraph; /** * Java: 邻接表表示的"无向图(List Undirected Graph)" */import java.io.IOException; import java.util.Scanner; public class ListUDG { // 邻接表中表对应的链表的顶点 private class ENode { int ivex; // 该边所指向的顶点的位置 ENode nextEdge; // 指向下一条弧的指针 }// 邻接表中表的顶点 private class VNode { char data; // 顶点信息 ENode firstEdge; // 指向第一条依附该顶点的弧 }; private VNode[] mVexs; // 顶点数组///* //* 创建图(自己输入数据) //*/ //public ListUDG() { // //// 输入"顶点数"和"边数" //System.out.printf("input vertex number: "); //int vlen = readInt(); //System.out.printf("input edge number: "); //int elen = readInt(); //if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) { //System.out.printf("input error: invalid parameters!\n"); //return ; //} // //// 初始化"顶点" //mVexs = new VNode[vlen]; //for (int i = 0; i < mVexs.length; i++) { //System.out.printf("vertex(%d): ", i); //mVexs[i] = new VNode(); //mVexs[i].data = https://www.it610.com/article/readChar(); //mVexs[i].firstEdge = null; //} // //// 初始化"边" ////mMatrix = new int[vlen][vlen]; //for (int i = 0; i < elen; i++) { //// 读取边的起始顶点和结束顶点 //System.out.printf("edge(%d):", i); //char c1 = readChar(); //char c2 = readChar(); //int p1 = getPosition(c1); //int p2 = getPosition(c2); //// 初始化node1 //ENode node1 = new ENode(); //node1.ivex = p2; //// 将node1链接到"p1所在链表的末尾" //if(mVexs[p1].firstEdge == null) //mVexs[p1].firstEdge = node1; //else //linkLast(mVexs[p1].firstEdge, node1); //// 初始化node2 //ENode node2 = new ENode(); //node2.ivex = p1; //// 将node2链接到"p2所在链表的末尾" //if(mVexs[p2].firstEdge == null) //mVexs[p2].firstEdge = node2; //else //linkLast(mVexs[p2].firstEdge, node2); //} //}/* * 创建图(用已提供的矩阵) * * 参数说明： *vexs-- 顶点数组 *edges -- 边数组 */ public ListUDG(char[] vexs, char[][] edges) {// 初始化"顶点数"和"边数" int vlen = vexs.length; int elen = edges.length; // 初始化"顶点" mVexs = new VNode[vlen]; for (int i = 0; i < mVexs.length; i++) { mVexs[i] = new VNode(); mVexs[i].data = https://www.it610.com/article/vexs[i]; mVexs[i].firstEdge = null; }// 初始化"边" for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 char c1 = edges[i][0]; char c2 = edges[i][1]; // 读取边的起始顶点和结束顶点 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); // 初始化node1 ENode node1 = new ENode(); node1.ivex = p2; // 将node1链接到"p1所在链表的末尾" if(mVexs[p1].firstEdge == null) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 ENode node2 = new ENode(); node2.ivex = p1; // 将node2链接到"p2所在链表的末尾" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } }/* * 将node节点链接到list的最后 */ private void linkLast(ENode list, ENode node) { ENode p = list; while(p.nextEdge!=null) p = p.nextEdge; p.nextEdge = node; }/* * 返回ch位置 */ private int getPosition(char ch) { for(int i=0; i='a'&&ch<='z') || (ch>='A'&&ch<='Z'))); return ch; }/* * 读取一个输入字符 */ private int readInt() { Scanner scanner = new Scanner(System.in); return scanner.nextInt(); }/* * 深度优先搜索遍历图的递归实现 */ private void DFS(int i, boolean[] visited) {visited[i] = true; System.out.printf("%c ", mVexs[i].data); ENode node = mVexs[i].firstEdge; while (node != null) { if (!visited[node.ivex]) DFS(node.ivex, visited); node = node.nextEdge; } }/* * 深度优先搜索遍历图 */ public void DFSTravel() { boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记// 初始化所有顶点都没有被访问 for (int i = 0; i < mVexs.length; i++) visited[i] = false; System.out.printf("DFS: "); for (int i = 0; i < mVexs.length; i++) { if (!visited[i]) DFS(i, visited); } System.out.printf("\n"); }/* * 广度优先搜索（类似于树的层次遍历） */ public void BFSTravel() { int head = 0; int rear = 0; int[] queue = new int[mVexs.length]; // 辅组队列 boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记for (int i = 0; i < mVexs.length; i++) visited[i] = false; System.out.printf("BFS: "); for (int i = 0; i < mVexs.length; i++) { if (!visited[i]) { visited[i] = true; System.out.printf("%c ", mVexs[i].data); queue[rear++] = i; // 入队列 }while (head != rear) { //当队列不空 int j = queue[head++]; // 出队列 ENode node = mVexs[j].firstEdge; while (node != null) { int k = node.ivex; if (!visited[k]) { visited[k] = true; System.out.printf("%c ", mVexs[k].data); queue[rear++] = k; } node = node.nextEdge; } } } System.out.printf("\n"); }/* * 打印矩阵队列图 */ public void print() { System.out.printf("List Graph:\n"); for (int i = 0; i < mVexs.length; i++) { System.out.printf("%d(%c): ", i, mVexs[i].data); ENode node = mVexs[i].firstEdge; while (node != null) { System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data); node = node.nextEdge; } System.out.printf("\n"); } }public static void main(String[] args) { char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; ListUDG pG; // 自定义"图"(输入矩阵队列) //pG = new ListUDG(); // 采用已有的"图" pG = new ListUDG(vexs, edges); pG.print(); // 打印图 pG.DFSTravel(); // 深度优先遍历 pG.BFSTravel(); // 广度优先遍历 } }

二、拓扑排序参考文献 【图的相关算法（一）（广度和深度优先遍历、拓扑排序）】https://www.cnblogs.com/skywang12345/category/508186.html