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

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("경로가 존재하지 않습니다");  // 경로가 없다는 메세지 출력

}

}