[Theory] Graph 2. 인접 리스트(Adjacent List) 탐색

 이어서 동일한 그래프를 인접 리스트(Adjacent List)로 나타내 보도록 하자.
인접리스트로 나타내기 위해서는 노드를 구현한 클래스가 필요하다.  이 노드 클래스는 자신의 vertex 번호와, 이어지는 노드에 대한 정보를 담고 있어야 한다.

- 노드 클래스 구조

static class Node{
		int vertex;
		Node next;
		public Node(int vertex, Node next) {
			this.vertex = vertex;
			this.next = next;
		}
		public Node(int vertex) {
			this.vertex = vertex;
		}
		@Override
		public String toString() {
			return "Node [vertex=" + vertex + ", next=" + next + "]";
		}
	}

 

- 연결 리스트 구조화
이제 입력받는 간선 정보를 바탕으로 연결리스트를 만든다. 먼저 adjList는 Node배열이다. 따라서 adjList의 원소들은, 이어진 여러 노드들의 head격에 해당한다. 여기서 주의할 점은, 뒤로 이어진 노드들 간의 연관관계가 있는 것이 아니라 노드들은 항상 adjList의 원소랑만 연관관계가 있는 것이다.

특히 아래 코드에서는, 각 head node에서 마지막 노드를 검색해서 그 뒤에 붙이는 방법이 아니라, head 바로 뒷부분에 계속해서 붙이게 되어 있다. 따라서 연결리스트의 마지막을 매번 찾을 필요가 없다. 더불어 처음 노드를 뒤에 붙이는 것도 new Node(to, adjList[from]) 의 adjList[from]에 null값이 들어가게 된다!!

public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjList = new Node[N];
		
		StringTokenizer st = null;
		for(int i=0; i<C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

//			1. 현재 head가 가리키는 레퍼런스를 가지는 to Node를 만든다.
//			2. 현재 head를 to Node로 바꾼다 -> 결국 계속 첫번째 노드를 집어넣는 방식이다.
//			   다른 방법으로, 헤드가 가리키는 마지막 노드를 검색해서 그 뒤에 붙이는  방법도 있지만, 위의 방법으로는 마지막 노드를 검색할 필요가 없다.
			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);
 		}
		
		bfs();
		
		// dfs탐색에서는 전역변수로 visited 선언
		visited = new boolean[N];
		dfs(0);
		
	}

 

- BFS
  리스트의 동작방식을 알게되면 BFS역시 동일한 방법으로 움직인다. 다만 다음 노드를 구하는 데 있어 .next로 타고 들어가는 부분만 다르고, 나머지는 동일하다.

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		int start = 0;
		queue.offer(start);
		visited[start] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println((char)(current+65));
			
			for(Node temp = adjList[current]; temp!=null; temp = temp.next) { // 인접 정점만 반복처리
				// 따라서 인접을 체크하는 조건이 오지 않는다.
				if(!visited[temp.vertex]) { 
					queue.offer(temp.vertex);
					visited[temp.vertex] = true;
				}
			}
		}
	}

- DFS
  DFS로 작성하면 코드는 더 간단명료해 진다. 

private static void dfs(int current) {
		visited[current] = true; // 만약에 dfs()에 들어가기 직전에 체크를 하면, 처음 시작에도 true를 해 주어야 한다.
		System.out.println((char)(current+65));
		
		for(Node temp = adjList[current]; temp != null; temp = temp.next) {
			if(!visited[temp.vertex]) {
				dfs(temp.vertex); // 그 정점으로 이동
			}
		}
	}

 

---

물론 라이브러리를 활용해서 ArrayList 자료구조를 사용할 수 있다. 

- 라이브러리 사용 ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G2_adjListTest {
	
	static int N;
	static ArrayList<Integer>[] adjList; // 헤드의 역할을 하는 배열
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjList = new ArrayList[N]; // 배열객체 생성
		for(int i=0; i<N; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		
		StringTokenizer st = null;
		for(int i=0; i<C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adjList[from].add(to);
			adjList[to].add(from);
 		}
		
		bfs();
		
		// dfs탐색에서는 전역변수로 visited 선언
		visited = new boolean[N];
		dfs(0);
		
	}
	
	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		int start = 0;
		queue.offer(start);
		visited[start] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println((char)(current+65));
			
			for(int temp : adjList[current]) {// temp : current와 인접한 정점들의 번호 
				if(!visited[temp]) { 
					queue.offer(temp);
					visited[temp] = true;
				}
			}
			
		}
	}
	
	private static void dfs(int current) {
		visited[current] = true; // 만약에 dfs()에 들어가기 직전에 체크를 하면, 처음 시작에도 true를 해 주어야 한다.
		System.out.println((char)(current+65));
		
		for(int temp : adjList[current]) {
			if(!visited[temp]) {
				dfs(temp); // 그 정점으로 이동
			}
		}
	}

}

 

- Node 클래스 직접 선언 ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G2_adjListTest {

	static class Node{
		int vertex;
		Node next;
		public Node(int vertex, Node next) {
			this.vertex = vertex;
			this.next = next;
		}
	}
	
	static int N;
	static Node[] adjList; // 헤드의 역할을 하는 배열
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		int C = Integer.parseInt(in.readLine());
		adjList = new Node[N];
		
		StringTokenizer st = null;
		for(int i=0; i<C; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

//			1. 현재 head가 가리키는 레퍼런스를 가지는 to Node를 만든다.
//			2. 현재 head를 to Node로 바꾼다 -> 결국 계속 첫번째 노드를 집어넣는 방식이다.
//			   다른 방법으로, 헤드가 가리키는 마지막 노드를 검색해서 그 뒤에 붙이는  방법도 있지만, 위의 방법으로는 마지막 노드를 검색할 필요가 없다.
			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);
 		}
		
		bfs();
		
		// dfs탐색에서는 전역변수로 visited 선언
		visited = new boolean[N];
		dfs(0);
		
	}
	
	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		int start = 0;
		queue.offer(start);
		visited[start] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println((char)(current+65));
			
			for(Node temp = adjList[current]; temp!=null; temp = temp.next) { // 인접 정점만 반복처리
				// 따라서 인접을 체크하는 조건이 오지 않는다.
				if(!visited[temp.vertex]) { 
					queue.offer(temp.vertex);
					visited[temp.vertex] = true;
				}
			}
		}
	}
	
	private static void dfs(int current) {
		visited[current] = true; // 만약에 dfs()에 들어가기 직전에 체크를 하면, 처음 시작에도 true를 해 주어야 한다.
		System.out.println((char)(current+65));
		
		for(Node temp = adjList[current]; temp != null; temp = temp.next) {
			if(!visited[temp.vertex]) {
				dfs(temp.vertex); // 그 정점으로 이동
			}
		}
	}

}