1 / 3 일 모각코 제 2회 결과

3 주차 : 깊이 우선 탐색 신장트리

순환 깊이 우선 탐색 알고리즘 구현 메소드 

public void recu_dfs(int i) {

 if(i==0) { // i가 0이라면 (시작정점을 0번째 정점으로 하였을때)

visit=new boolean[size]; // size 크기를 가지는 visit 배열 

System.out.print("DFS: "); 

}

visit[i] = true; // index i 방문했다 표시 

System.out.print(vertices[i]+ " "); // vertices[i] 출력 

for(int k=0; k<size; k++) { //k 가 0부터 size보다 작을떄 까지 반복 

if(a[i][k] && !visit[k]) {  // k정점을 방문하지 않고 인접행렬이라면

recu_dfs(k); // k에 대한 recu_dfs(k) 실행 

}

}

}

방문순서와 신장트리를 출력하는 메소드 ( 순환으로 )

public void recu_dfs_tree(int i){ 

if(i==0) { // i가 0이라면 (시작정점을 0번째 정점으로 하였을때)

visit=new boolean[size]; //size 크기를 가지는 visit 배열 

}

visit[i] = true;// index i 방문했다 표시 

for (int k = 1; k <size; k++) {  //k 가 0부터 size보다 작을떄 까지 반복 

      if (!visit[k] && a[i][k]  ) {  // k정점을 방문하지 않고 인접행렬이라면

            System.out.println("정점" +vertices[k] + "는 정점 " + vertices[i] + "의 자식이다."); 

// 메세지 출력 

            recu_dfs_tree(k);  // k에 대한 recu_dfs_tree(k) 실행 

      }

}

}

방문순서와 신장트리를 출력하는 메소드  ( 위의 메소드와 결과 같지만 선형 )

public void dfs_tree(int i) { 

Stack<Integer> stack = new Stack<Integer>(); // integer 타입의 스택 stack 선언 

visit=new boolean[size]; //size 크기를 가지는 visit 배열 

visit[i]=true;  // index i 방문했다 표시 

stack.push(i); // stack 에 i 삽입 

int q=0; // q를 0으로 초기화 

while(! stack.isEmpty()) { // 스택이 비어있지 않다면 반복 

int k=stack.pop(); // 스택의 맨위에있는 원소 삭제후 k 에 삽입 

int num=size; // num을 size로 초기화 

 

for(int j=0; j<size; j++) { //j 가 0부터 size보다 작을떄 까지 반복 

if(a[k][j]) { //j정점과 인접행렬이라면

if(!visit[j]) {  //j정점을 방문하지 않았다면 

visit[j] = true;  // index j 방문했다 표시 

stack.push(j); // stack 에 j 삽입 

}

if(!a[q][k]) { //q 정점과 인접행렬이 아니 라면

if(a[q][j]) { // q 정점 j정점 인접행렬 이라면 

num=j;  // num에 j 삽입 -> 부모 표시를 위하여 

}

else { // q 정점 j정점 인접행렬 이아니라면 

for(int o=0; o<size; o++)  

//o 가 0부터 size보다 작을떄 까지 반복 

if(a[q][o]) q=o; //  q 정점 o정점 인접행렬 이라면 q에 o삽입

}

}

}

}

if(num!=size) // num 가 초기값인 size 가 아니면 

q=num; //q에  num 삽입 -> 부모를 표시하기 위해 

if(k!=i) // k 가 i가 아니라면 (시작정점 이후부터 프린트 하기위하여 )

  System.out.print("정점"+vertices[k]+"는 정점"+vertices[q]+"의 자식이다.\n"); 

q=k; // 바로 전에 pop 된 원소 q 에 삽입 (부모를 나타내기 위하여 )

}

}

}

4 주차 : Kruskal 알고리즘 구현

두집합의 합집합을 구하는 메소드 

public void  weightedunion(int set1, int set2) { //두 집합의 합집합을 구함

    int set1num = parent[set1]; //set1가 가르키는 부모를 set1num에 삽입 

    int set2num = parent[set2]; //set2가 가르키는 부모를 set2num에 삽입 

    int root1 = set1; // root1 에 set1 삽입 

    int root2 = set2; // root2 에 set2 삽입

    while(set1num>=0) { //set1num가 0이상이라면 반복 

    root1 = set1num; // root1 에 set1num 삽입 

    set1num = parent[root1]; // root1이 가르키는 부모를 set1num 에 삽입 

    }

    while(set2num>=0) {//set2num가 0이상이라면 반복 

    root2 = set2num; // root2 에 set2num 삽입 

    set2num = parent[root2]; // root2이 가르키는 부모를 set2num 에 삽입 

    }   

    if(set1num<set2num) { // 음수값이므로 세트 원이 세트 투보다 더 큰 집합이라는것 

    parent[root1]=set1num+set2num; // set1num와 set2num의 합을 parent[root1]에 넣음 

    parent[root2] = root1; // root1을 parent[root2] 에 삽입 

    }

    else { // 두 집합의 크기가같거나 세트 투가 세트 원보다 더 큰 집합일때 

    parent[root2] = set1num+set2num; // set1num와 set2num의 합을 parent[root2]에 넣음 

    parent[root1] = root2; // root2을 parent[root1] 에 삽입 

    }

    

}

한 원소가 속한 집합을 구하여 루트를 리턴하는 메소드  

public int Collapsingfind(int set) { //한 원소가 속한 집합을 구하여 루트 리턴 

    

    int setnum = parent[set]; // setnum에 parent[set]삽입 

    int root = set; // set을 root 에 삽입 

    while(setnum>=0) { // setnum이 0이상이라면 반복 

    root = setnum; //root에 setnum 삽입 

    setnum = parent[root]; //setnum 에 parent[root] 삽입 

    }

    while(set!=root) { // set 이 root와 같지 않다면 

    int temp = parent[set];  //temp 에 parent[set] 삽입 

    parent[set] = root; // parent[set] 에 root 삽입 

    set = temp; // set 에 temp 삽입 

    }

    return root; // root 리턴 

}

위의 두 메소드를 이용하여 구현 - 최소비용 신장트리에 포함된 edge 들과 최소 비용 출력 

 public void Kruskal() { //위의 두 메소드를 이용 Kruskal 알고리즘 구현

    //최소 비용 신장 트리에 포함된 edge들과 최소 비용 출력    

     for(int i=0; i<a.length; i++) { // 가중치 기준 오름차순으로 정럴 

     for(int j=i+1; j<a.length; j++) {

     if(a[i].weight>a[j].weight) {

     Edge temp = a[i];

     a[i] = a[j];

     a[j] = temp;

     }

     }    

     }

     

     int sum=0;

     int num=0;

     int minedge=0;

     

     while(num<parent.length-1) { //num가 parent.length-1 보다 작다면 반복 

    int root1 = Collapsingfind( a[minedge].v); //  a[minedge].v의 루트값을 root1 에 삽입 

    int root2 = Collapsingfind( a[minedge].w); // a[minedge].w의 루트값을 root2 에 삽입 

    

    if(root1!=root2) { //root1과 root2 의 값이 다르다면 

    sum += a[minedge].weight; // sum 에 가중치를 더해 갱신 

    weightedunion (a[minedge].v,a[minedge].w); 

// a[minedge].v의 집합과 a[minedge].w의 집합의 합

    a[minedge].selected = true; // a[minedge].selected 에 true 삽입 (선택했다고 표시)

    num++; // num 값 증가 

    }   

    minedge++;  // minedge 증가 

     }     

     System.out.println("최소 신장트리에 포함된 간선 "); // 메세지 출력 

     

     for(int i=0; i<a.length; i++) { //선택된 간선 트리 

     if(a[i].selected==true)

     System.out.print("( "+a[i].v + ", "+a[i].w + " )");

     }

     System.out.println("\n Min cost: " + sum);  // 가중치 의 합 출력 

    }

}