-4

我有一个由邻接矩阵表示的无向图。

我需要一个高效的代码，函数只需要返回真或假。

而且我知道Dijkstra 的算法可以工作，我想我不需要最短路径，我的邻接矩阵是：

a[i][j] = 1 or -1

没有其他值。

4

2 回答 2

0

抱歉，我没有注意到你的矩阵只包含 0 和 1。

如果只查询一次，也许 DFS 或 BFS 更好，只有O(|V|+|E|)

如果是双向路径，Disjoint-set data structure（见维基百科）有效！

  • 单源还是多源？
  • 单查询还是多查询？

如果只有一个查询，则所有单源最短路径算法都可以。像：

  • 贝尔曼福特O(|V||E|)
  • 迪杰斯特拉O(|V|^2)
  • Dijkstra + 堆Θ((|E|+|V|)log|V|)
  • SPFA（贝尔曼福特使用队列）
  • ...

如果有很多查询，请考虑

  • Floyd-Warshall 算法O(|V|^3)
于 2012-08-12T02:49:49.830 回答
0

如果您只需要知道两点是否连接，我认为http://en.wikipedia.org/wiki/Disjoint-set_data_structure会尽快完成这项工作。从它自己的集合中的每个点开始，然后对于两个点之间的每个链接，连接这些点所属的两个集合。

于 2012-08-12T04:12:30.860 回答