系统学习图像算法Day.15——数据结构学习——“图”

迷南。 2023-08-17 16:00 37阅读 0赞

————————————————————————————————————————————————————————————

这不要放长假了吗，这不要要篮球比赛了吗，好多的乐趣超过学习枯燥的算法，选择“学”？、选择“娱乐”？ 放心我并不会为了某一个而牺牲另一个，因为我并不认为他们冲突，生活嘛，可以暂时性偏重哪一项，但永远不会放弃做自己喜欢的事。

来吧，上“图”

# 图 #

照例，先简要了解几个问题  
什么是“图”？  
为什么构件“图”这个ADT？  
有哪几类图？  
涉及哪些经典算法？  
有哪些专业术语？  
有哪些应用？

## 什么是图 ##

**定义**：一个图（graph）G=（V,E），其中V表示顶点集，E表示边集。  
**本质上**：表示“多对多”的关系  
**“图”ADT**：

> 类型名称：图（Graph）   
> 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。   
> 操作集：对于任意图G Graph，以及v V, e E  Graph Create()：建立并返回空图；   
> Graph InsertVertex(Graph G, Vertex v)：将v插入G；   
> Graph InsertEdge(Graph G, Edge e)：将e插入G；   
> voidDFS(Graph G, Vertex v)：从顶点v出发深度优先遍历图G；   
> voidBFS(Graph G, Vertex v)：从顶点v出发宽度优先遍历图G；   
> voidShortestPath(Graph G, Vertex v, intDist\[\])：计算图G中顶点v到任意其他顶点的最短距离；   
> voidMST(Graph G)：计算图G的最小生成树；

## 为什么构建“图”这个ADT？ ##

构建一个ADT肯定是为了解决问题的，图的作用可以应用在许多的场景，比如各城市之间的铁路线，地铁线路，这些都可以抽象为图的问题，然后利用图的一些算法进行求取“最短路径”、“最省钱的修路方法”等等。于是，咱们先把“图”这个ADT搭建起来，然后进行研究

## 有哪几类图？ ##

有向图  
无向图  
临接矩阵  
临接表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center]  
————————————————————————————————————————————————————————————————————————————————  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 1]  
————————————————————————————————————————————————————————————————————————————————  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 2]

## “图”ADT有哪些经典的操作、涉及哪些经典算法？ ##

首先咱们一起看看“图”的**遍历**

> 有两种经典算法：  
> 深度优先搜索（Depth First Search, DFS）、广度优先搜索(Breadth First Search, BFS)

DFS:  
类似于树的先序遍历  
*Tips:一招记住先、中、后序遍历（先：根左右、中：左根右、后：左右根）*

> void DFS ( Vertex V ) 
    {  
    visited[ V ] = true;  
        for( V 的每个邻接点W )
            if( !visited[ W ] )
                DFS( W ); 
    }

BFS  
：就是一层一层的访问

voidBFS ( Vertex V ) 
    {  
       visited[V] = true;
       Enqueue(V, Q); 
      while(!IsEmpty(Q))
          {  
             V = Dequeue(Q); 
            for( V 的每个邻接点W ) 
               if( !visited[W] ) 
                  { 
                      visited[W] = true; 
                      Enqueue(W, Q); 
                  }
            }
     }

## 有哪些专业术语？ ##

连通：如果从V到W存在一条（无向）路径，则称 V和W是连通的  
路径：V到W的路径是一系列顶点\{V, v1, v2, …, vn, W\}的集合，其中任一对相邻的顶点间都有图 中的边。路径的长度是路径中的边 数（如果带权，则是所有边的权重和）。如果V到W之间的所 有顶点都不同，则称简单路径 。  
回路：起点等于终点的路径   
连通图：图中任意两顶点均连通  
连通分量：无向图的极大连通子图 

> 连通分量需满足： 极大顶点数：再加1个顶点就不连通了  极大边数：包含子图中所有顶点相连的所有边

## 应用 ##

最短路径问题：  
一些基本概念：

> 在网络中，求两个不同顶点之间的所有路径 中，边的权值之和最小的那一条路径 ，  
> 这条路径就是两点之间的**最短路径（Shortest Path） **  
> 第一个顶点为源点（Source）  最后一个顶点为终点（Destination）

将最短路径问题分类的话:

> 也就是：有权图、无权图、有向、无向、单源、多源， 排列组合  
> 比如：无权图中的——无向单源最短路径、有向单源最短路径…

**常见的经典算法**

*无权图的单源最短路算法*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 3]

void Unweighted ( Vertex S )
     { 
         Enqueue(S, Q); 
         while(!IsEmpty(Q))
               {  
                   V = Dequeue(Q);
                  for( V 的每个邻接点W )
                      if( dist[W]==-1  ) 
                          {  
                             dist[W] = dist[V]+1; 
                             path[W] = V; 
                             Enqueue(W, Q);
                          }
                } 
    }

*有权图的单源最短路算法*

不多讲， Dijkstra算法 ， 自己看去

*有权图的多源最短路算法*

Floyd 算法

拓扑排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 4]

一些基本概念：

> **拓扑序**：如果图中从V到W有一条有向路径， 则V一定排在W之前。满足此条件的顶点序列 称为一个拓扑序   
> 获得一个拓扑序的过程就是拓扑排序   
> AOV如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph, DAG）

其他的算法层面的东西先不作展开，后续补。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230810/3be999170cc54357b2e6543e1addbcbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230810/ef9cd1b63e7c4892b260b8852e37af26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230810/b80ac684d6814db3b715cdc97c52155a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230810/83658a64ab594455a62d06321529fa0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230810/77c4b14d7ca74054b2ee4dfede7aa7f9.png