data-structures - 在没有 STL 的情况下实现图形的最佳方法？

Question

我被分配了一个项目，我必须接受一堆节点，以及在某些节点之间具有权重的边。

然后，我必须使用此信息为图形的每个连接组件找到最小生成树（因此，如果图形有两个连接组件，我需要创建两个生成树）

问题是我不能使用任何 STL 库，除了 .

我知道我需要创建自己的数据结构，但我不知道我需要哪些。我想最小堆对于找到要使用的最低权重边缘很有用，但是我将如何为每个连接的组件创建一个最小堆？

我在想我需要实现联合查找来组织连接组件的集合。

我需要为此实现哪些其他数据结构？

Answer 1

对于 union-find，您需要实现 DISJOINT SET。

这是使用简单数组的简单实现..看看

// Disjoint Set implementation
// Shashank Jain

#include<iostream>
#define LL long long int
#define LIM 100005
using namespace std;
int p[LIM],n; // p is for parent
int rank[LIM];
void create_set()
{
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        rank[i]=0;
    }
}
int find_set(int x)
{
    if(x==p[x])
        return x;
    else    
    {
        p[x]=find_set(p[x]);
        return p[x];
    }           
}
void merge_sets(int x,int y)
{
    int px,py;
    px=find_set(x);
    py=find_set(y);
    if(rank[px]>rank[py])
        p[py]=px;
    else
    if(rank[py]>rank[px])
        p[px]=py;
    else
    if(rank[px]==rank[py])
    {
        p[px]=py;
        rank[py]++;
    }               
}
int main()
{
    cin>>n; // no: of vertex , considering that vertex are numbered from 1 to n
    create_set();
    int a,b,q,i;
    cin>>q; // queries
    while(q--)
    {
        cin>>a>>b;
        merge_sets(a,b);
    }
    for(i=1;i<=n;i++)
    {
        cout<<find_set(i)<<endl; // vertex having same value of find_set i.e same representative of set are in same subset  
    }
    return 0;
}

Answer 2

我将假设您可以选择您的 MST 算法，并且输出是边列表。Borůvka 的算法实现起来很简单，除了图和不相交的集合结构之外不需要其他数据结构。相比之下，Prim 的算法需要一个优先级队列和一些逻辑来处理断开的图，而 Kruskal 的算法需要一个不相交的集合结构和一个排序算法。我会像这样设置数据结构。每个事件顶点-边对都有一个邻接记录。

struct Adjacency;

struct Edge {
    int weight;
};

struct Vertex {
    struct Adjacency *listhead;  // singly-linked list of adjacencies
    struct Vertex *parent;  // union-find parent
};

struct Adjacency {
    struct Adjacency *listnext;
    struct Edge *edge;
    struct Vertex *endpoint;  // the "other" endpoint
};