Lonely patients

时光不回头,当下最重要。

数据结构探险之图篇(上)理论篇

数据结构探险之图篇

什么是图?

如下图:无向图 & 有向图
箭头分方向。
无向图中每条认为有来有回两条线

无向图&有向图

图中的概念:

有向图中的概念
  • 结点称为顶点。
  • 之间的线称为弧。
  • 弧尾和弧头(箭头)。
  • 从顶点发出去和射入的。
  • 出度:一个顶点发射出去的。& 入度:一个顶点射入的。

无向图中的概念
  • 顶点 & 边
  • 连线着的两个结点称为邻接点。

连通图

任意两个图之间都是直接或间接联通的。也就是存在路径

完全图

任意两个结点之间都有路径相互连接。就是完全图。

生成树

任意两个结点只有一个边,边数为n-1

图的表示法 & 图的遍历 & 最小生成树。

图的应用

图的基本概念及存储方式(一)

图的存储结构:

图的存储结构

无向图是由边 & 顶点组成的。 有向图是由弧 & 顶点组成

图的存储结构:

  • 邻接矩阵(数组)
  • 邻接表(链表)有向
  • 十字链表(链表)有向
  • 邻接多重表(链表)无向

弧尾&权值&弧头

邻接矩阵(数组)

有向图邻接矩阵

有弧用1,没弧用0。自身不能到自身

无向图邻接矩阵

主对角线对称。只记录一半

邻接矩阵定义为二维数组

顶点与图的结构体表示

顶点与图的结构体表示

邻接表-链式存储

邻接表-链式存储

通过一个顶点索引,找到出弧链表头指针。然后找到下一个节点。下一个节点又可以找到出弧。

链式存储
  • 弧指针,1代表索引。2代表索引。说明v1既有弧指向v2又有指向v3。又有指向v4。
  • v2 没有出度直接指向NULL
  • v3 有一条指向v4的弧。
  • v4 有指向v1的边。

邻接表记录出弧,逆邻接表记录入弧的
弧头改为弧尾。

数据结构代码体现:

弧代码体现
struct Map
{
    顶点数组;
};

十字链表-链式存储

十字链表表示法

十字链表弧表示

十字链表节点表示
struct Map
{
    顶点数组;
};

邻接多重表-链式存储(无向图)

邻接多重表-无向图

邻接多重表数据结构表示

图的遍历

  • 深度优先搜索
  • 广度优先搜索

图的深度 & 广度

深度:a-b-c-e-f-d-g-h(前序遍历:根左右)

去掉成环的边

广度优先搜索:一层一层搜索

丢弃两条边

不同的遍历方式形成不同的生成树。

最小生成树

权重 & 最小生成树

有a.b.c.e.f六个城市修路,权值为成本。a修到b,不如a-f-b
希望得到的结果是如右图

最小生成树算法:

  • 普里姆(Prim)算法
  • 克鲁斯卡尔(Kruskal)算法

Prim算法基本思想
  • 先有一个点的集合。这个点的集合是纳入最小生成树的点的集合,
  • 还要有一个边的集合。这个边的集合也是纳入最小生成树的边的集合
  • 待选边集合:当我们选定一个顶点,该顶点可以走的边的集合

假设从a开始做最小生成树。从a出去有三条待选边。a-b(6)、a-f(1)、a-e(5)。在待选边集合中找到权值最小的边。

a-f再次选择

将a-f所有的边都归入待选边集合中。再次选取最小权值边。

b纳入点集合

循环结果

最终点变成全集。边集合就成了最小连接边的集合。生成最小生成树。

克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法
  • 把所有边放入待选边集合中。在所有边中选取一条权值最小的边。
  • 把该边放入已选边集合中,选定了边就是选定了涉及的点。
  • 然后载待选边集合中选次小的边。f-b/d-e权值为2都可以选。
  • 判断有没有和原来的边形成闭环。形成闭环就抛弃掉该边

两个集合

选出f-d边之后。两集合变成一个集合。

要求

所有的点被涉及,并且已经纳入同一个集合。

点赞