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

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

1.图的实际应用


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


地图:


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


d40a37975a754b13938207bdc115806a.png

电路图:


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


d096e2ebe32849d4a09d49d52a65c5a9.png


2.图的定义及分类


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


6429984d25a84bb6a2856adf45c65a56.png


特殊的图:


1.自环:即一条连接一个顶点和其自身的边;

2.平行边:连接同一对顶点的两条边;


9e78c0ff50a5463bbd706f759fd55793.png


图的分类:


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


无向图:边仅仅连接两个顶点,没有其他含义;

有向图:边不仅连接两个顶点,并且具有方向;


3.无向图


3.1 图的相关术语


相邻顶点:


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


度:

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


子图:

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


路径:

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


环:

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


39c097a141454c798e88ba2802f96b12.png


连通图:

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


连通子图:

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


b0a8155995e5495da585e6d6068c6bab.png

4560b077c88d4c14963a3351fb7c3aab.png

3.2 图的存储结构


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


1.图中所有的顶点;

2.所有连接顶点的边;


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


3.2.1 邻接矩阵


1.使用一个V*V的二维数组int[V][V] adj,把索引的值看做是顶点;

2.如果顶点v和顶点w相连,我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。


2303e051a7384871ba1f9012ceed92ec.png


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


3.2.2 邻接表


1.使用一个大小为V的数组 Queue[V] adj,把索引看做是顶点;


2.每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点


9018f3339fc14e85ac7f330ae00c0e53.png


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


3.3 图的实现


3.3.1 图的API设计


image.png

3.3.2 代码实现

public class Graph {
  //顶点数目
  private final int V;
  //边的数目
  private int E;
  //邻接表
  private Queue<Integer>[] adj;
  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) {
      //把w添加到v的链表中,这样顶点v就多了一个相邻点w
      adj[v].enqueue(w);
      //把v添加到w的链表中,这样顶点w就多了一个相邻点v
      adj[w].enqueue(v);
      //边的数目自增1
      E++;
    }
    //获取和顶点v相邻的所有顶点
    public Queue<Integer> adj(int v){
      return adj[v];
    }
}


3.4 图的搜索


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


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


3.4.1 深度优先搜索


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


8cecfb4133cf44a788826cf89ba5d8c9.png

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


API设计:


image.png


代码:

public class DepthFirstSearch {
  //索引代表顶点,值表示当前顶点是否已经被搜索
  private boolean[] marked;
  //记录有多少个顶点与s顶点相通
  private int count;
  //构造深度优先搜索对象,使用深度优先搜索找出G图中s顶点的所有相邻顶点
  public DepthFirstSearch(Graph G,int s){
    //创建一个和图的顶点数一样大小的布尔数组
    marked = new boolean[G.V()];
    //搜索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没有被搜索过,则递归搜索与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月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
1月前
|
机器学习/深度学习 算法 Python
机器学习入门:理解并实现K-近邻算法
机器学习入门:理解并实现K-近邻算法
36 0
|
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
43 0
|
2月前
|
存储 缓存 应用服务中间件
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
Nginx入门 -- 基本数据结构中之ngx_list_t,ngx_queue_t
39 0
|
2月前
|
存储 应用服务中间件 nginx
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
Nginx入门 -- 基本数据结构中之ngx_str_t,ngx_array_t
82 0
|
2月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)