图的表示方法

基本要求

1. 它必须为可能在应用中碰到的各种类型的图预留出足够的空间；
2. 图的实例方法实现一定要快。

实现选择

• 邻接矩阵
• 边的数组
• 邻接表数组

邻接矩阵

使用一个V乘V的布尔矩阵。当顶点v和顶点w之间有相连接的边时，定义v行w列的元素值为true，否则为false。这种表示方法不符合第一个条件--含有上百万个顶点的图是很常见的，V^2个布尔值所需要的空间不能满足。

边的数组

使用一个Edge类，它含有两个int实例变量。这种表示方法很简洁但不满足第二个条件--获取顶点v所有邻接顶点要检查图中所有的边。

邻接表数组

使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。这种数据结构能够同时满足上述两个条件。

邻接表数组