数据结构与算法之图入门(下)

简介: 数据结构与算法之图入门

3.4.2 广度优先搜索


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


68e7b2e88c284b5a9f93cf8686bab443.png


API 设计:


image.png


代码

public class BreadthFirstSearch {
  //索引代表顶点,值表示当前顶点是否已经被搜索
  private boolean[] marked;
  //记录有多少个顶点与s顶点相通
  private int count;
  //用来存储待搜索邻接表的点
  private Queue<Integer> waitSearch;
  //构造广度优先搜索对象,使用广度优先搜索找出G图中s顶点的所有相邻顶点
  public BreadthFirstSearch(Graph G, int s) {
    //创建一个和图的顶点数一样大小的布尔数组
    marked = new boolean[G.V()];
    //初始化待搜索顶点的队列
    waitSearch = new Queue<Integer>();
    //搜索G图中与顶点s相同的所有顶点
    dfs(G, s);
  }
  //使用广度优先搜索找出G图中v顶点的所有相邻顶点
  private void dfs(Graph G, int v) {
    //把当前顶点v标记为已搜索
    marked[v]=true;
    //把当前顶点v放入到队列中,等待搜索它的邻接表
    waitSearch.enqueue(v);
    //使用while循环从队列中拿出待搜索的顶点wait,进行搜索邻接表
    while(!waitSearch.isEmpty()){
      Integer wait = waitSearch.dequeue();
      //遍历wait顶点的邻接表,得到每一个顶点w
      for (Integer w : G.adj(wait)) {
        //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
        if (!marked[w]) {
          dfs(G, w);
        }
      }
    }
    //相通的顶点数量+1
    count++;
  }
  //判断w顶点与s顶点是否相通
  public boolean marked(int w) {
    return marked[w];
  }
  //获取与顶点s相通的所有顶点的总数
  public int count() {
    return count;
  }
}

3.5 案例-畅通工程续1


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


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


119125b4f44f45de88d1e80f8b7570df.png


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


解题思路:


1.创建一个图Graph对象,表示城市;

2.分别调用addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addEdge(6,10),addEdge(4,8),表示已经修建好的道路把对应的城市连接起来;

3.通过Graph对象和顶点9,构建DepthFirstSearch对象或BreadthFirstSearch对象;

4.调用搜索对象的marked(10)方法和marked(8)方法,即可得到9和城市与10号城市以及9号城市与8号城市是否相通。


代码:

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Traffic_Project2 {
  public static void main(String[] args) throws Exception {
    //创建输入流
    BufferedReader reader = new BufferedReader(new
    InputStreamReader(Traffic_Project2.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
    //读取城市数目,初始化Graph图
    int number = Integer.parseInt(reader.readLine());
    Graph G = new Graph(number);
    //读取已经修建好的道路数目
    int roadNumber = Integer.parseInt(reader.readLine());
    //循环读取已经修建好的道路,并调用addEdge方法
    for (int i = 0; i < roadNumber; i++) {
      String line = reader.readLine();
      int p = Integer.parseInt(line.split(" ")[0]);
      int q = Integer.parseInt(line.split(" ")[1]);
      G.addEdge(p, q);
    }
    //根据图G和顶点9构建图的搜索对象
    //BreadthFirstSearch search = new BreadthFirstSearch(G,9);
    DepthFirstSearch search = new DepthFirstSearch(G, 9);
    //调用搜索对象的marked(10)方法和marked(8)方法
    boolean flag1 = search.marked(10);
    boolean flag2 = search.marked(8);
    System.out.println("9号城市和10号城市是否已相通:" + flag1);
    System.out.println("9号城市和8号城市是否已相通:" + flag2);
  }
}

3.6 路径查找


在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市。这类问题翻译成专业问题就是:从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径。


d489cb6f224a496fa9250b8ccadeaf44.png


例如在上图上查找顶点 0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。


3.6.1 路径查找API设计


image.png


3.6.2 路径查找实现


根据图G和顶点9构建图的搜索对象我们实现路径查找,最基本的操作还是得遍历并搜索图,所以,我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组,这个整型数组会记录从每个顶点回到起点s的路径。如果我们把顶点设定为0,那么它的搜索可以表示为下图:


a02c007cd21544ca802cfd0ab791bf03.png


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


public class DepthFirstPaths {
  //索引代表顶点,值表示当前顶点是否已经被搜索
  private boolean[] marked;
  //起点
  private int s;
  //索引代表顶点,值代表从起点s到当前顶点路径上的最后一个顶点
  private int[] edgeTo;
  //构造深度优先搜索对象,使用深度优先搜索找出G图中起点为s的所有路径
  public DepthFirstPaths(Graph G, int s){
    //创建一个和图的顶点数一样大小的布尔数组
    marked = new boolean[G.V()];
    //创建一个和图顶点数一样大小的整型数组
    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 (Integer w : G.adj(v)){
      //如果当前顶点w没有被搜索过,则将edgeTo[w]设置为v,表示w的前一个顶点为v,并递归搜索与w顶点相通的其他顶点
      if (!marked[w]){
        edgeTo[w]=v;
        dfs(G,w);
      }
    }
  }
  //判断w顶点与s顶点是否存在路径
  public boolean hasPathTo(int v){
    return marked[v];
  }
  //找出从起点s到顶点v的路径(就是该路径经过的顶点)
  public Stack<Integer> pathTo(int v){
    //当前v顶点与s顶点不连通,所以直接返回null,没有路径
    if (!hasPathTo(v)){
      return null;
    }
    //创建路劲中经过的顶点的容器
    Stack<Integer> path = new Stack<Integer>();
    //第一次把当前顶点存进去,然后将x变换为到达当前顶点的前一个顶点edgeTo[x],在把前一个顶点存进去,继续将x变化为到达前一个顶点的前一个顶点,继续存,一直到x的值为s为止,相当于逆推法,最后把s放进去
    for (int x = v;x!=s;x=edgeTo[x]){
      //把当前顶点放入容器
      path.push(x);
    }
    //把起点s放入容器
    path.push(s);
    return path;
  }
}
//测试代码
public class DepthFirstPathsTest {
  public static void main(String[] args) throws Exception {
    //创建输入流
    BufferedReader reader = new BufferedReader(new
    InputStreamReader(DepthFirstPathsTest.class.getClassLoader().getResourceAsStream("road_find.txt")));
    //读取城市数目,初始化Graph图
    int number = Integer.parseInt(reader.readLine());
    Graph G = new Graph(number);
    //读取城市的连通道路
    int roadNumber = Integer.parseInt(reader.readLine());
    //循环读取道路,并调用addEdge方法
    for (int i = 0; i < roadNumber; i++) {
      String line = reader.readLine();
      int p = Integer.parseInt(line.split(" ")[0]);
      int q = Integer.parseInt(line.split(" ")[1]);
      G.addEdge(p, q);
    }
    //根据图G和顶点0路径查找对象
    DepthFirstPaths paths = new DepthFirstPaths(G, 0);
    //调用查找对象的pathTo(4)方法得到路径
    Stack<Integer> path = paths.pathTo(4);
    //遍历打印
    StringBuilder sb = new StringBuilder();
    for (Integer v : path) {
      sb.append(v+"-");
    }
    sb.deleteCharAt(sb.length()-1);
    System.out.println(sb);
  }
}


目录
相关文章
|
3月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
2月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
2月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
2月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
存储 机器学习/深度学习 算法
探索数据结构:入门及复杂度的解锁
探索数据结构:入门及复杂度的解锁
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_hash_t
Nginx入门 -- 基本数据结构中之ngx_hash_t
36 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
28 0
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
71 0
|
2月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)
|
4月前
|
机器学习/深度学习 人工智能 算法
AI入门必读:Java实现常见AI算法及实际应用,有两下子!
本文全面介绍了人工智能(AI)的基础知识、操作教程、算法实现及其在实际项目中的应用。首先,从AI的概念出发,解释了AI如何使机器具备学习、思考、决策和交流的能力,并列举了日常生活中的常见应用场景,如手机助手、推荐系统、自动驾驶等。接着,详细介绍了AI在提高效率、增强用户体验、促进技术创新和解决复杂问题等方面的显著作用,同时展望了AI的未来发展趋势,包括自我学习能力的提升、人机协作的增强、伦理法规的完善以及行业垂直化应用的拓展等...
190 3
AI入门必读:Java实现常见AI算法及实际应用,有两下子!