STL없이 그래프를 구현하는 가장 좋은 방법은 무엇입니까?

Question

나는 노드 묶음과 특정 노드 사이의 가중치를 가지고 있어야하는 프로젝트를 할당 받았다.

내가 다음 그래프의 연결되어있는 각 구성 요소에 대한 최소 스패닝 트리를 찾기 위해이 정보를 사용합니다

는 캐치 내가 사용할 수 있습니다

(그래프가 두 개의 연결된 구성 요소가있는 경우 그래서 두 개의 스패닝 트리를 만들 필요) for를 제외한 모든 STL 라이브러리.

나는 내 자신의 데이터 구조를 만들어야하지만 어떤 것들이 필요한지 알 수 없다는 것을 알고있다. 최소한의 힙을 사용하면 가장 적은 가중치를 찾는 데 유용 할 것이지만 연결된 각 구성 요소에 대해 최소 힙을 만드는 방법은 무엇입니까?

그리고 내가 연결된 구성 요소 집합을 구성하기 위해 연합 검색을 구현해야한다고 생각했습니다.

이것을 위해 구현해야하는 다른 데이터 구조는 무엇입니까?

Answer 1

공용체의 경우 DISJOINT SET을 구현해야합니다.

여기 .. ​​간단한 배열을 사용하여 간단한 구현을하는 모습을 나는 당신이 당신의 MST 알고리즘을 선택할 수 있다고 가정거야

// 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

을 가지고 있고 출력은 가장자리의 목록입니다. Borůvka's algorithm은 구현이 간단하며 그래프 및 분리 된 세트 구조 이외의 데이터 구조가 필요하지 않습니다. 대조적으로, 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 
};