软件开发者面试百问-----怎样在内存中实现伦敦地铁的结构?

时间:2021-02-18 17:40:10

怎样在内存中实现伦敦地铁的结构?

 

我想这个说的就是数据结构中的图,图常用的表示方法有两种:
邻接表和邻接矩阵,都可以用来表示有向图和无向图。
我想我们这里可以假设伦敦地铁是无向图,
因为两个站点一般都是可以互相通行的。

比如地铁结构如下:
①----②-----③
|          / /
|         /   /
|        /     /
⑤--④---⑥
邻接表:
①---②---⑤
②---①---④---⑥---③
③---②
④---⑤---⑥---②
⑤---④---①
⑥---②---④

如果想要在内存中实现上面的结构应该很简单吧!


邻接矩阵:
    ①  ②  ③  ④  ⑤  ⑥
①  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

内存中用二维数组就可以了。

这两者都可以用来表示图,稀疏图的时候用邻接表,稠密图的时候用邻接矩阵。