노드 및 호에 대한 데이터 구조에서 그래프 데이터 구조를 만드는 방법은 무엇입니까?

Question

나는 다음과 같은 노드와 아크 구조체를 만든 :

struct arc 
{ 
int length; 
string start; 
string end; 

    arc(int k,string s,string e) 
    { 
    this->length = k; 
    this->start = s; 
    this->end = e; 
    } 
}; 

struct node 
{ 
string name; 
double x; 
double y; 
vector<arc> link; 

node(string n,double xx,double yy) 
    { 
    this->name = n; 
    this->x = xx; 
    this->y = yy; 
    } 
}; 

지금 내가 그것에 크루스 칼의 알고리즘을 구현 할 수있는 그래프 데이터 구조는 만들고 싶어. 이 두 구조체를 어떻게 활용할 수 있는지 이해할 수 없습니다. 각 노드는 이름과 좌표 및 그로부터 또는 노드로가는 아크에 대한 정보를 저장합니다. 그래서 클러스터 노드가 있지만 어떻게 모든 것을 함께 연결합니까? 여기에는 루트 노드가 없습니다. 내 그래프 클래스에 무엇을 추가해야합니까? 인접 목록 및 매트릭스를 검색했지만 내 생각을 그들과 연관시키는 방법을 이해할 수 없습니까? 친절하게 설명하십시오

Answer 1

두 개의 호를 비교하고 어느 것이 더 작 으면 기준을 정의해야합니다.

두 노드의 좌표를 비교하면 노드를 비교하는 방법을 알 수 있습니다.
기준에 따라 호를 정렬하십시오.
노드가 모두 있지만 호가없는 빈 그래프로 시작하십시오.
DisjointSet 구조를 사용하면 연결된 구성 요소에 대한 정보를 유지할 수 있습니다 (사이클을 피하기 위해)
사이클을 만들면 작고 큰 것부터 호에 그래프를 추가하고 호를 무시하십시오.

크루스 칼 알고리즘 : http://en.wikipedia.org/wiki/Kruskal 's_algorithm

DisjointSet : http://en.wikipedia.org/wiki/Disjoint-set_data_structure