数据结构之图:邻接矩阵和邻接表、深度优先遍历和广度优先遍历

太过爱你忘了你带给我的痛 2023-02-20 02:15 106阅读 0赞

# 简介 #

线性表是一种线性结构，除了头结点和尾节点，线性表的每个元素都只有一个前取节点和一个后继节点。而**树结构**则相较于线性表更加复杂，它描述的关系为数据元素之间的父子关系，也是现实世界父子关系的缩影，

*  一个父亲节点可以有零个或者多个子节点
 *  而每个子节点有且只有一个父节点

但是在图是比树更加复杂的数据结构，图的基本特征是，**在图中，数据元素（顶点）之间的关系使任意的，每个顶点都可以和其他任何顶点相关**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70][]

上图中就存在两个图，其中右边的图更加复杂，是现实世界中的交通路线图。左图是抽象图，可以看到在左图是一个**无向图**，其中

*  顶点集合为\{A、B、C、D、E\}
 *  边集为\{A-B， B-C， A-D， D-E， B-C\}一共五条边
    
     *  注意：在无向图中A-B和B-A是一样的。

## 定义 ##

图G由两个集合V和E组成，记为**G=\{V, E\}**。其中V是顶点的有限集合，E是连接V中两个不同顶点的边的有限集合。如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G是有向图。如果顶点对是无序的，则称G是无向图。

## 图的常用概念 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2][]

# 图的存储方式 #

图有两种存储方式：邻接矩阵（**二维数组**）和邻接表（**链表**），选取那种存储方式取决于具体的图结构和欲实施的操作。

## 邻接矩阵 ##

![1592622289383][]

转化成邻接矩阵，则表示如下：

![1592622396024][]

邻接矩阵表示法是把邻接矩阵的n行表示成n个单链表。其中较为关键的是**边链表**的概念

> 与顶点v邻接的所有顶点以某种次序组成的单链表称作顶点v的边链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3][]

邻接矩阵中Graph类的声明如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4][]

## 邻接表 ##

# 代码实现 #

## 邻接矩阵 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6][]

## 邻接矩阵代码实现 ##

上述的UML图对应的代码如下：

package com.atguigu.graph.graph;
    
    import java.awt.*;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /** * 使用邻接矩阵实现图类 * * @author songquanheng * @Time: 2020/6/20-11:32 */
    public class Graph { 
        /** * 顶点数组 */
        private String[] vertexs;
        private int numberOfVertex;
        /** * 边数 */
        private int numberOfEdges;
    
    
        /** * 边集合，采用二维数组表示 */
        private int[][] edges;
    
        public static void main(String[] args) { 
            String[] vertexs = "1 2 3 4 5 6 7 8 ".split(" ");
            Graph graph = new Graph(vertexs);
            graph.show();
    
            graph.insertEdge(0, 1, 1);
            graph.insertEdge(0, 2, 1);
            graph.insertEdge(1, 3, 1);
            graph.insertEdge(1, 4, 1);
            graph.insertEdge(3, 7, 1);
            graph.insertEdge(4, 7, 1);
            graph.insertEdge(2, 5, 1);
            graph.insertEdge(2, 6, 1);
            graph.insertEdge(5, 6, 1);
    
            graph.show();
    
            graph.dfs();
            System.out.println();
            graph.dfs(2);
            System.out.println();
    
            graph.bfs();
            System.out.println();
    
            graph.bfs(2);
            System.out.println();
        }
    
        public Graph(String[] vertexs) { 
            numberOfVertex = vertexs.length;
            this.vertexs = new String[numberOfVertex];
            int i = 0;
            for (String item : vertexs) { 
                this.vertexs[i++] = item;
            }
    
            // 初始化邻接矩阵
            this.edges = new int[numberOfVertex][numberOfVertex];
    
        }
    
        public void show() { 
            System.out.println("Graph.show");
            System.out.println(Arrays.toString(vertexs));
            System.out.println();
            for (int[] row : edges) { 
                System.out.println(Arrays.toString(row));
            }
            System.out.println("graph.getNumberOfEdges() = " + getNumberOfEdges());
            System.out.println("graph.getNumberOfVertex() = " + getNumberOfVertex());
            System.out.println();
        }
    
        /** * @param v1 边的起点的序号 * @param v2 边的终点的序号 * @param w 边的权值 无向图赋值为1即可 */
        public void insertEdge(int v1, int v2, int w) { 
            edges[v1][v2] = w;
            edges[v2][v1] = w;
            numberOfEdges++;
        }
    
        /** * 深度优先遍历，此时不考虑起始点，即以0号序列的顶点为起始顶点 */
        public void dfs() { 
            System.out.println("Graph.dfs");
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
            for (int i = 0; i < numberOfVertex; i++) { 
                if (!visited[i]) { 
                    dfs(i, visited);
                }
    
            }
            System.out.println();
        }
    
        /** * 从指定顶点进行深度优先遍历 * * @param vertex 开始顶点的序号 */
        public void dfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            dfs(vertex, visited);
            System.out.println();
        }
    
        /** * @param vertex 深度优先遍历的开始顶点所在的序号 */
        private void dfs(int vertex, boolean[] visited) { 
            System.out.print(vertexs[vertex] + "->");
            visited[vertex] = true;
    
            int w = getFirstNeighbour(vertex);
            while (w != -1) { 
                if (!visited[w]) { 
                    dfs(w, visited);
                } else { 
                    // 如果w已经被访问过，则访问w的下一个邻接顶点
                    w = getNextNeighbour(vertex, w);
                }
    
            }
    
        }
    
        /** * 广度优先遍历 */
        public void bfs() { 
            System.out.println("Graph.bfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            for (int i = 0; i < numberOfVertex; i++) { 
                if (!visited[i]) { 
                    bfs(i, visited);
                }
            }
        }
    
        /** * 从指定顶点vertex开始进行广度优先遍历 * * @param vertex 从vertex顶点开始进行广度优先遍历 */
        public void bfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
    
        }
    
        /** * 从顶点vertex开始进行广度优先遍历 * * @param vertex 顶点序号 * @param visited 辅助遍历数组 */
        private void bfs(int vertex, boolean[] visited) { 
            System.out.print(vertexs[vertex] + "->");
            visited[vertex] = true;
    
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addLast(vertex);
            while (!queue.isEmpty()) { 
                // 此时head所在的顶点已经访问过了
                int head = queue.remove();
                int w = getFirstNeighbour(head);
    
                while (w != -1) { 
                    if (!visited[w]) { 
                        // 深度优先遍历从此处开始递归，但广度优先不进行递归
                        System.out.print(vertexs[w] + "->");
                        visited[w] = true;
                        queue.addLast(w);
                    }
                    w = getNextNeighbour(head, w);
                }
            }
    
    
        }
    
    
        /** * 返回序号为vertex的第一个邻接顶点的序号 * * @param vertex 顶点的序号，对于A顶点，则传入的vertex为A顶点所在的序号0 * @return 返回该顶点的第一个邻接顶点所在的序号, 如果存在，返回顶点所在的序号，否则返回-1表示不存在 */
        public int getFirstNeighbour(int vertex) { 
            return neighbour(vertex, 0);
        }
    
        /** * 返回序号为vertex的顶点相对于序号为currentAdjacentVertex的顶点的下一个邻接顶点的序号 * * @param vertex 顶点序号 * @param currentAdjacentVertex currentAdjacentVertex为vertex序号顶点的邻接点，求相对于这个currentAdjacentVertex的下一个邻接顶点的序号 * @return 返回下一个邻接顶点的序号 */
        public int getNextNeighbour(int vertex, int currentAdjacentVertex) { 
            return neighbour(vertex, currentAdjacentVertex + 1);
        }
    
        /** * 从firstSearchLocation查找获取顶点vertex序号的顶点的邻接点的序号， * * @param vertex 顶点序号 * @param firstSearchIndex 查找位置值的范围为[0, numberOfVertex - 1] * @return 如果从firstSearchIndex开始查找存在返回邻接顶点，则返回邻接顶点的序号，否则返回1 */
        private int neighbour(int vertex, int firstSearchIndex) { 
            for (int i = firstSearchIndex; i < numberOfVertex; i++) { 
                if (edges[vertex][i] > 0) { 
                    return i;
                }
            }
            return -1;
        }
    
        public int getNumberOfEdges() { 
            return numberOfEdges;
        }
    
        public int getNumberOfVertex() { 
            return numberOfVertex;
        }
    
    
    }

### 深度优先遍历阐述 ###

深度优先遍历的思想如下：

> 因为图的人一顶点都可能与其他顶点相连接，所以图的遍历算法比树的遍历算法要复杂的多。在访问了某个顶点之后，可能沿着某条路径搜索又回到了出发点。因此，为保证每个顶点恰好只访问一次，需要额外设置一个标志顶点是否被访问的辅助数组visited。该数组元素的初值均为false，一旦顶点vi被访问，相应的visited\[i\]置位true。图的遍历算法应用非常广泛，能够解决很多与图有关的问题，**如判断两个顶点之间是否可达，确定某一顶点所属的联通分量，构造图的支撑树等**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 7][]

### 深度优先代码实现 ###

/** * 深度优先遍历，此时不考虑起始点，即以0号序列的顶点为起始顶点 */
        public void dfs() { 
            System.out.println("Graph.dfs");
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
            for (int i = 0; i < numberOfVertex; i++) { 
                if (!visited[i]) { 
                    dfs(i, visited);
                }
    
            }
            System.out.println();
        }
    
        /** * 从指定顶点进行深度优先遍历 * * @param vertex 开始顶点的序号 */
        public void dfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            dfs(vertex, visited);
            System.out.println();
        }
    
        /** * @param vertex 深度优先遍历的开始顶点所在的序号 */
        private void dfs(int vertex, boolean[] visited) { 
            System.out.print(vertexs[vertex] + "->");
            visited[vertex] = true;
    
            int w = getFirstNeighbour(vertex);
            while (w != -1) { 
                if (!visited[w]) { 
                    dfs(w, visited);
                } else { 
                    // 如果w已经被访问过，则访问w的下一个邻接顶点
                    w = getNextNeighbour(vertex, w);
                }
    
            }
        }

深度优先遍历在实现时，关键的几个步骤为：

1.  初始化辅助数组，均置为false
2.  标志初始顶点被访问，并获取该顶点的第一个邻接顶点，作为当前的邻接顶点
3.  循环，判断该邻接顶点是否被访问过，如果没有被访问过，则以相同的策略访问邻接顶点，否则获取初始顶点的相对于当前邻接顶点获取下一个邻接顶点继续进行深度优先遍历

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 8][]

### 广度优先遍历阐述 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 9][]

### 广度优先遍历代码实现 ###

/** * 广度优先遍历 */
        public void bfs() { 
            System.out.println("Graph.bfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            for (int i = 0; i < numberOfVertex; i++) { 
                if (!visited[i]) { 
                    bfs(i, visited);
                }
            }
        }
    
        /** * 从指定顶点vertex开始进行广度优先遍历 * * @param vertex 从vertex顶点开始进行广度优先遍历 */
        public void bfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
    
        }
    
        /** * 从顶点vertex开始进行广度优先遍历 * * @param vertex 顶点序号 * @param visited 辅助遍历数组 */
        private void bfs(int vertex, boolean[] visited) { 
            System.out.print(vertexs[vertex] + "->");
            visited[vertex] = true;
    
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addLast(vertex);
            while (!queue.isEmpty()) { 
                // 此时head所在的顶点已经访问过了
                int head = queue.remove();
                int w = getFirstNeighbour(head);
    
                while (w != -1) { 
                    if (!visited[w]) { 
                        // 深度优先遍历从此处开始递归，但广度优先不进行递归
                        System.out.print(vertexs[w] + "->");
                        visited[w] = true;
                        queue.addLast(w);
                    }
                    w = getNextNeighbour(head, w);
                }
            }
    
    
        }

## 邻接表 ##

## 邻接表代码实现 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 10][]

邻接表的代码实现如下所示：

package com.atguigu.graph.graph;
    
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.stream.Collectors;
    
    /** * 邻接表实现图 * * @author songquanheng */
    public class GraphList { 
        private int numberOfVertex;
        private int numberOfEdge;
    
        /** * 顶点集合 */
        private Vertex[] vertices;
    
        public static void main(String[] args) { 
            GraphList graphList = new GraphList();
            graphList.show();
    
            // 8 1 2 3 4 5 6 7 8
            graphList.initializeVertex();
            // 9 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1 6 7 1 4 8 1 5 8 1
            graphList.initializeEdge();
            graphList.show();
            System.out.println();
    
            graphList.dfs(0);
            graphList.dfs("1");
            System.out.println();
    
            graphList.bfs(0);
            graphList.bfs("1");
    
    
        }
    
        /** * 解决离散图像-即非连通图像的深度优先遍历 */
        public void dfs() { 
            System.out.println("GraphList.dfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
            for (int i = 0; i < getNumberOfVertex(); i++) { 
                if (!visited[i]) { 
                    dfs(i, visited);
                }
            }
    
            System.out.println();
        }
    
        public void dfs(String vertexName) { 
            System.out.println("GraphList.dfs");
            System.out.println("vertexName = [" + vertexName + "]");
    
    
            int vertex = vertexIndexByName(vertexName);
            dfs(vertex);
            System.out.println();
        }
    
        /** * 从指定顶点进行深度优先遍历，对于连通的图可以完整的遍历 * * @param vertex 开始顶点的序号 */
        public void dfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            dfs(vertex, visited);
            System.out.println();
        }
    
        /** * @param vertex 深度优先遍历的开始顶点所在的序号 */
        private void dfs(int vertex, boolean[] visited) { 
            System.out.print(vertices[vertex].getVertexName() + "->");
            visited[vertex] = true;
    
            int w = getFirstNeighbour(vertex);
            while (w != -1) { 
                if (!visited[w]) { 
                    dfs(w, visited);
                } else { 
                    // 如果w已经被访问过，则访问w的下一个邻接顶点
                    w = getNextNeighbour(vertex, w);
                }
    
            }
    
        }
    
        public void bfs(String vertexName) { 
            System.out.println("GraphList.bfs");
            System.out.println("vertexName = [" + vertexName + "]");
    
            int vertex = vertexIndexByName(vertexName);
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
            System.out.println();
        }
        /** * 从指定顶点开始进行广度优先遍历 * @param vertex 顶点所在的位置 */
        public void bfs(int vertex) { 
            System.out.println("GraphList.bfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
            System.out.println();
        }
    
        private void bfs(int vertex, boolean[] visited) { 
            System.out.print(vertices[vertex].getVertexName() + "->");
            visited[vertex] = true;
    
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addLast(vertex);
    
            while (!queue.isEmpty()) { 
                traverseVertex(visited, queue);
            }
    
            System.out.println();
        }
    
        /** * @param visited 访问的辅助数组 * @param queue 待访问的顶点队列 */
        private void traverseVertex(boolean[] visited, LinkedList<Integer> queue) { 
            int vertex = queue.remove();
            int neighbour = getFirstNeighbour(vertex);
    
            // 一个循环走完，就把一行走位了，在这一行中，顶点vertexIndex不变，而neighbour作为vertexIndex的邻接顶点一直在遍历
            // 然后在下一个循环中，vertexIndex更新成第一个顶点的邻接顶点了
            while (neighbour != -1) { 
                if (!visited[neighbour]) { 
                    System.out.print(vertices[neighbour].getVertexName() + "->");
                    visited[neighbour] = true;
                    queue.addLast(neighbour);
                }
                neighbour = getNextNeighbour(vertex, neighbour);
            }
        }
    
        /** * 负责图的初始化 */
        public void initializeVertex() { 
            System.out.println("GraphList.initializeVertex");
            Scanner scan = new Scanner(System.in);
            System.out.println("请输入顶点数");
            this.numberOfVertex = scan.nextInt(); // 8
    
            this.vertices = new Vertex[this.numberOfVertex];
            System.out.println("请依次输入顶点名称：");
    
            for (int i = 0; i < numberOfVertex; i++) { 
                String name = scan.next(); // 1 2 3 4 5 6 7 8
                Vertex vertex = new Vertex(name);
                vertices[i] = vertex;
            }
    
            System.out.println("顶点初始化完成");
        }
    
        public void initializeEdge() { 
            System.out.println("GraphList.initializeEdge");
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入顶点数"); // 9
            this.numberOfEdge = scanner.nextInt();
    
    
            for (int i = 0; i < this.numberOfEdge; i++) { 
                System.out.println("开始输入边，形式为(顶点1名称 顶点2名称 权重)");
                // 此处应校验顶点名称是合法的，即用户输入的顶点在之前的初始化顶点中
                // 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1 6 7 1 4 8 1 5 8 1
                String vertex1Name = scanner.next();
                String vertex2Name = scanner.next();
                int weight = scanner.nextInt();
    
                int vertex1Index = vertexIndexByName(vertex1Name);
                int vertex2Index = vertexIndexByName(vertex2Name);
    
                Edge edge1 = new Edge(vertex2Index, weight);
                vertices[vertex1Index].add(edge1);
    
                Edge edge2 = new Edge(vertex1Index, weight);
                vertices[vertex2Index].add(edge2);
    
            }
        }
    
        /** * @param index 顶点序号 * @return 返回顶点序号的第一个邻接顶点的序号 */
        public int getFirstNeighbour(int index) { 
            Edge edge = vertices[index].getAdjacentEdge();
            if ((edge != null)) { 
                return edge.getAdjacentVertex();
            }
            return -1;
        }
    
        /** * 获取index顶点，相对于currentNeighbourIndex的下一个邻接顶点 * * @param index 顶点序号 * @param currentNeighbourIndex 在顶点序号的邻接顶点的当前邻接顶点 * @return 相对于currentNeighbourIndex的，index顶点的下一个邻接顶点 */
        public int getNextNeighbour(int index, int currentNeighbourIndex) { 
            Edge edge = vertices[index].getAdjacentEdge();
    
            while (edge != null && edge.getAdjacentVertex() != currentNeighbourIndex) { 
                edge = edge.getNext();
            }
    
            edge = edge.getNext();
            if (edge == null) { 
                return -1;
            } else { 
                return edge.getAdjacentVertex();
            }
    
    
        }
    
        /** * 输出图的邻接链表表示 */
        public void show() { 
            System.out.println("GraphList.show");
            System.out.println("numberOfVertex = " + getNumberOfVertex());
            System.out.println("numberOfEdge = " + getNumberOfEdge());
    
            Edge edge;
            for (int i = 0; i < numberOfVertex; i++) { 
                System.out.print(vertices[i].vertexName);
    
                edge = vertices[i].adjacentEdge;
                while (edge != null) { 
                    // edge.getAdjacentVertex() 获取边上的邻接顶点
                    // vertices[edge.getAdjacentVertex()].getVertexName()
                    System.out.print("-->" + vertexNameByIndex(edge.getAdjacentVertex()));
                    edge = edge.getNext();
                }
                System.out.println();
            }
            System.out.println();
        }
    
        /** * @param index 根据顶点的索引号获取顶点的名称 * @return 顶点名称 */
        public String vertexNameByIndex(int index) { 
            assert index < vertices.length;
    
            return vertices[index].getVertexName();
        }
    
        /** * 根据顶点名称返回顶点的索引号 * * @param vertexName 顶点名称 * @return 返回的是边对象的标签 */
        public int vertexIndexByName(String vertexName) { 
            List<String> validVertexNames = Arrays.stream(vertices)
                    .map(vertex -> vertex.getVertexName())
                    .collect(Collectors.toList());
            assert validVertexNames.contains(vertexName);
    
            for (int i = 0; i < getNumberOfVertex(); i++) { 
                if (vertices[i].vertexName.equals(vertexName)) { 
                    return i;
                }
            }
            return -1;
        }
    
        /** * @return 获取图中的顶点数 */
        public int getNumberOfVertex() { 
            return numberOfVertex;
        }
    
        /** * @return 获取图中的边数 */
        public int getNumberOfEdge() { 
            return numberOfEdge;
        }
    }
    
    /** * 边类 */
    class Edge { 
        /** * 邻接顶点 */
        private int adjacentVertex;
        /** * 权重 */
        private int weight;
        /** * 下一个邻接顶点 */
        private Edge next;
    
        public Edge getNext() { 
            return next;
        }
    
        public void setNext(Edge next) { 
            this.next = next;
        }
    
        public Edge(int adjacentVertex, int weight) { 
            this.adjacentVertex = adjacentVertex;
    
            this.weight = weight;
        }
    
        public int getAdjacentVertex() { 
            return adjacentVertex;
        }
    }
    
    /** * 顶点类 */
    class Vertex { 
        /** * 顶点名称 */
        String vertexName;
        /** * 边链表的头指针 */
        Edge adjacentEdge;
    
        public Vertex(String vertexName) { 
            this.vertexName = vertexName;
        }
    
        public String getVertexName() { 
            return vertexName;
        }
    
        public void setVertexName(String vertexName) { 
            this.vertexName = vertexName;
        }
    
        public Edge getAdjacentEdge() { 
            return adjacentEdge;
        }
    
        public void setAdjacentEdge(Edge adjacentEdge) { 
            this.adjacentEdge = adjacentEdge;
        }
    
        /** * 把待添加的邻接边添加到末尾 * * @param edge 待添加的邻接边 */
        public void add(Edge edge) { 
            // 表示待添加的邻接表为第一条边
            if (adjacentEdge == null) { 
                adjacentEdge = edge;
            } else { 
                Edge tail = tail();
                tail.setNext(edge);
    
            }
        }
    
        /** * 获取当前顶点的链表的尾部, 在该顶点的邻接表不为空的情况下调用 * * @return 获取邻接表的尾部 */
        private Edge tail() { 
            assert adjacentEdge != null;
            Edge tail = adjacentEdge;
            while (tail.getNext() != null) { 
                tail = tail.getNext();
            }
            return tail;
        }
    
    
    }

### 代码运行结果 ###

GraphList.show
    numberOfVertex = 0
    numberOfEdge = 0
    
    GraphList.initializeVertex
    璇疯緭鍏ラ《鐐规暟
    8 1 2 3 4 5 6 7 8
    璇蜂緷娆¤緭鍏ラ《鐐瑰悕绉帮細
    椤剁偣鍒濆鍖栧畬鎴�
    GraphList.initializeEdge
    璇疯緭鍏ラ《鐐规暟
    9 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1 6 7 1 4 8 1 5 8 1
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    寮�濮嬭緭鍏ヨ竟锛屽舰寮忎负(椤剁偣1鍚嶇О 椤剁偣2鍚嶇О 鏉冮噸)
    GraphList.show
    numberOfVertex = 8
    numberOfEdge = 9
    1-->2-->3
    2-->1-->4-->5
    3-->1-->6-->7
    4-->2-->8
    5-->2-->8
    6-->3-->7
    7-->3-->6
    8-->4-->5
    
    
    1->2->4->8->5->3->6->7->
    GraphList.dfs
    vertexName = [1]
    1->2->4->8->5->3->6->7->
    
    
    GraphList.bfs
    1->2->3->4->5->6->7->8->
    
    GraphList.bfs
    vertexName = [1]
    1->2->3->4->5->6->7->8->

### 初始化（对顶点的初始化和对边的初始化） ###

在处理图的初始化的时候，采用和用户进行交互的方式，采用的方式是先进行顶点初始化、然后进行边的初始化。

通过Scanner类进行初始化。

#### 顶点初始化 ####

/** * 负责图的初始化 */
        public void initializeVertex() { 
            System.out.println("GraphList.initializeVertex");
            Scanner scan = new Scanner(System.in);
            System.out.println("请输入顶点数");
            this.numberOfVertex = scan.nextInt(); // 8
    
            this.vertices = new Vertex[this.numberOfVertex];
            System.out.println("请依次输入顶点名称：");
    
            for (int i = 0; i < numberOfVertex; i++) { 
                String name = scan.next(); // 1 2 3 4 5 6 7 8
                Vertex vertex = new Vertex(name);
                vertices[i] = vertex;
            }
    
            System.out.println("顶点初始化完成");
        }

可以看到在图的内部是通过**vertices**数组来管理顶点的。

#### 边的初始化 ####

public void initializeEdge() { 
            System.out.println("GraphList.initializeEdge");
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入顶点数"); // 9
            this.numberOfEdge = scanner.nextInt();
    
    
            for (int i = 0; i < this.numberOfEdge; i++) { 
                System.out.println("开始输入边，形式为(顶点1名称 顶点2名称 权重)");
                // 此处应校验顶点名称是合法的，即用户输入的顶点在之前的初始化顶点中
                // 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1 6 7 1 4 8 1 5 8 1
                String vertex1Name = scanner.next();
                String vertex2Name = scanner.next();
                int weight = scanner.nextInt();
    
                int vertex1Index = vertexIndexByName(vertex1Name);
                int vertex2Index = vertexIndexByName(vertex2Name);
    
                Edge edge1 = new Edge(vertex2Index, weight);
                vertices[vertex1Index].add(edge1);
    
                Edge edge2 = new Edge(vertex1Index, weight);
                vertices[vertex2Index].add(edge2);
    
            }
    }
    
    	/** * @param index 根据顶点的索引号获取顶点的名称 * @return 顶点名称 */
        public String vertexNameByIndex(int index) { 
            assert index < vertices.length;
    
            return vertices[index].getVertexName();
        }
    
        /** * 根据顶点名称返回顶点的索引号 * * @param vertexName 顶点名称 * @return 返回的是边对象的标签 */
        public int vertexIndexByName(String vertexName) { 
            List<String> validVertexNames = Arrays.stream(vertices)
                    .map(vertex -> vertex.getVertexName())
                    .collect(Collectors.toList());
            assert validVertexNames.contains(vertexName);
    
            for (int i = 0; i < getNumberOfVertex(); i++) { 
                if (vertices[i].vertexName.equals(vertexName)) { 
                    return i;
                }
            }
            return -1;
        }

#### 辅助函数 ####

/** * @param index 顶点序号 * @return 返回顶点序号的第一个邻接顶点的序号 */
        public int getFirstNeighbour(int index) { 
            Edge edge = vertices[index].getAdjacentEdge();
            if ((edge != null)) { 
                return edge.getAdjacentVertex();
            }
            return -1;
        }
    
        /** * 获取index顶点，相对于currentNeighbourIndex的下一个邻接顶点 * * @param index 顶点序号 * @param currentNeighbourIndex 在顶点序号的邻接顶点的当前邻接顶点 * @return 相对于currentNeighbourIndex的，index顶点的下一个邻接顶点 */
        public int getNextNeighbour(int index, int currentNeighbourIndex) { 
            Edge edge = vertices[index].getAdjacentEdge();
    
            while (edge != null && edge.getAdjacentVertex() != currentNeighbourIndex) { 
                edge = edge.getNext();
            }
    
            edge = edge.getNext();
            if (edge == null) { 
                return -1;
            } else { 
                return edge.getAdjacentVertex();
            }
    
    
        }

### 深度优先遍历实现 ###

深度优先遍历的思想与之前一样的，无多大的区别

/** * 解决离散图像-即非连通图像的深度优先遍历 */
        public void dfs() { 
            System.out.println("GraphList.dfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
            for (int i = 0; i < getNumberOfVertex(); i++) { 
                if (!visited[i]) { 
                    dfs(i, visited);
                }
            }
    
            System.out.println();
        }
    
        public void dfs(String vertexName) { 
            System.out.println("GraphList.dfs");
            System.out.println("vertexName = [" + vertexName + "]");
    
    
            int vertex = vertexIndexByName(vertexName);
            dfs(vertex);
            System.out.println();
        }
    
        /** * 从指定顶点进行深度优先遍历，对于连通的图可以完整的遍历 * * @param vertex 开始顶点的序号 */
        public void dfs(int vertex) { 
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            dfs(vertex, visited);
            System.out.println();
        }
    
        /** * @param vertex 深度优先遍历的开始顶点所在的序号 */
        private void dfs(int vertex, boolean[] visited) { 
            System.out.print(vertices[vertex].getVertexName() + "->");
            visited[vertex] = true;
    
            int w = getFirstNeighbour(vertex);
            while (w != -1) { 
                if (!visited[w]) { 
                    dfs(w, visited);
                } else { 
                    // 如果w已经被访问过，则访问w的下一个邻接顶点
                    w = getNextNeighbour(vertex, w);
                }
    
            }
    
        }

### 广度优先代码实现 ###

/** * 从指定顶点名称开始进行广度优先遍历 * * @param vertexName 顶点名称 */
        public void bfs(String vertexName) { 
            System.out.println("GraphList.bfs");
            System.out.println("vertexName = [" + vertexName + "]");
    
            int vertex = vertexIndexByName(vertexName);
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
            System.out.println();
        }
    
        /** * 从指定顶点开始进行广度优先遍历 * * @param vertex 顶点所在的位置 */
        public void bfs(int vertex) { 
            System.out.println("GraphList.bfs");
    
            boolean[] visited = new boolean[numberOfVertex];
            Arrays.fill(visited, false);
    
            bfs(vertex, visited);
            System.out.println();
        }
    
        private void bfs(int vertex, boolean[] visited) { 
            System.out.print(vertices[vertex].getVertexName() + "->");
            visited[vertex] = true;
    
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addLast(vertex);
    
            while (!queue.isEmpty()) { 
                traverseVertex(visited, queue);
            }
    
            System.out.println();
        }
    
        /** * @param visited 访问的辅助数组 * @param queue 待访问的顶点队列 */
        private void traverseVertex(boolean[] visited, LinkedList<Integer> queue) { 
            int vertex = queue.remove();
            int neighbour = getFirstNeighbour(vertex);
    
            // 一个循环走完，就把一行走位了，在这一行中，顶点vertexIndex不变，而neighbour作为vertexIndex的邻接顶点一直在遍历
            // 然后在下一个循环中，vertexIndex更新成第一个顶点的邻接顶点了
            while (neighbour != -1) { 
                if (!visited[neighbour]) { 
                    System.out.print(vertices[neighbour].getVertexName() + "->");
                    visited[neighbour] = true;
                    queue.addLast(neighbour);
                }
                neighbour = getNextNeighbour(vertex, neighbour);
            }
        }

### 注意事项 ###

需要注意的是，无论是深度优先遍历还是广度优先遍历，对于非连通图来说，通过指定顶点进行遍历是是无法遍历完所有的顶点的。因此无论是进行深度优先遍历、还是广度优先遍历，均提供了不提供指定顶点开始的遍历方式，如下图代码所示：

# 下载 #

[下载地址][Link 1]

# 总结 #

总算是结束了对本文的撰写，2020年第25周周末，自己好像也就完成了这一个文章的撰写，其实效率很低的，换了大的显示器以后，办理了网线发现更容易看LPL了，很多的时间都花费掉了，好在周末的这两天都进行了运动，虽然雨一下一整天，但两天早晨都进行了跳绳，算是一点小小的坚持，只是体重仍然没有起色。看来想要的东西，从来没有能够简简单单就获得到的。

关于图的基础知识，先介绍到这里，之后还要进行阐述的内容包括

*  图的深度优先查找、广度优先查找
 *  最小支撑树
    
     *  普利姆算法
     *  克鲁斯卡尔算法
 *  地接斯科拉算法
 *  弗洛伊德算法

虽然读书时关于图的基础内容自己理解的深度不够，但现在韩顺平老师的数据结构的课程已经看完了，自己要趁着机会好好的总结一下。

> 2020年6月21日周日22:02:18于AUX

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621221311410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621221311837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200621221312214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[1592622289383]: https://img-blog.csdnimg.cn/20200621221312375.png
[1592622396024]: https://img-blog.csdnimg.cn/20200621221312563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200621221312984.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200621221313132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200621221313500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200621221313674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020062122131425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200621221314389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200621221314958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200621221315578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw,size_16,color_FFFFFF,t_70
[Link 1]: https://download.csdn.net/download/lk142500/12541241