algorithm - 通过删除边从另一个图中迭代创建没有循环的图

Question

我有一个带有一些边的无向图，它保证有一些循环。我们称此图为 G1。我必须以迭代方式从该图中创建另一个图，比如 G2。当且仅当添加这条边不会在 G2 中创建循环时，我从第一个图 G1 中取出一条边并将其添加到我的第二个图 G2 中。如果它创建循环我不添加此边缘。我需要去除边缘的方式在我的程序逻辑中定义。 (每条边都有一个类型，我们首先使用一种类型的边，然后使用第二种类型的边，依此类推)

所以我使用了像https://www.geeksforgeeks.org/detect-cycle-undirected-graph/这样的正常循环查找算法每次添加边缘后。如果它创建了一个循环，我从第二个图 G2 中删除了边。不幸的是，它在 5000 节点图上速度太慢了。有什么更好的方法来处理这个问题？

图表信息:图表中的边代表复杂的网络拓扑。每条边都是一个数据结构

struct edge
{
  int weight ;
  int type ;
  int verter1;
  int vertex2;
};

类型是一个枚举整数

enum type
{
  wired , wifi , 4g , 3g , 2g ;
} ;

数据不是任意的，而是根据一些网络细节分配的。然后处理逻辑需要根据类型创建第二个图。我们想首先使用有线线路而不创建循环。然后处理wifi线路等等。

Answer 1

在构建第二张图时，您可以保留一些额外信息:该图中的连通分量。

定义一个组件数组。每个组件都是由第二个图中的路径连接的顶点的集合。最初，有多少个顶点就有多少个组件，每个组件只包含一个顶点。

要快速找到顶点属于哪个组件，请创建一个以顶点为键的 map 。对于给定的顶点，映射将顶点所属的组件作为值保存。

每当将一条边添加到第二个图中时，在图中查找该边的两个顶点所属的两个分量。当这两个组件实际上是同一个组件时，边缘会创建一个循环。如果不是，则边连接两个断开连接的组件:在这种情况下，对于两个组件中最小的每个顶点，将其移动到另一个组件并相应地更新 map 。