어떻게 C++에서 무향 그래프를 생성합니까?

Question

내 Kruskal의 알고리즘을 테스트하려면 간단한 무향 그래프를 생성해야합니다. 나는 이렇게 만든 모든 연결을위한 구조를 가지고 :

struct connection 
    { 
     node1; 
     node2; 
     edge_value; 
    } 

지금 나는 그것을 크루스 칼의를 테스트하기 위해, 이러한 연결의 상당한 금액을 생성해야합니다. Kruskal의 algo는이 세대보다 힘들지 않았습니다. 아마 Graphs에 처음으로 직면했을 것입니다.

Answer 1

kruskal 알고리즘을 실행하기 때문에 데이터 구조가 정상입니다!

당신은 이미 kruskal 구현을했다고 가정합니다.이 데이터 구조를 사용하면 필요한 것은 벡터를 설정 한 다음 해당 함수를 사용하여 해당 벡터를 정렬하고 마지막으로 벡터를 n log (n)의 계산 비용).

알고리즘을 테스트해야한다면 머리 위로부터이 문제를 참조 할 수있는 uva의 웹 사이트를 방문하는 것이 좋습니다. http://uva.onlinejudge.org/external/113/11354.html 3 가지 사례를 사용하여 kruskal 구현이 작동하는지 테스트 할 수 있습니다.