首先要解决的问题就是使用什么样的数据结构来表示无向图，一种方式是使用邻接矩阵，即一个大小为v*v的矩阵，当i和j之间有边连接时，则Vij为true，这种方式带来的问题就是总是需要用V^2的空间大小来表示一张有V个顶点的图，当图过大时，开销就会很大。
一种比较好的方式是使用邻接表，即使用数组来表示。将顶点的编号 0，1，2... 作为数组的索引，数组中每个位置的元素存放一个链表，链表中存储了所有与该索引的顶点相连的顶点的索引，如图所示：
可以看出，使用这种方式，对于一幅图，可能有多种不同的邻接表来表示。对于一幅V个顶点和E条边的图，空间复杂度与V+E成正比，添加一条边的时间复杂度为常数，遍历一个顶点的所有边的时间复杂度与V的度数成正比。
湘公网安备 43102202000103号