数据结构和算法分析

图的表示方法

2018-08-12  本文已影响3人  耶也夜

基本要求

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

实现选择

邻接矩阵

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

边的数组

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

邻接表数组

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


邻接表数组
上一篇下一篇

猜你喜欢

热点阅读