교실 노트: 최소 생 성 트 리
Void prime(MGraph G){
for(int i=1;i<G.vertexNu;i++){
lowcost[i]=G.arc[0][i];
adjvex[i]=0;
}
lowcost[0]=0;
for(i=1;i<G.vertexNum;i+++){
k=MinEdge(lowcost,G.vertexNum)
cout<<K<<adjvex[k]<<lowcost[k];
lowcost[k]=0;
for(j=1;j<G.vertexNum;j++)
if((G.arc[k][j]<lowcost[j]){
lowcost[j]=G.arc[k][j];
arcvex[j]=k;
}
}
}시간 복잡성: O (n2), 조밀도 에 적용.Kruskal 알고리즘 기본 사상: 1. 무방 향 연결 망 을 G = (V, E) 로 설정 하고 G 의 최소 생 성 트 리 를 T = (U, TE) 로 만 들 며 그 초 태 는 U = V, TE = {}, 2. 그리고 변 의 가중치 에 따라 작은 것 에서 큰 순서 로 G 의 변 집합 E 의 각 변 을 고찰 한다.2.1 고찰 된 변 의 두 정점 이 T 에 속 하 는 두 개의 서로 다른 연결 분량 이 라면 이 변 을 최소 생 성 트 리 의 변 으로 T 에 넣 고 두 개의 연결 분량 을 하나의 연결 분량 으로 연결한다.2.2 만약 에 고찰 된 변 의 두 정점 이 같은 연결 분량 에 속 하면 이 변 을 버 리 고 회 로 를 초래 하지 않도록 한다.3. 이렇게 하면 T 의 연결 분량 개수 가 1 일 때 이 연결 분량 은 G 의 최소 생 성 나무 입 니 다.Kruskal 알고리즘 사상 1. 초기 화: U = V;TE={ }； 2. T 의 연결 분량 개수 가 1. 2.1 일 때 까지 순환 하고 E 에서 가장 짧 은 변 (u, v) 을 찾 습 니 다.2.2 만약 에 정점 u, v 가 T 의 두 개의 서로 다른 연결 분량 에 있 으 면 2.2.1. 변 (u, v) 을 TE 에 합병 한다.2.2.2 이 두 개의 연결 분량 을 하나 로 합 친다.2.3. E 에 가장자리 (u, v) 를 표시 하여 (u, v) 후속 최 단 변 의 선택 에 참가 하지 않 게 한다.Kruskal 알고리즘 실현 중의 세 가지 관건 적 인 문제 1. 그림 의 저장 구 조 는 변 집합 배열 저장 도 를 사용한다.2. 한 변 에 붙 어 있 는 두 개의 정점 이 같은 연결 분량 에서 (집합 을 찾 아) Parent [i] 배열 을 정의 하 는 지 어떻게 판단 합 니까?배열 분량 의 값 은 정점 i 의 부모 노드 (초기 값 은 - 1;) 를 나타 낸다. 한 변 (u, v) 의 두 정점 의 뿌리 가 같 지 않 을 때 이 두 노드 는 서로 다른 연결 분량 에 속한다.어떻게 한 변 에 붙 어 있 는 두 개의 정점 을 같은 연결 분량 에 합 쳐 연결 분량 의 합병 을 진행 합 니까? 그 중에서 한 정점 이 있 는 나무의 뿌리 노드 는 vex 1 이 고 다른 정점 이 있 는 나무의 뿌리 노드 는 vex 2 입 니 다. 그러면 parent [vex 2] = vex 1 입 니 다.
int Find(int *parent, int node){
int f;
f=node;
while(parent[f]>-1)
f=parent[f];
return f;
}
int main(){
int arcNum, int vertexNum;
EdgeNode *edge;
int *parent;
cout<<"please input the number of vertexNum:";
cin>>vertexNum;
cout<<"please input the number of edges:";
cin>>arcNum;
edge=new EdgeNode[arcNum];
parent=new int[vertexNum];
for(int i=0;i<arcNum;i++){
cout<<"Please input the edges:";
cin>>edge[i].from>>edge[i].to>>edge[i].weight;
}
sort(edges, G);
for (i=0;i<vertexNum;i++)
parent[i]=-1;
int k=0,begin,end,count=0;
cout<<"next is the MST :"<<endl;
for (k=0;k<arcNum;k++){
begin=edge[k].from;
end=edge[k].to;
int m,n;
m=Find(parent,begin);
n=Find(parent,end);
if(m!=n){
cout<<begin<<","<<end<<","<<edge[k].weight<<endl;
parent[n]=m;
count++;
if(count==vertexNum-1)
break;
}
}
return 0;
}Kruskal 알고리즘 의 시간 복잡성 분석 변 집합 배열 정렬, 시간 복잡성 O (eloge), e 변 에서 변 을 선택 하고 시간 복잡성 은 O (e) 이 므 로 시간 복잡성 은 O (eloge) 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
《 큰소리 데이터 구 조 》 노트 - day 2배열 의 길 이 는 선형 표를 저장 하 는 저장 공간의 길이 로 보통 변 하지 않 는 다 메모리 의 모든 저장 부 는 자신의 번 호 를 가지 고 있 는데 이 번 호 는 주소 계산 선형 표 의 위치 라 고 한다. 요소...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
