一、图的基本介绍
图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点,图表示多对多的关系。
二、图的常用概念
##三、图的表示方式
- 图的表示方式有两种:邻接矩阵(二维数组表示)、邻接表(链表表示)
- 邻结矩阵:是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是row col 表示的1..n
- 邻接表:是数组加链表的形式
三、图的深度优先遍历
- 介绍
图的深度优先搜索(Depth First Search) 。
(1)深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
(2)我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
(3)显然,深度优先搜索是一个递归的过程 - 思想
深度优先遍历算法步骤
(1)访问初始结点v,并标记结点v为已访问。
(2)查找结点v的第一个邻接结点w。
(3)若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
(4)若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
(5)查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
四、图的广度优先遍历
思想
图的广度优先搜索(Broad First Search) 。
类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点步骤
(1)访问初始结点v并标记结点v为已访问。
(2)结点v入队列
(3)当队列非空时,继续执行,否则算法结束。
(4)出队列,取得队头结点u。
(5)查找结点u的第一个邻接结点w。
(6)若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
(6.1) 若结点w尚未被访问,则访问结点w并标记为已访问。
(6.2 )结点w入队列
(6.3) 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
五、代码
package com.depth; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; /** * @Description 构造图结构 * 说明:图具有多对多的特性 * @Author Meng * @Versions * @Date 2021-07-30-15:14 */ public class Graph { private ArrayList<String> vertexList; // 保存顶点 private int[][] edges; // 存储图对应的邻结矩阵 private int numOfEdges;// 表示边的数目,往邻结矩阵插入的边数目 private boolean[] isVertex; // 用于标记该顶点是否已经被访问 public static void main(String[] args) { // String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"}; String Vertexs[] = {"A", "B", "C", "D", "E"}; Graph graph = new Graph(5); // 插入顶点 for (String vertex : Vertexs) { graph.insertVertex(vertex); } // 描绘顶点之间的边的关系 graph.indertEdges(0,1,1); graph.indertEdges(0,2,1); graph.indertEdges(1,2,1); graph.indertEdges(1,3,1); graph.indertEdges(1,4,1); graph.showGraph(); // System.out.println("深度优先"); // graph.dfs(); System.out.println("广度优先"); graph.bfs(); } public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges = 0; isVertex = new boolean[n]; } /** * 当前这个顶点的邻接顶点 * @param index 当前顶点的下标 * @return 第一个相邻顶点的下标 */ public int getFirstNeighbor(int index){ for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] > 0) { return i; } } return -1; } /** * 当根据前一个邻接结点的下标来获取下一个邻接结点 * @param index 当前顶点 * @param v2 第一个邻接顶点 * @return 下一个邻接顶点的下标 */ public int getNextNeighbor(int index, int v2) { for (int i = v2 + 1; i < vertexList.size(); i++) { if (edges[index][i] > 0) { return i; } } return -1; } /** * 广度优先遍历 * @param isVertex * @param i */ public void bfs(boolean[] isVertex, int i) { // 创建一个队列 LinkedList<Integer> queue = new LinkedList<>(); // FirstVertexIndex 第一个顶点的下标 int fvi = 0; // firstNeighborVertexIndex第一个临界点的下标 int fnvi = 0; // 直接输出当前顶点 System.out.print(getValueByIndex(i) + "->"); // 将当前顶点加入队列(队列先进先出) queue.addLast(i); // 将当前顶点标记为已访问,以免重复输出 isVertex[i] = true; // 判断队列是否为空 while (!queue.isEmpty()) { // 得到队列的第一个顶点的下标 fvi = queue.removeFirst(); // 得到fvi顶点的第一个相邻顶点下标 fnvi = getFirstNeighbor(fvi); // 判断是否存在该邻接顶点 while (fnvi != -1) { // 存在该邻接顶点,继续判断该邻接顶点是否被标记为已访问 if (!isVertex[fnvi]){ // 若没有标记为已访问,则直接输出 System.out.print(getValueByIndex(fnvi) + "->"); // 继续将该邻接顶点加入队列 queue.addLast(fnvi); // 并将该邻接顶点标记为已访问 isVertex[fnvi] = true; } // 继续获取该邻接顶点的下一个邻接顶点 fnvi = getNextNeighbor(i,fnvi); } } } /** * 重载bfs */ public void bfs() { // 遍历每个顶点,保证没有遗漏任何一个顶点 for (int i = 0; i < getNumOfVertex(); i++) { // 将每个顶点广度优先遍历前,判断该顶点是否被标记为已访问 if (!isVertex[i]){ // 若没有被标记为已访问,则进行广度优先遍历 bfs(isVertex,i); } } } /** * 深度优先遍历 * @param isVertex 用于标记该顶点是否已经被访问 * @param i 当前顶点 */ public void dfs(boolean[] isVertex, int i) { // 直接输出当前顶点 System.out.print(getValueByIndex(i) + "->"); // 标记当前顶点已被访问 isVertex[i] = true; // 第一个邻接顶点的下标,若没有则返回-1 int firstNeighborVertex = getFirstNeighbor(i); // 判断是否有这邻接顶点的下标 while (firstNeighborVertex != -1){ //若存在该下标,则继续判断该下标对应的顶点是否已被访问 if (!isVertex[firstNeighborVertex]) { // 若该下标对应的顶点没有被访问,则对该顶点进行深度优先遍历 dfs(isVertex, firstNeighborVertex); } // 返回第一个邻接顶点的下一个邻接顶点,若没有则返回-1 firstNeighborVertex = getNextNeighbor(i, firstNeighborVertex); } } public void dfs(){ // 遍历所有顶点 for (int i = 0; i < getNumOfVertex(); i++) { // 判断该顶点是否被访问 if (!isVertex[i]){ // 没有访问,就深度优先遍历这个顶点 dfs(isVertex,i); } } } /** * 打印邻结数组 */ public void showGraph() { for (int i = 0; i < edges.length; i++) { System.out.println(Arrays.toString(edges[i])); } } /** * 返回结点i(下标)对应的顶点 0->"A" 1->"B" 2->"C" * @param i * @return */ public String getValueByIndex(int i) { return vertexList.get(i); } /** * 返回v1和v2的权值 */ public int getWeight(int v1, int v2) { return edges[v1][v2]; } /** * 得到边的条数 * @return */ public int getNumOfEdges() { return numOfEdges; } /** * 获取顶点的个数 * @return */ public int getNumOfVertex(){ return vertexList.size(); } /** * 将顶点插入到vertexList * @param vertex 顶点值 */ public void insertVertex(String vertex){ vertexList.add(vertex); } /** * 插入边,记录那两个点是相连的 * @param v1 顶点1 * @param v2 顶点2 * @param weight 权值 表示两个点是否相连 */ public void indertEdges(int v1, int v2, int weight) { edges[v1][v2] = weight; //由于是无向表所有节点 A-B B-A edges[v2][v1] = weight; numOfEdges++; } }