图的实际应用

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

地图

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

数据结构与算法知识点总结 数据结构与算法(1)

电路图

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

数据结构与算法知识点总结 数据结构与算法(2)

图的定义及分类

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

数据结构与算法知识点总结 数据结构与算法(3)

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

数据结构与算法知识点总结 数据结构与算法(4)

图的分类

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

  • 无向图：边仅仅连接两个顶点，没有其他含义；
  • 有向图：边不仅连接两个顶点，并且具有方向；
无向图的相关术语
  • 相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
  • 度：某个顶点的度就是依附于该顶点的边的个数。
  • 子图：是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。
  • 路径：是由边顺序连接的一系列的顶点组成。
  • 环：是一条至少含有一条边且终点和起点相同的路径。

数据结构与算法知识点总结 数据结构与算法(5)

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

数据结构与算法知识点总结 数据结构与算法(6)

无向图的存储结构

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

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

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

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

数据结构与算法知识点总结 数据结构与算法(7)

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

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

数据结构与算法知识点总结 数据结构与算法(8)

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

无向图的实现无向图的设计

类名

Graph

构造方法

Graph(int v)：创建一个包含v个顶点但不包含边的图

成员方法

public int v()：获取图中顶点的数量

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

API设计

类名

DepthFirstSearch

构造方法

DepthFirstSearch(Graph g, int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点

成员方法

private void dfs(Graph g, int v)：使用深度优先搜索找出G图中v顶点的所有相通顶点

public boolean marked(int w)：判断w顶点与s顶点是否相通

public int count()：获取与顶点s相通的所有顶点的总数

成员变量

private boolean[] marked：索引代表顶点，值表示当前顶点是否已经被搜索 private int count：记录有多少个顶点与s顶点相通

代码实现

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)); } }

广度优先搜索

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

数据结构与算法知识点总结 数据结构与算法(9)

API设计

类名

BreadthFirstSearch

构造方法

BreadthFirstSearch(Graph g, int s)：构造广度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点

成员方法

private void bfs(Graph g, int v)：使用广度优先搜索找出G图中v顶点的所有相通顶点

public boolean marked(int w)：判断w顶点与s顶点是否相通

public int count()：获取与顶点s相通的所有顶点的总数

成员变量

private boolean[] marked：索引代表顶点，值表示当前顶点是否已经被搜索 private int count：记录有多少个顶点与s顶点相通

private Queue<Integer> waitSearch：用来存储待搜索邻接表的点

代码实现

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号城市是否相通？

新建一个traffic_project.txt文件，内容如下：

20 7 0 1 6 9 3 8 5 11 2 12 6 10 4 8

它就是诚征道路统计表，下面是对数据的解释：

数据结构与算法知识点总结 数据结构与算法(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); // 9号城市和10号城市是否已相通：true LOGGER.info("9号城市和10号城市是否已相通：{}", marked10); // 9号城市和8号城市是否已相通：false LOGGER.info("9号城市和8号城市是否已相通：{}", marked8); }

测试结果：

9号城市和10号城市是否已相通：true 9号城市和8号城市是否已相通：false

路径查找

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

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

API设计

类名

DepthFirstPaths

构造方法

DepthFirstPaths(Graph g, int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径

成员方法

private void dfs(Graph g, int v)：使用深度优先搜索找出G图中v顶点的所有相邻顶点

public boolean hasPathTo(int v)：判断v顶点与s顶点是否存在路径

public Stack pathTo(int v)：找出从起点s到顶点v的路径（就是该路径经过的顶点）

成员变量

private boolean[] marked：索引代表顶点，值表示当前顶点是否已经被搜索 private int s：起点

private int[] edgeTo：索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点

代码实现

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

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

数据结构与算法知识点总结 数据结构与算法(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); } }

测试结果：顶点0到顶点4的路径是：0-2-3-4

,
上一篇下一篇

最新推荐

热门推荐

© 2024 秒懂生活
站务投诉邮箱：anhduc.ph@yahoo.com