给定多图的邻接表，计算O（| V | + | E |）时间内等价（简单）无向图的邻接表 [英] Given an adjacency list for multigraph, compute adjacency list for equivalent (simple) undirected graph in O(|V|+|E|) time

问题描述

给出一个多图的邻接表G =（V，E），并且需要找到一个O（V + E）算法来计算等价（简单）无向图的邻接表。

我在另一篇文章中发现了以下解决方案（它是问题部分的一部分，因此我转贴）：
$ b

[H ]创建一个大小为| V |的数组，以便在adj [u]中标记至少遇到一次的顶点，从而防止出现重复。在遍历每个adj [u]之前，数组将被重置。

原谅我的无知，但我不确定这是O（| V | + | E |）。重置长度| V |的成本是多少？数组| V |时间？

谢谢。

解决方案

以实际重置数组。

说数组存储int。顶点标记为iff mark [u] == v 其中 v 是当前顶点的索引或id。

当您移动到下一个顶点时， v 的值会发生变化，并且数组中的所有条目将计算为假而不必更改数组中的值。

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 (simple) undirected graph.

I found the following solution in another post (it was part of the question section hence my repost):

"[H]aving 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]."

Forgive my ignorance, but I'm not sure how this is O(|V| + |E|). What is the cost of resetting a length |V| array |V| times?

Thank you.

解决方案

You don't need to actually reset the array.

Say the array stores int. A vertex is marked iff mark[u] == v where v is the index or id of the current vertex.

When you move to the next vertex the value of v changes and all the entries in the array will evaluate to false without having to change the values in the array.

这篇关于给定多图的邻接表，计算O（| V | + | E |）时间内等价（简单）无向图的邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！