我目前正在研究C++中的有向图数据结构(此项目没有Boost GL).主要应用程序将识别连接的组件和接收器.预计图形是稀疏的(数字边缘的E~4V上限)并且都是均匀的权重.我试图在邻接列表,发生率列表或可能还有其他我尚未听说过的表示之间做出决定(adj.矩阵不是稀疏性的选项bc).瓶颈可能是整体空间和图形初始化的速度:图形将从潜在的巨大阵列初始化,使得阵列中的每个元素最终成为具有指向其相邻元素之一的有向边缘的顶点.要获取每个顶点的边,必须首先比较其所有相邻元素.
我的问题是:(1)表示通常更快地初始化,也快BFS遍历,(2)什么算法(比香草BFS等)是否有寻找连接组件？我知道这是O(V + E)使用BFS(这是最佳的,我认为),但我很担心中间队列的大小的图形宽度与高度呈指数增长.
没有太多的图形实现经验,所以我很感激任何建议.
c++ algorithm graph breadth-first-search directed-acyclic-graphs