从邻接列表到边缘列表的快速转换 [英] Fast Convertion From Adjacency List to Edge List

问题描述

我有一个使用邻接表实现的无向加权图，需要将其转换为边缘列表。问题是，对于每个边（A，B），我在邻接列表中有两个条目：一个指示从A到B的边，另一个指示从A到B的边。 ，将其转换为边缘列表时，我需要搜索整个部分完成的边缘列表，以防止重复。

I have an undirected weighted graph implemented with adjacency list which I need to convert to an edge list. The problem is, for each edge (A, B), I have two entries in adjacency list: one indicating an edge to B from A and other from A to B. So, while converting this to edge list, I need to search the whole partially completed edge list to prevent duplicates.

有什么办法可以使它更快/更简单？我需要保留邻接表，因为我在图形中检测循环的算法依赖于此。

Is there any way I can make that faster/ less complicated? I need to keep the adjacency list because my algorithm of detecting cycles in graph relies on it.

推荐答案

枚举您的顶点仅将边（u，v）使得 u< = v 。

Enumerate you vertices add to your list only edges (u, v) such that u <= v.

这篇关于从邻接列表到边缘列表的快速转换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！