数据结构(四) 图的物理存储结构与深搜、广搜（Swift面向对象版）

开门见山，本篇博客就介绍图相关的东西。图其实就是树结构的升级版。上篇博客我们聊了树的一种，在后边的博客中我们还会介绍其他类型的树，比如红黑树，B树等等，以及这些树结构的应用。本篇博客我们就讲图的存储结构以及图的搜索，这两者算是图结构的基础。下篇博客会在此基础上聊一下最小生成树的Prim算法以及克鲁斯卡尔算法，然后在聊聊图的最短路径、拓扑排序、关键路径等等。废话少说开始今天的内容。

 

一、概述

在博客开头，我们先聊一下什么是图。在此我不想在这儿论述图的定义，当然那些是枯燥无味的。图在我们生活中无处不在呢，各种地图，比如铁路网，公路网等等这都是典型的图形结构。来点直观的，我们就以北京的地铁为例。如果你在北京坐过地铁，那么对下方的这张图并不陌生。下方就是一个典型的图形结构，而且还是连通图呢。也就是说，你从任意一个地铁站进去，就可以在其他相连的地铁站出来。

下方每个地铁站就是图的结点，地铁站与地铁站之间的连线就是图的弧，如果我们给弧添加上距离，那么这个距离就是这个弧所对应的权值。比如我们举个例子，假如大望路站到国贸站的距离是1.5公里。那么我们翻译成我们图中的术语就是大望路结点到国贸结点有一条弧，这条弧的权值是1.5公里。当然，从大望路到国贸有多条路径，那么那条路径最近呢，这就是我们后面要说的最优路径了。我们如果想连通每个站点，并且想连接每个站点的权值的和最小，那么就是我们以后要聊的最小生成树了。

今天我们博客的主题就是如果去存储下方这种类型的图，然后对图中的节点进行遍历。当然存储的时候我们要存储弧度所对应的权值。

当然，上面这个地铁站的地铁是比较复杂的，我们就简单画一个图，来模拟一下上述图的结构即可。然后将该结构进行存储。然后再基于该存储结构对图进行遍历。图的物理存储结构可以分为邻接矩阵和邻接链表的形式。则图的搜索分为广度优先搜索（BSF -- Breadth First Search）和深度优先搜索（DFS -- Depth First Search）。下面这个图的结构就是我们要存储以及遍历的图。红色的部分就是每条边的权值。

 

二、邻接矩阵

接下来我们就将上面这个图存储下来，当然是使用我们上面提到过的邻接矩阵或者邻接链表来存储。在构建图之前呢，我们依然要先定义图的协议，因为图的物理存储结构分为邻接矩阵和邻接链表。不同的存储方式也就对应着构建图的方式不同，那么图的BFS与DFS的具体实现也是不同的，但是对外的接口是一致的。还是那句话，面向接口编程。所以我们要先定义完图的相

延伸阅读

• ssh框架 2016-09-30
• 阿里移动安全 [无线安全]玩转无线电——不安全的蓝牙锁 2017-07-26
• 消息队列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
• Selective Search for Object Recognition 论文笔记【图片目标分割】 2017-07-26
• 词向量-LRWE模型-更好地识别反义词同义词 2017-07-26
• 从栈不平衡问题 理解 calling convention 2017-07-26
• php imagemagick 处理 图片剪切、压缩、合并、插入文本、背景色透明 2017-07-26
• Swift实现JSON转Model - HandyJSON使用讲解 2017-07-26
• 阿里移动安全 Android端恶意锁屏勒索应用分析 2017-07-26
• 集合结合数据结构来看看(二) 2017-07-26

学习是年轻人改变自己的最好方式