C++中无向图应该用什么数据结构存

level 1

joycao4869 楼主

我想实现一个路径搜索算法，dijstra算法的伪代码大致看懂了，但具体实现时图应该怎样表示呢？各位大虾帮帮我吧...（最好不要用链表，在下指针用得不好）

2007年03月19日 04点03分 1

level 7

Leeroy

你前面偷懒了吧，这种东西是用邻接矩阵存储的如果空间要求不高的话，直接用二维数组，i到j的权值为dist[i][j]很容易看出，这是一个下三角矩阵，所以如果数据量过大导致存储区不够用的话可以用线性表来存储这个下三角矩阵

2007年03月19日 04点03分 2

level 0

W希洛W

邻接表是我最喜欢的表示方式，两个类，一个顺序结构定死数量当然C#表示的话可以写成像Arraylist这样的动态数组，一个是可以new N个节点类

2007年03月19日 08点03分 3

level 6

zxl0714

dijstra应该用邻接表。。。邻接矩阵如果稠密图还可以。。稀疏图就不行了

2007年03月19日 10点03分 4

level 1

list<>用起来一点也不麻烦配合上priority_queue<>实现一个dijkstra算法用不上30行吧

2007年03月19日 11点03分 5