数据结构与算法（十）图的入门

淩亂°似流年 2023-10-03 22:57 60阅读 0赞

## 图的实际应用 ##

在现实生活中，有许多应用场景会**包含很多点以及点点之间的连接**，而这些应用场景我们都可以用即将要学习的图这种数据结构去解决。

### 地图 ###

我们生活中经常使用的地图，基本上是由城市以及连接城市的道路组成，如果我们把城市看做是一个一个的点，把道路看做是一条一条的连接，那么地图就是我们将要学习的图这种数据结构。

![format_png][]

### 电路图 ###

下面是一个我们生活中经常见到的集成电路板，它其实就是由一个一个触点组成，并把触点与触点之间通过线进行连接，这也是我们即将要学习的图这种数据结构的应用场景。

![format_png 1][]

## 图的定义及分类 ##

> 图是由一组顶点和一组能够将两个顶点相连的边组成的。

![format_png 2][]

### 特殊的图 ###

1.  自环：即一条连接一个顶点和其自身的边；
2.  平行边：连接同一对顶点的两条边；

![format_png 3][]

### 图的分类 ###

按照连接两个顶点的边的不同（**有没有方向**），可以把图分为以下两种：

*  **无向图**：边仅仅连接两个顶点，没有其他含义；
 *  **有向图**：边不仅连接两个顶点，并且具有方向；

## 无向图的相关术语 ##

*  **相邻顶点**：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
 *  **度**：某个顶点的度就是依附于该顶点的边的个数。
 *  **子图**：是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。
 *  **路径**：是由边**顺序连接**的一系列的顶点组成。
 *  **环**：是一条至少含有一条边且终点和起点相同的路径。

![format_png 4][]

*  **连通图**：如果**图中任意一个顶点都存在一条路径到达另外一个顶点**，那么这幅图就称之为连通图。
 *  **连通子图**：一个**非连通图**由若干连通的部分组成，**每一个连通的部分**都可以称为该图的连通子图。

![format_png 5][]

## 无向图的存储结构 ##

要表示一幅图，只需要表示清楚以下两部分内容即可：

1.  图中所有的顶点；
2.  所有连接顶点的边；

常见的图的存储结构有两种：邻接矩阵和邻接表。

### 邻接矩阵 ###

1.  使用一个`V * V`的二维数组`int[V][V] adj`，把索引的值看做是顶点；
2.  如果顶点v和顶点w相连，我们只需要将`adj[v][w]`和`adj[w][v]`的值设置为1,否则设置为0即可。

![format_png 6][]

很明显，邻接矩阵这种存储方式的空间复杂度是`V^2`的，如果我们处理的问题规模比较大的话，内存空间极有可能不够用。

### 邻接表 ###

1.  使用一个大小为V的数组`Queue[V] adj`，把索引看做是顶点；
2.  每个索引处`adj[v]`存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点。

![format_png 7][]

很明显，邻接表的空间**并不是是线性级别**的，所以后面我们一直采用邻接表这种存储形式来表示图。

## 无向图的实现 ##

### 无向图的设计 ###

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th><code>Graph</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>Graph(int v)</code>：创建一个包含v个顶点但不包含边的图</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>public int v()</code>：获取图中顶点的数量<br><code>public int e()</code>：获取图中边的数量<br><code>public void addEdge(int v, int w)</code>：向图中添加一条边 v-w<br><code>public Queue&lt;Integer&gt; adj(int v)</code>：获取和顶点v相邻的所有顶点</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td><code>private final int v</code>：记录顶点数量<br><code>private int e</code>：记录边数量<br><code>private Queue&lt;Integer&gt;[] adj</code>：邻接表</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

public class Graph {
    
        /**
         * 记录顶点数量
         */
        private final int v;
    
        /**
         * 记录边数量
         */
        private int e;
    
        /**
         * 邻接表
         */
        private Queue<Integer>[] adj;
    
        /**
         * 创建一个包含v个顶点但不包含边的图
         */
        public Graph(int v) {
            // 初始化顶点数量
            this.v = v;
            // 初始化边的数量
            this.e = 0;
            // 初始化邻接表
            this.adj = new Queue[v];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new Queue<>();
            }
        }
    
        /**
         * 获取图中顶点的数量<
         */
        public int v() {
            return v;
        }
    
        /**
         * 获取图中边的数量
         */
        public int e() {
            return e;
        }
    
        /**
         * 向图中添加一条边 v-w
         */
        public void addEdge(int v, int w) {
            // 在无向图中，边是没有方向的，所以，既要将w加入v的邻接表，也要将v加入w的邻接表
            adj[v].push(w);
            adj[w].push(v);
            e++;
        }
    
        /**
         * 获取和顶点v相邻的所有顶点
         */
        public Queue<Integer> adj(int v) {
            return adj[v];
        }
    
    }
    复制代码

## 图的搜索 ##

在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相通，是非常常见的需求。

有关图的搜索，最经典的算法有**深度优先**搜索和**广度优先**搜索，接下来我们分别讲解这两种搜索算法。

### 深度优先搜索 ###

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么**先找子结点，然后找兄弟结点**。

![format_png 8][]

很明显，在由于边是没有方向的，所以，如果4和5顶点相连，那么4会出现在5的相邻链表中，5也会出现在4的相邻链表中，那么为了不对顶点进行重复搜索，应该要有相应的标记来表示当前顶点有没有搜索过，可以使用一个布尔类型的数组`boolean[V] marked`，索引代表顶点，值代表当前顶点是否已经搜索，如果已经搜索，标记为`true`，如果没有搜索，标记为`false`。

#### API设计 ####

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th><code>DepthFirstSearch</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>DepthFirstSearch(Graph g, int s)</code>：构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private void dfs(Graph g, int v)</code>：使用深度优先搜索找出G图中v顶点的所有相通顶点<br><code>public boolean marked(int w)</code>：判断w顶点与s顶点是否相通<br><code>public int count()</code>：获取与顶点s相通的所有顶点的总数</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td><code>private boolean[] marked</code>：索引代表顶点，值表示当前顶点是否已经被搜索<br><code>private int count</code>：记录有多少个顶点与s顶点相通</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

public class DepthFirstSearch {
    
        /**
         * 索引代表顶点，值表示当前顶点是否已经被搜索
         */
        private final boolean[] marked;
    
        /**
         * 记录有多少个顶点与s顶点相通
         */
        private int count;
    
        /**
         * 构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点
         */
        public DepthFirstSearch(Graph g, int s) {
            this.marked = new boolean[g.v()];
            this.count = 0;
            // 搜索G图中与顶点s相同的所有顶点
            dfs(g, s);
        }
    
        /**
         * 使用深度优先搜索找出G图中v顶点的所有相通顶点
         */
        private void dfs(Graph g, int v) {
            // 把v顶点标识为已搜索
            marked[v] = true;
            // 遍历v顶点的邻接表，得到每一个顶点w
            for (var item : g.adj(v)) {
                // 如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
                if (!marked[item]) {
                    dfs(g, item);
                }
            }
            // 相通的顶点数量+1
            count++;
        }
    
        /**
         * 判断w顶点与s顶点是否相通
         */
        public boolean marked(int w) {
            return marked[w];
        }
    
        /**
         * 获取与顶点s相通的所有顶点的总数
         */
        public int count() {
            return count;
        }
    }
    复制代码

测试代码

class DepthFirstSearchTest {
    
        @Test
        void test() {
            // 准备图
            var graph = new Graph(13);
            graph.addEdge(0, 5);
            graph.addEdge(0, 1);
            graph.addEdge(0, 2);
            graph.addEdge(0, 6);
            graph.addEdge(5, 3);
            graph.addEdge(5, 4);
            graph.addEdge(3, 4);
            graph.addEdge(4, 6);
    
            graph.addEdge(7, 8);
    
            graph.addEdge(9, 11);
            graph.addEdge(9, 10);
            graph.addEdge(9, 12);
            graph.addEdge(11, 12);
    
            var depthFirstSearch = new DepthFirstSearch(graph, 0);
    
            // 测试与某个顶点相通的数量
            assertEquals(7, depthFirstSearch.count());
    
            // 顶点5与顶点0是否相通
            assertTrue(depthFirstSearch.marked(5));
            // 顶点7与顶点0是否相通
            assertFalse(depthFirstSearch.marked(7));
        }
    
    }
    复制代码

### 广度优先搜索 ###

所谓的广度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么**先找兄弟结点，然后找子结点**。

![format_png 9][]

#### API设计 ####

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th><code>BreadthFirstSearch</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>BreadthFirstSearch(Graph g, int s)</code>：构造广度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private void bfs(Graph g, int v)</code>：使用广度优先搜索找出G图中v顶点的所有相通顶点<br><code>public boolean marked(int w)</code>：判断w顶点与s顶点是否相通<br><code>public int count()</code>：获取与顶点s相通的所有顶点的总数</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td><code>private boolean[] marked</code>：索引代表顶点，值表示当前顶点是否已经被搜索<br><code>private int count</code>：记录有多少个顶点与s顶点相通<br><code>private Queue&lt;Integer&gt; waitSearch</code>：用来存储待搜索邻接表的点</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

public class BreadthFirstSearch {
    
        /**
         * 索引代表顶点，值表示当前顶点是否已经被搜索
         */
        private final boolean[] marked;
    
        /**
         * 记录有多少个顶点与s顶点相通
         */
        private int count;
    
        /**
         * 用来存储待搜索邻接表的点
         */
        private final Queue<Integer> waitSearch;
    
        /**
         * 构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点
         */
        public BreadthFirstSearch(Graph g, int s) {
            this.marked = new boolean[g.v()];
            this.count = 0;
            this.waitSearch = new Queue<>();
    
            // 搜索G图中与顶点s相同的所有顶点
            bfs(g, s);
        }
    
        /**
         * 使用深度优先搜索找出G图中v顶点的所有相通顶点
         */
        private void bfs(Graph g, int v) {
            // 把v顶点标识为已搜索
            marked[v] = true;
    
            // 让顶点v进入待搜索队列
            waitSearch.push(v);
    
            // 使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表
            while (!waitSearch.isEmpty()) {
                var wait = waitSearch.pop();
                // 遍历wait顶点的邻接表，得到每一个顶点w
                for (var item : g.adj(wait)) {
                    // 如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
                    if (!marked[item]) {
                        bfs(g, item);
                    }
                }
            }
            // 相通的顶点数量+1
            count++;
        }
    
        /**
         * 判断w顶点与s顶点是否相通
         */
        public boolean marked(int w) {
            return marked[w];
        }
    
        /**
         * 获取与顶点s相通的所有顶点的总数
         */
        public int count() {
            return count;
        }
    }
    复制代码

测试代码

class BreadthFirstSearchTest {
    
        @Test
        void test() {
            // 准备图
            var graph = new Graph(13);
            graph.addEdge(0, 5);
            graph.addEdge(0, 1);
            graph.addEdge(0, 2);
            graph.addEdge(0, 6);
            graph.addEdge(5, 3);
            graph.addEdge(5, 4);
            graph.addEdge(3, 4);
            graph.addEdge(4, 6);
    
            graph.addEdge(7, 8);
    
            graph.addEdge(9, 11);
            graph.addEdge(9, 10);
            graph.addEdge(9, 12);
            graph.addEdge(11, 12);
    
            var breadthFirstSearch = new BreadthFirstSearch(graph, 0);
    
            // 测试与某个顶点相通的数量
            assertEquals(7, breadthFirstSearch.count());
    
            // 顶点5与顶点0是否相通
            assertTrue(breadthFirstSearch.marked(5));
            // 顶点7与顶点0是否相通
            assertFalse(breadthFirstSearch.marked(7));
        }
    
    }
    复制代码

## 案例-畅通工程 ##

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。目前的道路状况，9号城市和10号城市是否相通？9号城市和8号城市是否相通？

在我们的测试数据文件夹中有一个`trffic_project.txt`文件，它就是诚征道路统计表，下面是对数据的解释：

![format_png 10][]

总共有20个城市，目前已经修改好了7条道路，问9号城市和10号城市是否相通？9号城市和8号城市是否相通？

### 解题思路 ###

创建一个图`Graph`对象，表示城市； 分别调用`addEdge(0, 1)`，`addEdge(6, 9)`，`addEdge(3, 8)`，`addEdge(5, 11)`，`addEdge(2, 12)`，`addEdge(6, 10)`，`addEdge(4, 8)`，表示已经修建好的道路把对应的城市连接起来；

通过`Graph`对象和顶点9，构建`DepthFirstSearch`对象或`BreadthFirstSearch`对象； 调用搜索对象的`marked(10)`方法和`marked(8)`方法，即可得到9和城市与10号城市以及9号城市与8号城市是否相通。

#### 代码实现 ####

/**
     * 案例-畅通工程
     */
    @Test
    void trafficProject() throws IOException {
    	var br = new BufferedReader(new InputStreamReader(BreadthFirstSearchTest.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
    	// 读取第一行数据
    	var totalNumber = Integer.parseInt(br.readLine());
    	// 读取城市数目，初始化Graph图
    	var graph = new Graph(totalNumber);
    	// 读取第二行数据
    	var roadNumber = Integer.parseInt(br.readLine());
    
    	for (int i = 0; i < roadNumber; i++) {
    		var line = br.readLine();
    		var arr = line.split(" ");
    		var p1 = Integer.parseInt(arr[0]);
    		var p2 = Integer.parseInt(arr[1]);
    
    		// 循环读取已经修建好的道路，并调用addEdge方法
    		graph.addEdge(p1, p2);
    	}
    
    	// 根据图G和顶点9构建图的搜索对象
    	var breadthFirstSearch = new BreadthFirstSearch(graph, 9);
    	// 调用搜索对象的marked(10)方法和marked(8)方法
    	var marked10 = breadthFirstSearch.marked(10);
    	var marked8 = breadthFirstSearch.marked(8);
    
    	// 还需要12条道路才能畅通
    	LOGGER.info("9号城市和10号城市是否已相通：{}", marked10);
    	LOGGER.info("9号城市和8号城市是否已相通：{}", marked8);
    }
    复制代码

## 路径查找 ##

在实际生活中，地图是我们经常使用的一种工具，通常我们会用它进行导航，输入一个出发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。

这类问题翻译成专业问题就是：从s顶点到v顶点是否存在一条路径？如果存在，请找出这条路径。

### API设计 ###

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th><code>DepthFirstPaths</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>DepthFirstPaths(Graph g, int s)</code>：构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private void dfs(Graph g, int v)</code>：使用深度优先搜索找出G图中v顶点的所有相邻顶点<br><code>public boolean hasPathTo(int v)</code>：判断v顶点与s顶点是否存在路径<br><code>public Stack pathTo(int v)</code>：找出从起点s到顶点v的路径（就是该路径经过的顶点）</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td><code>private boolean[] marked</code>：索引代表顶点，值表示当前顶点是否已经被搜索<br><code>private int s</code>：起点<br><code>private int[] edgeTo</code>：索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

我们实现路径查找，最基本的操作还是得遍历并搜索图，所以，我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了`edgeTo[]`整型数组，这个整型数组会记录从每个顶点回到起点s的路径。

如果我们把顶点设定为0，那么它的搜索可以表示为下图：

![format_png 11][]

根据最终`edgeTo`的结果，我们很容易能够找到**从起点0到任意顶点**的路径。

public class DepthFirstPaths {
    
        /**
         * 索引代表顶点，值表示当前顶点是否已经被搜索
         */
        private final boolean[] marked;
    
        /**
         * 起点
         */
        private int s;
    
        /**
         * 索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
         */
        private final int[] edgeTo;
    
        /**
         * 构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
         */
        public DepthFirstPaths(Graph g, int s) {
            // 创建一个和图的顶点数一样大小的布尔数组
            this.marked = new boolean[g.v()];
            // 创建一个和图顶点数一样大小的整型数组
            this.edgeTo = new int[g.v()];
            // 初始化顶点
            this.s = s;
            // 搜索G图中起点为s的所有路径
            dfs(g, s);
        }
    
        /**
         * 使用深度优先搜索找出G图中v顶点的所有相邻顶点
         */
        private void dfs(Graph g, int v) {
            // 把当前顶点标记为已搜索
            marked[v] = true;
            // 遍历v顶点的邻接表，得到每一个顶点w
            for (var w : g.adj(v)) {
                // 如果当前顶点w没有被搜索过，则将edgeTo[w]设置为v,表示w的前一个顶点为v，并递归搜索与w顶点相通的其他顶点
                if (!marked[w]) {
                    // 到达顶点w的路径上的最后一个顶点是v
                    edgeTo[w] = v;
                    dfs(g, v);
                }
            }
        }
    
        /**
         * 判断v顶点与s顶点是否存在路径
         */
        public boolean hasPathTo(int v) {
            return marked[v];
        }
    
        /**
         * 找出从起点s到顶点v的路径（就是该路径经过的顶点）
         */
        public Stack<Integer> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            // 创建路径中经过的顶点的容器
            var path = new Stack<Integer>();
    
            // 通过循环，从顶点v开始，一直往前找，直到起点为止
            for (var x = v; x != s; x = edgeTo[x]) {
                path.push(x);
            }
            path.push(s);
            return path;
        }
    
    }
    复制代码

测试代码

class DepthFirstPathsTest {
    
        @Test
        void test() throws IOException {
            var br = new BufferedReader(new InputStreamReader(DepthFirstPathsTest.class.getClassLoader().getResourceAsStream("road_find.txt")));
            // 读取城市数目，初始化Graph图
            var graph = new Graph(Integer.parseInt(br.readLine()));
            // 读取城市的连通道路
            var roadNumber = Integer.parseInt(br.readLine());
            // 循环读取道路，并调用addEdge方法
            for (var i = 0; i < roadNumber; i++) {
                var arr = br.readLine().split(" ");
                var p = Integer.parseInt(arr[0]);
                var q = Integer.parseInt(arr[1]);
                graph.addEdge(p, q);
            }
    
            // 根据图G和顶点0路径查找对象
            var depthFirstPaths = new DepthFirstPaths(graph, 0);
            // 调用查找对象的pathTo(4)方法得到路径
            var path4 = depthFirstPaths.pathTo(4);
            var sb = new StringBuilder();
            for (var item : path4) {
                sb.append(item).append("-");
            }
    
            sb.deleteCharAt(sb.length() - 1);
            System.out.println("顶点0到顶点4的路径是：" + sb);
        }
    
    }

[format_png]: https://img-blog.csdnimg.cn/img_convert/74928e0de97839474d27e98ac131cbaf.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/61cc24abfd1dbc075a6d622541cf50fd.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/e846dbbfd9c30d4404fe345f1fbfa573.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/97e50b662d1131f1db8c315523767e94.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/efe071214d5899b2abfea536728ebe21.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/45b8c31d3ae0966abf764c5250370520.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/2538ade2ab0ef8c11330440c6415c8e8.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/3b1a13395554a6024e2a890561a88c98.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/7a1e7f9ec7f6402f2cc174c1cbc2f62a.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/e31bdc8a908fdb8d593c0c5dd0e3b5b4.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/e21b17fb378a624aed306085d4209ced.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/bfce0969bf81eb014ebb58ff8bec2a41.webp?x-oss-process=image/format,png