怎样在内存中实现伦敦地铁的结构?
我想这个说的就是数据结构中的图,图常用的表示方法有两种:
邻接表和邻接矩阵,都可以用来表示有向图和无向图。
我想我们这里可以假设伦敦地铁是无向图,
因为两个站点一般都是可以互相通行的。
比如地铁结构如下:
①----②-----③
| / /
| / /
| / /
⑤--④---⑥
邻接表:
①---②---⑤
②---①---④---⑥---③
③---②
④---⑤---⑥---②
⑤---④---①
⑥---②---④
如果想要在内存中实现上面的结构应该很简单吧!
邻接矩阵:
① ② ③ ④ ⑤ ⑥
① 0 1 0 0 1 0
② 1 0 1 1 0 1
③ 0 1 0 0 0 0
④ 0 1 0 0 1 1
⑤ 1 0 0 1 0 1
⑥ 0 1 0 1 0 0
内存中用二维数组就可以了。
这两者都可以用来表示图,稀疏图的时候用邻接表,稠密图的时候用邻接矩阵。