algorithm - 将简单的有向图转换为简单的无向图

Question

如何将简单的有向图转换为简单的无向图？

这可能吗？

Answer 1

假设:(来自 here)

in a simple digraph loops are disallowed. (A loop is an arc that pairs a vertex to itself.)

和:(来自 here)

a simple [undirected] graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.

我假设边缘未加权，否则无法在不指定需要如何完成的情况下完成。

AM = 邻接矩阵

AL = 邻接表

• 去除所有边的方向。

  AM:对于每条边 A->B，A 行，B 列都已经设置。同时设置 B 行，A 列。

  AL:对于A->B的每条边，该边已经出现在A的AL中，也将边添加到B的AL中。

• 遍历所有边，移除我们已经在作为该边终点的两个顶点之间找到边的所有边(因此，如果 A-B 已经被处理，如果我们找到另一个 A-B(或等效于 B-A)，我们必须删除该边)。需要这样做，因为在简单的有向图中顶点之间可以有多个边，但这在简单的无向图中不会发生。

  AM:实际上不需要做任何事情，因为 AM 强制顶点之间只有一条边，所以我们只是覆盖边。

  AL:对于每个顶点 A，对于其邻接列表中的每条边 A-B 或 B-A，删除列表中的所有其他边 A-B 或 B-A。