我敢说，这图绝对跟你想象中的不太一样！

阅读本文大概需要6分钟

我没骗你们，这个图的确不是你想象中的图。你想看什么图我还不知道？不过，我的图却是大千世界，继续以通俗易懂的方式给你提升一波内功。不信你继续往下读。

图是一种与树有些相像的数据结构，实际上，从数学意义上说，树是图的一种。然而在计算机程序设计中，图的应用方式与树不同。

我前面一些文章中讨论的数据结构都有一个框架，这个框架都是由相应的算法设定的。比如说，二叉树是那样一个形状，就是因为那样的形状使它更容易搜索数据和插入新数据，树的边表示了从一个节点到另一个节点的快捷方式。而图通常也有一个固定的形状，这是由物理或抽象的问题所决定的。比如说，图中节点表示城市，而边表示城市间的航班线，这些都是固定的。即，图的形状取决于真实世界的具体情况。在图中，我们称节点为顶点。

在大多数情况下，顶点表示某个真实世界的对象，这个对象必须用数据项来描述。例如顶点代表城市，那么它需要存储城市名字、海拔高度、地理位置等相关信息。因此通常用一个顶点类的对象来表示一个顶点。这里我们仅仅在顶点中存储了一个字母来标识顶点，同时还有一个标志位，用来判断该顶点有没有被访问过。

顶点对象能放在数组（这里用vertexList数组）中，然后用下标指示，也可以放在链表或其他数据结构中，但不论使用什么数据结构，存储只为了使用方便，这与边如何连接点没有关系。

前面提到的树的表示中，大多数情况下都是每个节点包含它的子节点的引用，也可以用数组表示树，数组中的节点位置决定了它和其他节点的关系，比如堆。然而，图并不像树那样拥有几种固定的结构，因为图的每个顶点可以与任意多个顶点连接。为了模拟这种自由形式的组织结构，需要用一种不同的方法表示边，一般用两种方式：邻接矩阵和邻接表。

邻接矩阵是一个二维数组，里面的数据表示两点间是否存在边。如果图有N个顶点，那么邻接矩阵就是N*N的数组，如下表所示：1表示有边，0表示没有边，也可以用true和false来表示。

邻接表是一个链表数组（或者链表的链表），每个单独的链表表示了有哪些顶点与当前顶点邻接，如下表所示：A邻接顶点有B、C和D。

下面讨论下图中的搜索。在图中实现的基本操作之一就是搜索从一个定到可以到达其他哪些顶点，或者找所有当前顶点可到达的顶点。有两种常用的方法可用来搜索图：深度优先搜索（DFS）和广度优先搜索（BFS），它们最终都会到达所有的连通顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。具体的见下面的程序：

其中StackX和QueueX类的代码如下：

图中还有个最小生成树的概念，所谓最小生成树，就是用最少的边连接所有的顶点。对于给定的一组顶点，可能又很多种最小生成树，但是最小生成树边E的数量总是比顶点V的数量小1，即E=V-1。寻找最小生成树不需要关心边的长度，并不需要找到一条最短路径，而是要找最少数量的边（最小路径在带权图中讨论）。

创建最小生成树的算法与搜索算法几乎是相同的，它同样可以基于广度优先搜索和深度优先搜索，这里使用深度优先搜索。在执行深度优先搜索的过程中，如果记录走过的边，就可以创建一棵最小生成树，可能会感到有点奇怪。见下面的程序（是上面Graph类中的一个方法，加到Graph类中即可）：

好嘞，我的图就说这么多嘞，文章建议收藏，在等公交、吃饭排队的时候可以拿出来读一读，提升一波内功。利用碎片化时间来学习。

END

●编号753，输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《18个技术类公众微信》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。