-
2 votesanswersviews
最短路径树的子树也是最短的树？
我有一个无向加权图G =（V，E），其中V代表节点，E代表边 . 通过Dijkstra算法，我得到了一个最短路径树Ts =（s，V），它根源于源节点s并跨越图G中的所有节点V.然后我选择了一个子树Tm =（s，K），（其中K是最短路径树Ts =（s，V）的V）的子集，其将s连接到所有V个节点中的仅K个节点，即，子树Tm是最短路径树Ts的子集 . 我的问题是现在我怎么能通过参数或引理/定理来证明这个... -
0 votesanswersviews
将无向图转换为具有特定条件的有向图
给出了无向图，其具有M个边和N个顶点，我们必须将每个边从u-v转换为u-> v或v-> u，使得每个顶点的不均匀是均匀的 . 这种方法或算法适合于最小时间复杂度 . -
0 votesanswersviews
唯一路径无向循环图
我正在研究图表中的问题并试图找出寻找独特路径的方法 让我举个例子，让我们考虑一个包含4个节点和6个带边的边的图，如下所示 - 1 22 33 44 11 32 4 长度为5的独特循环路径将是 - 1 - > 2 - > 3 - > 4 - > 1 1 - > 3 - > 2 - > 4 - > 1 1 - > 2 ... -
0 votesanswersviews
无向图中最短周期的长度[重复]
这个问题在这里已有答案： Finding length of shortest cycle in undirected graph 3个答案 我给出了一个算法，该算法应该在具有单位边长的无向图中找到最短周期的长度 . 我必须通过提供反例来证明算法并不总是有效 . 我在提出一个可以证明此算法并不总是有效的示例时遇到问题 . 算法： 执行深度优先搜索，跟踪每个顶点的级别 . 每次遇到后沿... -
1 votesanswersviews
无法理解与无向图有关的一些术语
这是旧期中的一个示例问题： 设G =（V，E）是连通的无向图，其中边具有与它们相关联的正整数边权重，并且顶点s∈V是源 . 提供一种算法，对于每个顶点t∈V报告从s到t的非递减路径上的最小最后边缘权重（如果没有这样的路径，则为∞） . 路径v1，v2 ,. . . 如果对于i = 1,2，...... r-2，w（v_i，v_i 1）≤w（v_i 1，v_i 2），则vr不递减 . 我是否正... -
0 votesanswersviews
从邻接列表中创建无向图
我试图从邻接列表中创建一个无向图来练习Karger的Min Cut算法 . 以下是我的代码 class Vertex(object): '''Represents a vertex, with the indices of edges incident on it''' def __init__(self,name,edgeIndices=[]): s... -
-4 votesanswersviews
确定有向图上的所有顶点对之间是否存在路径
问题 我对这个问题有疑问： 给定包含N个顶点和M个边的有向图，请确定“对于所有 1 <= i, j <= N ，存在从顶点i到顶点j的路径” . 我想解决 N <= 500, M <= 250000 .我用dfs找到了天真的寻路算法，但时间复杂度是 O(N^2 M) ，所以它非常慢 .请告诉我解决它的有效算法 . 示例 例如，如果给出了这个图： 答案是否定的，因为没有从...