blocks|key|2889592|text|如果您想要实现O(V%2BE)时间复杂度，就没有更好的算法，因为这基本上是元素区分问题的一个变化，可以通过在O(nlogn)中排序或在O(n)中使用O(n)额外空间来解决。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2889593|因此，为了达到O(V%2BE)时间，您的算法是最优的(就大O符号而言)。|2889594|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Element_distinctness_problem^0|7|6|1G|8|1T|4|20|4|Z|6|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]|$9|S|A|T|B|C]|$9|U|A|V|B|C]|$9|W|A|X|B|C]]|D|@$9|Y|A|Z|1|10]]|E|$]]|$1|F|3|G|5|6|7|11|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|12|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

If you want to achieve <code>O(V+E)</code> time complexity, there is no better algorithm, because this is basically a variation of the <a href="http://en.wikipedia.org/wiki/Element_distinctness_problem" rel="nofollow">element distinctness problem</a>, which can be solved by sorting in <code>O(nlogn)</code>, or by using <code>O(n)</code> extra space in <code>O(n)</code>.

So, to achieve O(V+E) time, your algorithm is optimal (in terms of big O notation)

blocks|key|1568435|text|作为参考，应该注意的是，在技术上，每次重新设置数组时都使用O(V)时间。数组创建在技术上并不是免费的，因为它是用随机指针创建的，不能保证这些值是be.Thus的，它需要一次传递才能实际初始化它们0或null。因此，运行时成为O(V%5E2)为您提出的算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1568436|我知道这个问题现在已经解决了，但这个事实是值得注意的。|1568437|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

For reference it should be noted that technically, every time array is reset it uses O(V) time. Array creation is not technically free since it is created with random pointers with no guarantee of what those values will be.Thus it requires a single pass to actually initialize them 0 or null. Thus the run time becomes O(V^2) for your proposed algorithm.

I know this question has been resolved by now, but this fact should be noted.

blocks|key|1568414|text|您可以使用无序集数据结构从O(n)额外空间改进为O(最大邻居数)，只需检查邻接列表中没有添加两次邻居。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1568415|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

You could use a unordered set datastructure to improve from O(n) extra space to O(max number of neighbors) by only checking that no neighbor is added twice to the adjacency list.

blocks|key|2889639|text|遇到了同样的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2889640|经过思考，我想为您的解决方案提供一个快速的解决方案。正如@sunnytheit所提到的，在两个不同邻接列表之间的每两次迭代之间，您必须重置指示数组。此操作使您可以使用$\Theta({##**$$}V)$+This+(总计归纳为多项式运行时复杂性)。要修复它，可以使用与数组并行的堆栈。|2889641|一旦到达当前adj-列表中的顶点，首先检查它是否位于数组中，如果是，则继续到下一个邻居。如果没有，则将其推到堆栈上，并更新数组中的指示值。|2889642|当您在当前adj-列表上完成运行时，您希望弹出在该adj-列表上遇到的元素，并且对于每个值，您希望重置数组中的相应值。|2889643|总的来说，它可以概括为两次传递图形的边。因此，最后运行时的复杂性将是$\Theta(%7CV%7C%2B%7CE%7C)$。|2889644|注意:您可以使用某种类型的BST来节省额外的空间，而不是数组--但是您必须分析它对运行时复杂性的影响。|2889645|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

Encountered the same problem.

After thinking, I would like to suggest a quick little fix for your solution. As @sunnytheit mentioned - between each two iterations between two different adjacency lists, you've got to reset the indicating-array. This actions takes you $\Theta(|V|)$ indeed (In total summing up into polynomial runtime complexity). To fix it, you might use a stack parallerly with the array.

Once you reach a vertex in current adj-list, you firstly check whether it's located in array, if it does, you continue to the next neighbor. If it does not, you push it onto the stack and update the indicating value in the array.

When you finish running on the current adj-list, you would like to pop the elements you met on that adj-list, and for each value you would like to reset the corresponding value in the array.

Totally, it sums up to twice passing the edges of the graph. So, finally the runtime complexity would be $\Theta(|V|+|E|)$ as asked.

Remark: you can save up the additional space by using a BST of some sort instead of the array - but you would have to analyze its influence on the runtime complexity.

We are given the adjacency list for a multigraph, G = (V, E) and need to find an O(V + E) algorithm to compute the adjacency list of an equivalent undirected graph.

So far, I have thought of having an array of size |V| so as to mark the vertices that have been encountered at least once in adj[u], and thus preventing duplicates. The array is reset before traversing each adj[u]. But, I want to know if there exists a better algorithm for this that does not use extra space. Please suggest.

Algorithm to convert adjacency list of a multigraph to an equivalent undirected graph

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

给出了多图G= (V，E)的邻接表，并给出了求等价无向图邻接表的O(V + E)算法。到目前为止，我已经想过要有一个大小为x的数组，以便标记在adju中至少遇到过一次的顶点，从而防止重复。数组在遍历每个adju之前被重置。但是，我想知道是否有一个更好的算法不需要额外的空间。请建议一下。

问将多图邻接表转换为等价无向图的算法
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将多图邻接表转换为等价无向图的算法EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将多图邻接表转换为等价无向图的算法
EN