图的入门

图的实际应用

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

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

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

图的定义及分类

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

特殊的图:

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

图的分类:按照连接两个顶点的边的不同,可以把图分为以下两种

  1. 无向图:边仅仅连接两个顶点,没有其他含义
  2. 有向图:边不仅连接两个顶点,并且具有方向

无向图

图的相关术语

相邻顶点:当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点

:某个顶点的度就是依附于该顶点的边的个数

子图:是一幅图的所有边的子集(包含这些边依附的顶点)组成的图

路径:是由边顺序连接的一系列的顶点组成

:是一条至少含有一条边且终点和起点相同的路径

连通图如果图中任意一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为连通图

连通子图:一个非连通图由若干连通的部分组成,每一个连通的部分都可以称之为该图的连通子图

图的存储结构

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

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

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

邻接矩阵

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

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

邻接表

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

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

图的实现

图的API设计

类名Graph
构造方法Graph(int V):创建一个包含V个顶点但不包含边的图
成员方法1.public int V():获取图中顶点的数量 2.public int E():获取图中边的数量 3.public void addEdge(int v,int w):向图中添加一条边v-w 4.public Queue adj(int v):获取和顶点v相邻的所有顶点
成员变量1.private final int V:记录顶点数量 2.private int E:记录边数量 3.private Queue[] adj:邻接表

代码实现

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

  /**
   * 获取顶点数目
   */
  public int V() {
    return V;
  }

  /**
   * 获取边的数目
   */
  public int E() {
    return E;
  }

  /**
   * 向图中添加一条边v-w
   */
  public void addEdge(int v, int w) {
    //在无向图中,边是没有方向的,所以该边可以是v-w,也可以是w-v
    adj[v].enqueue(w);
    adj[w].enqueue(v);
    //边的数量+1
    E++;
  }

  /**
   * 获取和顶点v相邻的所有顶点
   */
  public Queue<Integer> adj(int v) {
    return adj[v];
  }
}

图的搜索

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

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

深度优先搜索

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

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

API设计:

类名DepthFirstSearch
构造方法DepthFirstSearch(Graph G,int s):构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相通顶点
成员方法1.private void dfs(Graph G,int v):使用深度优先搜索找出G图中v顶点的所有相通的顶点 2.public boolean marked(int w):判断w顶点与s顶点是否相通 3.public int count():获取与顶点s相通的所有顶点的总数
成员变量1.private boolean[] marked:索引代表顶点,值表示当前顶点是否已经被搜索 2.private int count:记录有多少个顶点与s顶点相通

代码实现:

DepthFirstSearch

public class DepthFirstSearch {

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

  /**
   * 构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相邻顶点
   */
  public DepthFirstSearch(Graph G, int s) {
    //初始化marked数组
    this.marked = new boolean[G.V()];
    //初始化跟顶点s相通的顶点的数量
    this.count = 0;
    dfs(G, s);
  }

  /**
   * 使用深度优先搜索找出G图中v顶点的所有相通顶点
   */
  private void dfs(Graph G, int v) {
    //因为我搜索的是v这个顶点,所以需要先标识v为已经搜索
    marked[v] = true;
    for (Integer w : G.adj(v)) {
      //判断当前w顶点是否被搜索过,如果没有被搜索过,则递归调用dfs方法进行深度搜索
      if (marked[w] == false) {
        dfs(G, w);
      }
    }
    //因为是递归调用,所以每当我搜索到了一个新的顶点,count+1
    count++;
  }

  /**
   * 判断w顶点与s顶点是否相通
   */
  public boolean marked(int w) {
    //如果已经被搜索过了,则一定相通
    return marked[w];
  }

  /**
   * 获取与顶点s相通的所有顶点的总数
   */
  public int count() {
    return count;
  }
}

DepthFirstSearchTest

public static void main(String[] args) {
    //准备一幅图Graph对象
    Graph graph = new Graph(13);
    //图1
    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);
    //图2
    graph.addEdge(7, 8);
    //图3
    graph.addEdge(9, 11);
    graph.addEdge(9, 10);
    graph.addEdge(9, 12);
    graph.addEdge(11, 12);
    //准备深度优先搜索对象
    DepthFirstSearch search1 = new DepthFirstSearch(graph, 0);
    //测试与某个顶点相通的顶点数量
    int graph1count = search1.count();
    System.out.println("在图1中与0顶点相通的顶点的数量为:" + graph1count);
    //测试某个顶点与起点是否相通
    boolean marked5 = search1.marked(5);
    System.out.println("顶点5与顶点0是否相通" + marked5);
    boolean marked7 = search1.marked(7);
    System.out.println("顶点7与顶点0是否相通" + marked7);
  }

广度优先搜索

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

API设计:

类名BreadthFirstSearch
构造方法BreadthFirstSearch(Graph G,int s):构造广度优先搜索对象,使用广度优先搜索找出G图中s顶点的所有相邻顶点
成员方法1.private void bfs(Graph G,int v):使用广度优先搜索找出G图中v顶点的所有相邻顶点 2.public boolean marked(int w):判断w顶点与s顶点是否相通 3.public int count():获取与顶点s相通的所有顶点的总数
成员变量1.private boolean[] marked:索引代表顶点,值表示当前顶点是否已经被搜索 2.private int count:记录有多少个顶点与s顶点相通 3.private Queue waitSearch:用来存储待搜索邻接表的点

代码实现:

BreathFirstSearch

public class BreadthFirstSearch {

  /**
   * 索引代表顶点,值表示当前顶点是否已经被搜索
   */
  private boolean[] marked;
  /**
   * 记录有多少个顶点与s顶点相通
   */
  private int count;
  /**
   * 用来存储待搜索邻接表的点
   */
  private Queue<Integer> waitSearch;

  /**
   * 构造广度优先搜索对象,使用广度优先搜索找出G图中s顶点的所有相邻顶点
   */
  public BreadthFirstSearch(Graph G, int s) {
    this.marked = new boolean[G.V()];
    this.count = 0;
    waitSearch = new Queue<Integer>();
    bfs(G, s);
  }

  /**
   * 使用广度优先搜素找出G图中v顶点的所有相邻顶点
   */
  private void bfs(Graph G, int v) {
    //把当前顶点v标识为已经搜索
    marked[v] = true;
    //让v进入队列
    waitSearch.enqueue(v);
    //循环调用,如果队列不为空,则从队列中弹出一个顶点
    while (!waitSearch.isEmpty()) {
      //弹出队列的顶点
      Integer wait = waitSearch.dequeue();
      //遍历wait顶点的兄弟节点
      for (Integer w : G.adj(wait)) {
        //如果没有被搜索,对其进行搜索
        if (!marked[w]) {
          marked[w] = true;
          //将节点放入到队列尾部,用于后续获得该节点的兄弟节点
          waitSearch.enqueue(w);
          //让相通的数目+1
          count++;
        }
      }
    }
  }

  /**
   * 判断w顶点与s顶点是否相通
   */
  public boolean marked(int w) {
    return marked[w];
  }

  /**
   * 获取与顶点s相通的所有顶点的总数
   */
  public int count() {
    return count;
  }
}

BreathFirstSearchTest

public static void main(String[] args) {
    //准备一幅图Graph对象
    Graph graph = new Graph(13);
    //图1
    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);
    //图2
    graph.addEdge(7, 8);
    //图3
    graph.addEdge(9, 11);
    graph.addEdge(9, 10);
    graph.addEdge(9, 12);
    graph.addEdge(11, 12);
    //准备广度优先搜索对象
    BreadthFirstSearch search1 = new BreadthFirstSearch(graph, 0);
    //测试与某个顶点相通的顶点数量
    int graph1count = search1.count();
    System.out.println("在图1中与0顶点相通的顶点的数量为:" + graph1count);
    //测试某个顶点与起点是否相通
    boolean marked5 = search1.marked(5);
    System.out.println("顶点5与顶点0是否相通" + marked5);
    boolean marked7 = search1.marked(7);
    System.out.println("顶点7与顶点0是否相通" + marked7);
  }

案例-畅通工程续

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

在测试文件夹中有一个traffic_project.txt文件,它就是城镇道路统计表,下面是对数据的解释

总共有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号城市8号城市是否连通

代码:

Traffic_Project_Test2

public class Traffic_Project_Test2 {

  public static void main(String[] args) throws Exception {
    //构建一个缓冲读取流BufferedReader
    BufferedReader br =
        new BufferedReader(new InputStreamReader(Traffic_Project_Test2.class.getClassLoader()
            .getResourceAsStream("traffic_project.txt")));
    //读取第一行数据20
    int totalNumber = Integer.parseInt(br.readLine());
    //构建一个Graph对象,大小为20
    Graph G = new Graph(totalNumber);
    //读取第二行数据7
    int secondNumber = Integer.parseInt(br.readLine());
    //循环读取7次已经连接好的城市
    for (int i = 1; i <= secondNumber; i++) {
      //例如"0 1"
      String road = br.readLine();
      String[] s = road.split(" ");
      int v = Integer.parseInt(s[0]);
      int w = Integer.parseInt(s[1]);
      //调用Graph的addEdge方法,把边添加到图中,表示已经连接好的城市
      G.addEdge(v, w);
    }
    //构建一个深度(广度)优先搜索对象,起点城市设置为9
    BreadthFirstSearch search9 = new BreadthFirstSearch(G, 9);
    //调用一个marked方法,判断8顶点和10顶点是否与起点9相通
    System.out.println("顶点8与顶点9是否相通" + search9.marked(8));
    System.out.println("顶点10与顶点9是否相通" + search9.marked(10));
  }
}

路径查找

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

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

路径查找API设计

类名DepthFirstPaths
构造方法DepthFirstPaths(Graph G,int s):构造深度优先搜索对象,使用深度优先搜索找出G图中起点为s的所有路径
成员方法1.private void dfs(Graph G,int v):使用深度优先搜索找出G图中v顶点的所有相邻顶点 2.public boolean hasPathTo(int v):判断v顶点与s顶点是否存在路径 3.public Stack pathTo(int v):找出从起点s到顶点v的路径(就是该路径经过的顶点)
成员变量1.private boolean[] marked:索引代表顶点,值表示当前顶点是否已经被搜索 2.private int s:起点 3.private int[] edgeTo:索引代表顶点,值代表从起点s到当前顶点路径上的最后一个顶点

路径查找实现

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

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

代码实现

DepthFirstPaths

public class DepthFirstPaths {

  /**
   * 索引代表顶点,值表示当前顶点是否已经被搜索
   */
  private boolean[] marked;
  /**
   * 起点
   */
  private int s;
  /**
   * 索引代表顶点,值代表从起点s到当前顶点路径上的最后一个顶点
   */
  private int[] edgeTo;

  /**
   * 构造深度优先搜索对象,使用深度优先搜索找出G图中起点为s的所有路径
   */
  public DepthFirstPaths(Graph G, int s) {
    //初始化marked数组
    this.marked = new boolean[G.V()];
    //初始化起点s
    this.s = s;
    //初始化edgeTo数组
    this.edgeTo = new int[G.V()];
    dfs(G, s);
  }

  /**
   * 使用深度搜索优先搜索找出G图中v顶点的所有相邻顶点
   */
  private void dfs(Graph g, int v) {
    //把v标识为已经搜索
    marked[v] = true;
    //遍历顶点v的邻接表,拿到每一个相通的顶点,继续递归搜索
    for (Integer w : g.adj(v)) {
      //如果顶点w没有被搜索,则继续搜索
      if (marked[w] == false) {
        //因为是从v到w,所以edgeTo[w]的值要为v
        edgeTo[w] = v;
        dfs(g, w);
      }
    }
  }

  /**
   * 判断w顶点与s顶点是否存在路径
   */
  public boolean hasPathTo(int v) {
    return marked[v];
  }

  /**
   * 找出从起点s到顶点v的路径(就是该路径经过的顶点)
   */
  public Stack<Integer> pathTo(int v) {
    //先判断是否有路径
    if (!hasPathTo(v)) {
      //如果没有路径
      return null;
    }
    //如果有路径,则应该先创建一个栈对象,保存路径中的所有顶点,又因为是倒着存进去的,所以用栈而不用堆
    Stack<Integer> path = new Stack<>();
    //通过循环,从顶点v开始找直到找到起点s为止
    while (v != s) {
      path.push(v);
      v = edgeTo[v];
    }
    //把起点s放入到栈中
    path.push(s);
    return path;
  }
}

DepthFirstPathsTest

public static void main(String[] args) throws Exception {
    //构建缓冲读取流BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(
        DepthFirstPathsTest.class.getClassLoader().getResourceAsStream("road_find.txt")));
    //读取第一行数据6
    int total = Integer.parseInt(br.readLine());
    //根据第一行数据构建一幅图Graph
    Graph G = new Graph(total);
    //读取第二行数据8(边的数量)
    int edgeNumber = Integer.parseInt(br.readLine());
    //继续通过循环读取每一条关联的两个顶点,调用addEdge方法添加边
    for (int i = 1; i <= edgeNumber; i++) {
      //0 1
      String edge = br.readLine();
      String[] str = edge.split(" ");
      int v = Integer.parseInt(str[0]);
      int w = Integer.parseInt(str[1]);
      G.addEdge(v, w);
    }
    //构建路径查找对象,并设置起点为0
    DepthFirstPaths paths = new DepthFirstPaths(G, 0);
    //调用pathTo(4),找到起点0到终点4的路径,返回Stack
    Stack<Integer> path = paths.pathTo(4);
    StringBuilder sb = new StringBuilder();
    //遍历栈对象
    for (Integer i : path) {
      sb.append(i + "-");
    }
    sb.deleteCharAt(sb.length() - 1);
    System.out.println(sb);
  }
Last modification:July 14, 2021
If you think my article is useful to you, please feel free to appreciate