首页 > 编程语言 >图的数据结构及基础算法

图的数据结构及基础算法

时间:2023-11-03 09:24:16浏览次数:45  
标签:end int 基础 邻接矩阵 算法 顶点 数据结构 adj 节点

图(Graph)这个数据结构在平时开发中遇到的比较少,但我认为它是十分重要的,因为从真实的世界中来看,很多东西都可以抽象为图的表示,比如人际关系,地理位置,天马行空的东西都可以抽象为图,所以它比链表等基础数据结构高级一点点,也比较复杂,属于非线性结构。数学中有一个图论的分支也是与其有关。了解图在程序世界的存储方式,我们可以更加细致地刻画图的结构,让其为我所用,岂不妙哉?

定义和分类

那么图的定义是什么呢?我们直接看维基百科:

一张图 $G$ 是一个二元组$(V,E)$,其中$V$称为顶点集,$E$称为边集。它们亦可写成$V(G)$和$E(G)$。 $E$的元素是一个二元组数对,用$(x,y)$表示,其中${x,y} \in V$。

下面一个图的示例:

image

图中的元素被称为顶点(Vertex),顶点与顶点之间连线被称为(Edge),每个顶点有多少连线被称称为(Degree),比如a图的2节点,度为2。

图(a)顶点与顶点之间的边没有方向,这种图被称为无向图(Undirected graph),在现实中,一个顶点与另一个顶点之间也可以是有向的,比如我们熟悉的铁路网等,从一个地方到一个地方,必然是有指向的,这种叫有向图(Directed graph),如图(b)所示。当然一个更常见的场景,比如北京到上海的距离肯定比上海到苏州的距离长,如何描述边与边的权重呢?这种图被称为带权图(Weighted graph),1顶点到2顶点边的权重为1。这里的权重只是抽象出的概念,在现实中可根据不同场景代表不同的含义,比如距离,车票价格等。

有向图中,指向这个顶点的边和从其出发的边是不一样的,所以用出度(Out-degree)和入度(In-degree)来具体描述顶点的度。出度指的是有多少边是从当前顶点出发指向其他顶点;入度指的是有多少边指向当前顶点。对于图(b)而言,1节点的出度和人度都是1。

当然图是有很多的概念,上面是最基本的,了解了这些,我们才可以探讨图在代码中如何表示(以无向图示例)。

存储表示

根据维基百科的介绍,图有如下存储表示:

  • 邻接矩阵(Adjacency matrix)
  • 邻接表(Adjacency list)
  • 前向星
  • 有向图的十字链表
  • 无向图的邻接多重表

本文以邻接矩阵和邻接表为例,后面几种再单独探讨。

邻接矩阵

大学学过线性代数的同学对矩阵可能还有点印象,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,映射到编程语言是二维数组。

对于上图(a)而言,该图是一个无向不加权图,在矩阵中,其中的元素初始值都是0,我们规定从一个顶点i到另一个顶点j如果有边,这两个顶点对应的矩阵位置G(i, j) 和 G(j, i) 的值记为1,由于是无向图,可能会映射到两个元素,下面是图(a)的邻接矩阵表示:

$$
\begin{bmatrix}
0 & 1 & 0 & 1 \
1 & 0 & 1 & 0 \
0 & 1 & 0 & 1 \
1 & 0 & 1 & 0 \
\end{bmatrix}
$$

对于图(b),这是个有向不加权图,我们规定,,其中的元素初始值都是0,从一个顶点i指向另一个顶点j,这两个顶点对应的矩阵位置G(i, j)的值记为1,图(b)的邻接矩阵表示为:

$$
\begin{bmatrix}
0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 1 \
0 & 0 & 0 & 0 \
\end{bmatrix}
$$

对于图(c),这是个无向加权图,我们规定,元素初始值都是0,从一个顶点i到另一个顶点j如果有边,这两个顶点对应的矩阵位置G(i, j) 和 G(j, i) 的值记为该边的权重值,所以图(c)的邻接矩阵表示为:

$$
\begin{bmatrix}
0 & 1 & 0 & 2 \
1 & 0 & 2 & 0 \
2 & 0 & 0 & 5 \
2 & 0 & 5 & 0 \
\end{bmatrix}
$$

从上面的几个邻接矩阵来看,用邻接矩阵来表示图还是很方便的,虽然简单,但却有很大问题,假设现在图G有n个顶点,需要开辟$n^2$个空间,并且很多空间都没有存储值,白白被浪费掉了。所以用邻接矩阵来表示图还是需要考虑考虑的。

用邻接矩阵来表示图代码也很简单,我们需要声明一个二维数组:

  // 邻接矩阵
  private int[][] adjacencyMatrix;

接下来要做的一个操作是添加边,首先要知道起始顶点的位置和目标顶点的位置,无向图两个位置都要赋值为1,代码如下:

  /**
   * 添加边
   *
   * @param start 起始节点位置
   * @param end   结束节点位置
   */
  public void addEdge(int start, int end) {
    checkPosition(start);
    checkPosition(end);

    this.adjacencyMatrix[start][end] = 1;
    this.adjacencyMatrix[end][start] = 1;
    this.edgeSize++;
  }

下面是完整代码:

/**
 * 无向图 - 基于邻接矩阵(adjacency matrix)
 *
 * @author hanjuntao
 */
public class AMUndiGraph implements Graph {

  /**
   * 邻接矩阵长或宽最大长度
   */
  private static final int maxSideLength = 4;
  // 邻接矩阵长或宽长度
  private int sideLength;
  // 邻接矩阵
  private int[][] adjacencyMatrix;
  // 节点数目
  private int nodeSize;
  // 边数量
  private int edgeSize;

  public AMUndiGraph() {
    this(maxSideLength);
  }

  public AMUndiGraph(int sideLength) {
    if (sideLength <= 0) {
      throw new IllegalArgumentException("The sideLength [" + sideLength + "] is not valid number");
    }

    this.sideLength = sideLength;
    adjacencyMatrix = new int[sideLength][sideLength];
  }

  /**
   * 添加边
   *
   * @param start 起始节点位置
   * @param end   结束节点位置
   */
  public void addEdge(int start, int end) {
    checkPosition(start);
    checkPosition(end);

    if (this.adjacencyMatrix[start][end] == 0 && this.adjacencyMatrix[end][start] == 0) {
      this.adjacencyMatrix[start][end] = 1;
      this.adjacencyMatrix[end][start] = 1;
      this.edgeSize++;
    }
  }

  /**
   * 获取节点数量
   *
   * @return 节点数量
   */
  @Override
  public int getNodeSize() {
    int currNodeSize = 0;

    for (int i = 0; i < sideLength; i++) {
      for (int j = 0; j < i + 1; j++) {
        if (adjacencyMatrix[i][j] == 1) {
          currNodeSize++;
        }
      }
    }

    return currNodeSize;
  }

  /**
   * 获取边的数量
   *
   * @return 边的数量
   */
  @Override
  public int getEdgeSize() {
    return this.edgeSize;
  }

  private void checkPosition(int index) {
    if (index < 0 || index >= adjacencyMatrix.length) {
      throw new IllegalArgumentException("The index [" + index + "] is not valid number");
    }
  }

  @Override
  public String toString() {
    return "AMUndiGraph{" +
        "sideLength=" + sideLength +
        ", adjacencyMatrix=" + Arrays.deepToString(adjacencyMatrix) +
        ", nodeSize=" + nodeSize +
        ", edgeSize=" + edgeSize +
        '}';
  }
}

邻接表

用邻接矩阵表示图代码很简单,计算也很方便,如果边比较密集,还是可以考虑的。可以不可以不要二维数组只要一维数组表示图呢?知道散列表的拉链法的同学比较清楚当一个key出现哈希冲突时,会存到链表里面,邻接表与这个类似,我们需要一个一维数组来保存所有的顶点,每一个顶点对应一个链表,存储所以与该顶点存在边的顶点。当我们需要判断一个顶点与另一个顶点是否存在边时,我们可以定位到这个顶点,然后遍历其链表看看有没有另一个顶点即可。如下图所示:

image

首先我们声明邻接表:

// 邻接表
private LinkedList<Integer>[] adj;

接着需要添加边,对于无向图,我们只需要将目标顶点放入到顶点对应的链表中就行了,代码如下:

public void addEdge(int start, int end) {
  checkPosition(start);
  checkPosition(end);
  adj[start].add(end);
  adj[end].add(start);
  this.edgeSize++;
}

完整代码如下:

/**
 * 无向图 - 基于邻接表(adjacency list)
 *
 * @author hanjuntao
 */
public class AJUndiGraph implements Graph {
  // 邻接表
  private LinkedList<Integer>[] adj;
  // 边数量
  private int edgeSize;

  public AJUndiGraph(int arrSize) {
    if (arrSize <= 0) {
      throw new IllegalArgumentException("The arrSize [" + arrSize + "] is not valid number");
    }

    adj = new LinkedList[arrSize];
    for (int i = 0; i < arrSize; i++) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int start, int end) {
    checkPosition(start);
    checkPosition(end);

    adj[start].add(end);
    adj[end].add(start);
    this.edgeSize++;
  }

  private void checkPosition(int index) {
    if (index < 0 || index >= adj.length) {
      throw new IllegalArgumentException("The index [" + index + "] is not valid number");
    }
  }

  @Override
  public int getNodeSize() {
    return adj.length;
  }

  @Override
  public int getEdgeSize() {
    return this.edgeSize;
  }

  @Override
  public String toString() {
    return "AJUndiGraph{" +
        "adj=" + Arrays.deepToString(adj) +
        ", nodeSize=" + getNodeSize() +
        ", edgeSize=" + edgeSize +
        '}';
  }
}

广度和深度优先搜索

广度优先搜索

广度优先搜索(Breadth-First-Search)被称为bfs,是一种比较好理解的图搜索方式,从图的一个顶点开始,向外一层一层地搜索。对于这种搜索,我们需要记录当前的节点是否被访问过,以及标识层次访问的情形。所以我们用一个数组记录节点是否被访问过,用一个队列来记录每一层的顶点。下面提供一个无向图,我们想要搜索到值为7的节点,如下图所示:

image

首先我们访问值为1的节点,我们需要先将1节点入队。节点1相当于下一层的顶点,该层只有1这个节点,接下来将1节点出队,访问1的第二层的节点。接着访问该层的所有节点,包括2,3,4,并依次入队。

image

第二层访问完毕,接下来我们要访问第三层。先从队列中取出2节点,访问2节点的下一层节点,图中只有5节点,该节点没有被访问过,将节点5加入到队列中。接着分别访问3节点和4节点的下一层节点,操作同上。

image

第三层节点访问完毕,接下来访问第四层节点,从队列中取出节点5,访问其下一层节点7,发现是我们要搜索的,搜索结束。

image

通过上面的图片演示,我们已经对bfs有一个大致的印象,下面我们来详细总结下bfs的搜索过程:

  1. 初始一个队列用来记录待访问节点的顶点,初始一个数据用来节点是否被访问过;将起始节点入队;
  2. 将队列中的队首元素出队,访问其连接的下一层节点,并将访问过的节点入队;
  3. 重复第二步,直至搜索到终止节点。

下面我们通过用领接表来表示无向图实现bfs,代码很容易读,至于如何利用广度优先搜索寻找起始节点和终止节点的最短路径,下一篇文章再系统讨论。bfs代码如下:

  /**
   * 广度优先搜索 Breadth-First-Search
   *
   * @param s 起始顶点
   * @param t 终止顶点
   */
  public void bfs2(int s, int t) {
    int len = adj.length;
    // 记录节点是否被访问过
    boolean[] visited = new boolean[len];

    // 存储每一层的顶点
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty()) {
      Integer vertex = queue.poll();
      for (int i = 0; i < adj[vertex].size(); i++) {
        Integer curr = adj[vertex].get(i);
        if (!visited[curr]) {
          visited[curr] = true;
          System.out.println("当前顶点:" + vertex + ",当前节点:" + curr);

          if (curr == t) {
            return;
          }

          queue.add(curr);
        }
      }
    }
  }

深度优先搜索

深度优先搜索(Depth-First-Search)被称为dfs,和广度优先搜索是截然不同的搜索算法,在深度优先搜索中,假设沿着某条路径可以找到想要的节点,那么就一直走下去,如果目标不存在,那么就返回上一个节点,重复以上步骤,直至匹配到目标或遍历整个图。

从上面的描述来看,很明显是用到了递归,这里的递归终止条件有两个:

  1. 匹配到目标,遍历结束
  2. 遍历整个图,遍历结束

bfs伪代码(图的存储结构采用邻接表)如下:

visited[]; 

dfs = (s, t) {
    visited[s] = true;
    if (match) {
        return;
    }
    
    for i : adj[s]
        if (!visited[i]) {
            visited[i] = true;
            dfs(i, t)
        }
}

同广度优先搜索类似,我们也需要一个数组记录图中的节点是否被访问过,如果被访问过,那么就需要跳过,感觉有点点回溯法的味道,这里确实用到了回溯的思想。

  /**
   * 深度优先搜索 Depth-First-Search
   *
   * 打印走过的路径
   *
   * @param s 起始顶点
   * @param t 终止顶点
   */
  public void dfs(int s, int t) {
    int len = adj.length;
    boolean[] visited = new boolean[len];
    recurDfs(s, t, visited);
  }

  private void recurDfs(int vertex, int t, boolean[] visited) {
    visited[vertex] = true;
    if (vertex == t) {
      return;
    }

    for (int i = 0; i < adj[vertex].size(); ++i) {
      int curr = adj[vertex].get(i);
      if (!visited[curr]) {
        System.out.println("当前顶点:" + vertex + ",当前节点:" + curr);
        recurDfs(curr, t, visited);
      }
    }
  }

References:


title: 图的数据结构及基础算法
tags: [数据结构, 图]
author: Mingshan
categories: [数据结构, 图]
date: 2020-01-19
mathjax: true

标签:end,int,基础,邻接矩阵,算法,顶点,数据结构,adj,节点
From: https://www.cnblogs.com/mingshan/p/17793538.html

相关文章

  • HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT - 基于双数组字典树的AC自动机
    双数组字典树能在O(1)(1是模式串长度)时间内高速完成单串匹配,并且内存消耗可控,然而软肋在于多模式匹配。如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配。比如ushers、shers、hers…这样一份文本要回退扫描多遍,性能较低。既然AC自动机的goto表本身就是一......
  • 【算法】十一月阳光下的阴影面积
    十一月的阳光透过窗户,照射在一位笑起来甜美、青春洋溢的女子的办公桌上。小悦,一个总是以高马尾造型亮相的软件工程师,展现出她的干练与活力。那乌黑亮丽的长发轻盈飘动,仿佛在诉说着她的独特魅力。她的眉眼如画,那双明亮的眼睛里闪烁着对知识的渴望和对技术挑战的热情。这一天,她收到......
  • JAVA基础
    打开CMD的方式1.开始+系统+命令指示符2.win+r(输入cmd)打开控制台3.在任意的文件夹下面按住(shift)+鼠标右键点击,在此处打开命令窗口4.资源管理器的地址栏前面加上cmd路径5.管理员方式运行(开始-windows系统-命令提示符-鼠标右键更多-管理员方式运行常用dos命令1.盘符切换:英......
  • 查找附近店铺(Redis GEO数据结构实现)
    附近店铺(RedisGEO数据结构实现)GEO数据结构GEO就是Geolocation的简写形式,代表地理坐标。Redis在3.2版本中加入了对GEO的支持,允许存储地理坐标信息,帮助我们根据经纬度来检索数据。常见的命令有:GEOADD:添加一个地理空间信息,包含:经度(longitude)、纬度(latitude)、值(member)GEO......
  • 数据结构笔记
    数据结构刷题笔记Points线段树显然先对\(x\)离散用线段树维护区间最大值,查询在线段树上二分出最小的\(x\)用set维护每个\(x\)对应的\(y\),lower_bound即可......
  • 操作系统实验——进程管理的算法实现
    前言笔者在大学下属的事业单位上班,最近去帮着带下操作系统的实验课,这里随手水点参考代码,欢迎各位领导老师莅临指正实验目标编写一个简单的进程调度器实验内容进程控制块(PCB)的定义与管理进程调度算法的实现进程创建、销毁和切换给定一批进程对比3-4种调度算法的时间(自选算......
  • Java 基础篇day05
    面向对象编程世间万物皆对象,在Java的观念中,把一切都看作对象,但是你操纵的确是一个对象引用。在Java中一旦创建了一个引用,就希望它能与一个新的对象继续关联,通常使用new操作符来实现这一目的。new的意思是,给我一个新对象,如果你不想相亲,自己new一个对象就好了,祝你下辈子幸福对象本......
  • 2023-2024-1 20231320 《计算机基础与程序设计》第六周学习总结
    2023-2024-120231320《计算机基础与程序设计》第六周学习总结作业信息这个作业属于哪个课程<班级的链接>(2023-2024-1计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(2022-2023-1计算机基础与程序设计第六周作业)这个作业的目标<自学《计算机基础与......
  • 自增主键与雪花算法的优缺点、设计更适合分库分表的UUID算法
    (目录)为什么不推荐使用自增主键递增主键的作用我们在数据库里保存的数据就跟excel表一样,一行行似的而在底层,这一行行数据,就是保存在一个个16k大小的页里。每次都去遍历所有的行性能会不好,于是为了加速搜索,我们可以根据主键id,从小到大排列这些行数据,将这些数据页用双向链表......
  • 关于“聚类算法”
        今天我在csdn上看到一篇文章关于聚类算法的文章。我了解到聚类算法是一类无监督学习的算法,用于将数据集中的对象按照相似性进行分组或聚集。聚类算法的目标是将相似的数据点归为一类,同时将不相似的数据点分开。        常见的聚类算法包括:1.K-means聚类算法。......