본문 바로가기
2019 모각코/진도

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

by 데구르르르 2019. 1. 2.
728x90

1 주차 : 인접행렬을 이용한 그래프 구현



각 정점에 인접한 정점들의 개수를 출력하는 메소드 


public void degree(String k) { // 정점에 인접한 정점들의 개수를 출력

int num=0; // int타입의 num 초기값 0으로 선언

int p = index(k); // String k 인덱스 값을 받아 p 저장

for (int i = 0; i < size; i++) //int i 사이즈 보다 작을때까지 하나씩 증가하며 반복

if(a[p][i]==true) num++; // 만약 a[p][i] 값이 true 라면 num 증가 

System.out.println(num); // num 출력

}



서로 다른 정점에 대해 길이가 2 경로(path) 존재하는지 찾아 출력하는 메소드


public void findPath(String v, String w) { //서로 다른 정점에 대해 길이가 2 경로(path) 존재하는지 찾아 출력

int num =0; // int타입의 num 초기값 0으로 선언

int i = index(v), j = index(w); 

// String v 인덱스 값을 받아 i 저장, String w 인덱스 값을 받아 j 저장

if(i==j) { // 만약 서로다른 정점이 아니라면 

System.out.println("서로 다른 정점을 입력해야합니다"); // 오류메세지 출력

}

else { //서로다른 정점이라면 

for(int k=0; k<size; k++) { // int k 사이즈 보다 작을때까지 하나씩 증가하며 반복

if((a[i][k]==true)&&(a[j][k]==true)) { 

// 만약 a[i][k] 값과 a[j][k] true 라면 (k i 연결되어있는 동시에 k j 연결되어있음)

System.out.println(v+"-"+vertices[k]+"-"+w); 

// 경로 출력 (k 인덱스 k 값을 가지는 모서리vertices[k] 출력)

num++; // num 증가

}

}

if(num==0) // num==0 이라면

System.out.println("경로가 존재하지 않습니다");  // 경로가 없다는 메세지 출력

}

}

}




2 주차 : 인접리스트를 이용한 그래프 구현



연결된 정점을 추가하는 add 메소드


public void add(String v,String w) { 


int i = index(v), j = index(w); 

// String v 인덱스 값을 받아 i 저장, String w 인덱스 값을 받아 j 저장

Node temp; 


temp = a[i].next; // a[i] next 값을 temp 넣음 

a[i].next = new Node(j,temp); 

// j 값을 to 갖고 temp 값을 next 값으로 같는 새로운 노드를 생성해서 a[i] next 값에 넣음 


temp = a[j].next; // a[j] next 값을 temp 넣음

a[j].next = new Node(i,temp); 

// i 값을 to 갖고 temp 값을 next 값으로 같는 새로운 노드를 생성해서 a[j] next 값에 넣음

}



프린트를 해주는 toString 메소드 


public String toString() { 

if(size==0)

 return "{}";

StringBuffer buf = new StringBuffer("{ "+vertices[0]);

if(a[0].next!=null) { // 만약 a[0].next 값이 null 아니라면 

buf.append(":"); 

for(Node p = a[0]; p.next!=null; p=p.next) 

// p a[0] 넣고 p.next 값이 null 아니라면 반복문 진행, p p.next 넣음 

buf.append(vertices[p.next.to]); // buf vertices[p.next.to] 값을 넣음 

}

for(int i=1; i<size; i++) { // i 1부터 size 보다 작을때까지 1 증가하며 반복문 진행 

buf.append(","+vertices[i]); // buf 정점을 넣음 


if(a[i].next!=null) { // a[i] next 값이 null 아니라면 

buf.append(":");

for(Node p = a[i]; p.next!=null; p=p.next) 

// p a[i] 넣고 p.next 값이 null 아니라면 반복문 진행, p p.next 넣음 

buf.append(vertices[p.next.to]); // buf vertices[p.next.to] 값을 넣음 

}

}

return buf + " }";

}



서로 다른  정점에 대해 길이가 2 경로(path) 존재하는지 찾아 출력하는 메소드


public void findPath(String v, String w) { //서로 다른 정점에 대해 길이가 2 경로(path) 존재하는지 찾아 출력

int num =0; // int타입의 num 초기값 0으로 선언

int i = index(v), j = index(w);  

// String v 인덱스 값을 받아 i 저장, String w 인덱스 값을 받아 j 저장

if(i==j) { // 만약 서로다른 정점이 아니라면 

System.out.println("서로 다른 정점을 입력해야합니다"); // 오류메세지 출력

}

else { //서로다른 정점이라면 

Node p,q; 

for(p=a[i]; p.next!=null; p=p.next) { 

// 노드 p a[i] 넣고 p.next값이 null 값이 아니라면 반복문 진행, 진행후 p p.next 값을 넣음 

for(q=a[j]; q.next!=null; q=q.next) { 

// 노드 q a[j] 넣고 q.next값이 null값이 아니라면 반복문 진행, 진행후 q q.next 값을 넣음 

if(p.next.to==q.next.to) { // 만약 p.next to 값이 q.next to 값이 같다면 

System.out.println(v+"->"+vertices[p.next.to]+"->"+w); // 경로 출력 

num++; //num 증가 

}

}

}

        if(num==0) // num==0 이라면

System.out.println("경로가 존재하지 않습니다");  // 경로가 없다는 메세지 출력

}

}


728x90

'2019 모각코 > 진도' 카테고리의 다른 글

1 / 9 일 모각코 제 3회 결과  (0) 2019.01.09
1/9 모각코 제3회 목표  (0) 2019.01.09
1 / 3 일 모각코 제 2회 결과  (0) 2019.01.03
1/3 모각코 제2회 목표  (0) 2019.01.03
1/2 모각코 제1회 목표  (0) 2019.01.02

댓글