图
图是一种网状的结构，它是数据结构中最复杂的元素，可以有很多种表达方式。从面向对象的思想出发，一个对象只要能对外界提供它对应的功能，而不必拘泥其内存中的表达方式。
对于一个图，我们经常有哪些访问要求呢？最常见的问题就是一个顶点到底连接了哪些边，一个边连接了哪些顶点，一个顶点相邻的顶点是谁，一个边相邻的边是谁，等等。如果我们能回答这些问题，那么它内存的表示，如何存储并不是十分关键。
图我们可以采用多种表示方式：
邻接矩阵
image.png
可以使用邻接矩阵的方式来表示上边的图
0 1 1 1 0
1 0 1 1 1
1 1 0 0 0
1 1 0 0 0
0 1 0 0 0
邻接矩阵的表示比较直观 易理解，比如下图中邻接矩阵第二行，它表示为节点1对应的邻接节点关系，0代表未连接，除了与它自己以外的所有节点都有连接。
image.png
对于无向图，邻接矩阵是关于主对角线对称的。
邻接矩阵是以顶点为中心的表达法，如果要回答一些关于边的问题就要稍稍吃力了。
邻接表
假如我们图比较稀疏，顶点又非常的多，那使用邻接矩阵就太浪费内存了。这种情况下我们就可以采用邻接表的形式
image.png
看上边的这个图，每个顶点都指向了一个链表，表示与它关联的顶点，这种表达方式就十分节约内存。从一个顶点出发，可以很容易找到它相邻顶点。
网友评论