图形表示基准

Question

当前正在开发一个程序，以解决（如果可能）尺寸从3X4到26x30的任何给定迷宫的问题。我用adj矩阵（稀疏）和adj列表来表示图。我想知道如何输出DFS使用一种方法然后使用另一种方法找到解决方案所花费的总时间。以编程方式，我怎么能产生这样的基准？

Answer 1

一个有用的表格，用于处理各种图形实现：

OPERATION               EDGE LIST      ADJ LIST             ADJ MATRIX

degree(v)                 O(m)         O(d(v))                O(n)
incidentEdges(v)          O(m)         O(d(v))                O(n)
areAdjacent(v1,v2)        O(m)         O(min(d(v1),d(v2))     O(1)
addVertex(v)              O(1)         O(1)                   O(n²)
addEdge(v)                O(1)         O(1)                   O(1)
removeVertex(v)           O(m)         O(m)                   O(n²)
removeEdge(e)             O(m)         O(d(v1)+d(v2))         O(1)

memory                    O(m+n)       O(m+n)                 O(n²)

其中，m是边数，n是顶点数，d(vertex)是顶点邻接表中的元素数。adj矩阵实现具有O(n²)添加和删​​除顶点的功能，因为您必须重新分配矩阵。

刚刚准备了这篇文章，这就是为什么我要准备它的原因:)

这与基准测试没有直接关系，因为通常您会研究最需要的操作并根据需要选择正确的实现，因此这是通过研究要实现的目标进行的一种“理论”基准测试。否则，您只需衡量代码在两个实现上完成全部工作所需的时间，然后进行比较即可。

编辑： 由于您使用稀疏矩阵实现，因此操作的复杂性可能会略有变化（大多数情况会更糟，因为您要以内存换取速度）。

EDIT2： 好的，现在我知道这是Java，它将非常简单：

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

答案以纳秒为单位，并且不能保证准确性，因此请小心使用此设备。进行多次运行的平均值（并检查方差低，丢弃与平均值相差较远的结果）将使您的结果具有连贯性。