最佳的数据结构是什么来描述一个未定向多重图(优化了速度和内存)?
使用边缘列表不合适,因为在我的代码中经常需要获取顶点的邻居。
邻接表不好,因为我必须保留有关已访问边缘的信息,当访问从1到3的边缘时(假设我正在遍历1的邻居并找到导致三个权重为W的边缘),我必须在3的邻居列表中找到相同的边缘,使其标记为已访问,这是很慢的。
我考虑过邻接矩阵,其中每个单元格都是表示有关是否访问顶点,边缘重量等信息的结构
在表示多重图时,是否有任何好的方法和技术?我不想使用第三方库解决方案,如
编辑:对不起,有误解。 这是大学的练习,我只能使用Standard库来完成它。图形有约束: 0 我有32 MB的内存限制和0.5秒的时间限制(我必须使用DFS遍历)。
使用边缘列表不合适,因为在我的代码中经常需要获取顶点的邻居。
邻接表不好,因为我必须保留有关已访问边缘的信息,当访问从1到3的边缘时(假设我正在遍历1的邻居并找到导致三个权重为W的边缘),我必须在3的邻居列表中找到相同的边缘,使其标记为已访问,这是很慢的。
我考虑过邻接矩阵,其中每个单元格都是表示有关是否访问顶点,边缘重量等信息的结构
set< Edge >
. 但是,当将graph [0] [1] [i]
设置为已访问时,我无法在 graph [1] [0]
的边缘中设置相同的边缘,而无需线性搜索。在表示多重图时,是否有任何好的方法和技术?我不想使用第三方库解决方案,如
boost :: AdjacencyList
; 我必须自己编写。编辑:对不起,有误解。 这是大学的练习,我只能使用Standard库来完成它。图形有约束: 0 我有32 MB的内存限制和0.5秒的时间限制(我必须使用DFS遍历)。