Question

数据结构-图的简介

Answer 1

举个例子，微信中许许多多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构中的图(Graph)。

图，是一种比树更为复杂的数据结构，树的节点之间是一对多的关系，并且存在父与子的层级划分，而图的顶点（注意在此不叫节点）之间是多对多的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。

在图中，最基本的单元是 顶点 ，相当于树中的节点，顶点之间的关联关系，被称为 边 。

在一些图中，每一条边并不是完全等同的，使得边具有 权重 ，涉及到权重的图，称为 带权图 。

还有一些图中，顶点之间的关联并不是完全对称的，举个例子比如说微博，你的粉丝列表里有我，但我的粉丝列表里未必有你，类似于这种单方面关注的，顶点之间的边就有了方向的区分，这种带有方向的图称为 有向图 。

因此，综合有向无向、带权重不带权重，交叉来讲，图有带权重有向的、 带权重无向的 、不带权重的有向的、不带权重的无向的...

使用二维数组，表达各个顶点之间的关联关系

为了解决 邻接矩阵占用空间 的问题，人们想到了另一种图的表示方法：邻接表
在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点(在有向图中更能体现优势）

另外，其他表示方法：逆邻接表、十字链表...，在此不过多介绍了就。

即从图的某个顶点出发， 访问图中的所有顶点，且使每个顶点仅被访问一次 ，这个过程为图的遍历。
方法：BFS、DFS（具体介绍在之后章节，敬请期待。。。）