O(n+m) 中的 DFS 和 BFS 会发生变化吗？
does DFS and BFS in O(n+m) change?
我们知道有一个 O(n+m) 解决方案（DFS 或 BFS）用于检查无向图 G 中是否存在从 s 到 t 的路径n 个顶点和 m 个边...将通过邻接列表实现。
如果我用邻接矩阵实现我的程序，运行时会受到影响吗？这是好选择还是坏选择？
编辑：我需要计算时间复杂度，用这种方式，有什么想法吗？
假设您的代码输入为 n 和 m（节点数和边数），后跟 m 行类型 a b表示顶点a和顶点b之间有一条边。现在你采用邻接矩阵 M[][] 使得 M[i][j]=1 如果 i 和 j 之间存在边，否则 M[i][j]=0 （因为图是无向的，矩阵将是对称，因此您只能存储 upper/lower 半矩阵，减少一半的内存）。现在您必须获取矩阵并将其初始化为 0（所有单元格），同时扫描边缘标记 M[a][b]=M[b][a]=1。现在初始化部分是O(n^2)。扫描并标记边缘是O(m)。现在让我们看看 BFS/DFS 例程。当您在一个节点上时，您会尝试查看其所有未访问的顶点。现在假设我们想知道顶点 a 的邻居，你将不得不做 for(int i=0;i<n;i++) if (M[a][i]==1)（假设基于 0 的索引）。现在必须为每个顶点完成此操作，因此例程的复杂性变为 O(n^2) 即使 m < (n*(n-1))/2（假设没有多条边和循环的简单图 m 最多可以 (n*(n-1))/2）。 因此总体而言，您的复杂性变为 O(n^2)。那么邻接矩阵有什么用呢？好吧 DFS/BFS 可能只是一个大算法的一部分，你的算法可能还需要一个判断节点 a 和 b 之间是否存在边，在该边邻接矩阵采用 O(1) 时间。因此，是否选择邻接列表或邻接矩阵实际上取决于您的算法（例如您可以占用的最大内存，诸如 DFS/BFS 例程或回答两个顶点是否连接等问题的时间复杂度等）。
希望我回答了你的问题。
我们知道有一个 O(n+m) 解决方案（DFS 或 BFS）用于检查无向图 G 中是否存在从 s 到 t 的路径n 个顶点和 m 个边...将通过邻接列表实现。
如果我用邻接矩阵实现我的程序，运行时会受到影响吗？这是好选择还是坏选择？
编辑：我需要计算时间复杂度，用这种方式，有什么想法吗？
假设您的代码输入为 n 和 m（节点数和边数），后跟 m 行类型 a b表示顶点a和顶点b之间有一条边。现在你采用邻接矩阵 M[][] 使得 M[i][j]=1 如果 i 和 j 之间存在边，否则 M[i][j]=0 （因为图是无向的，矩阵将是对称，因此您只能存储 upper/lower 半矩阵，减少一半的内存）。现在您必须获取矩阵并将其初始化为 0（所有单元格），同时扫描边缘标记 M[a][b]=M[b][a]=1。现在初始化部分是O(n^2)。扫描并标记边缘是O(m)。现在让我们看看 BFS/DFS 例程。当您在一个节点上时，您会尝试查看其所有未访问的顶点。现在假设我们想知道顶点 a 的邻居，你将不得不做 for(int i=0;i<n;i++) if (M[a][i]==1)（假设基于 0 的索引）。现在必须为每个顶点完成此操作，因此例程的复杂性变为 O(n^2) 即使 m < (n*(n-1))/2（假设没有多条边和循环的简单图 m 最多可以 (n*(n-1))/2）。 因此总体而言，您的复杂性变为 O(n^2)。那么邻接矩阵有什么用呢？好吧 DFS/BFS 可能只是一个大算法的一部分，你的算法可能还需要一个判断节点 a 和 b 之间是否存在边，在该边邻接矩阵采用 O(1) 时间。因此，是否选择邻接列表或邻接矩阵实际上取决于您的算法（例如您可以占用的最大内存，诸如 DFS/BFS 例程或回答两个顶点是否连接等问题的时间复杂度等）。
希望我回答了你的问题。