[DFS/BFS] 개념정리2 - 그래프, 인접행렬, 인접리스트

그래프

노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)라고도 함

두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현함

---

그래프 표현 방식(2가지)

1. 인접행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 

-> 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

/*
 * Adjacency Array(인접행렬) 
 */

class ArrGraph{
	private int[][] arrGraph; //2차원 배열 선언 
	
	//그래프 초기화 
	public ArrGraph(int graphSize) {
		//vertex가 1부터 시작할 때
		this.arrGraph = new int[graphSize+1][graphSize+1];
	}
	
	//그래프 return 
	public int[][] getGraph() {
		return this.arrGraph;
	}
	
	//그래프 추가 (단방향)
	public void putSingleEdge(int x, int y) {
		arrGraph[x][y] = 1;
	}
	
	//그래프 추가 (양방향) 
	public void putEdge(int x, int y) {
		arrGraph[x][y] = 1;
		arrGraph[y][x] = 1;
	}
	
	//그래프 출력 
	public void printGraph() {
		for(int i = 0; i < arrGraph.length; i++) {
			for(int j = 0; j < arrGraph[i].length; j++)
				System.out.print("[" + arrGraph[i][j] + "]");
			System.out.println();
		}
	}
}

public class AdjacencyMatrix {
	
	public static void main(String[] args) {
		int graphSize = 6;
		ArrGraph adjMatrix = new ArrGraph(graphSize);
		
		adjMatrix.putEdge(1, 2);
		adjMatrix.putEdge(1, 3);
		adjMatrix.putEdge(2, 3);
		adjMatrix.putEdge(2, 4);
		adjMatrix.putEdge(3, 5);
		
		adjMatrix.printGraph();
	}

}

2. 인접리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식 

-> 각 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장함

-> 연결 리스트 자료구조를 이용해 구현함(자바의 경우 별도로 연결 리스트 기능을 위한 표준 라이브러리 제공함)

//정점들의 LinkedList & 각 정점의 인접 정점들에 대한 LinkedList로 구현
/*
 * Adjacency List (인접리스트) 
 */
 
import java.util.LinkedList;

public class AdjacencyList {
	//간선 추가 메서드 (양방향 그래프 일 때) 
	public static void addEdge(LinkedList<LinkedList<Integer>> adjacencyList, int u, int v) {
		adjacencyList.get(u).add(v); 
		adjacencyList.get(v).add(u);
	}

	//인접리스트 출력 
	public static void printAdjacencyList(LinkedList<LinkedList<Integer>> adjacencyList) {
		for(int i = 0; i < adjacencyList.size(); i++) {
			System.out.print(i); //정점 출력 
			for(int v : adjacencyList.get(i)) //각 정점의 연결리스트의 노드들의 데이터값 반환 
				System.out.print(" -> " + v);
			System.out.println(); 
		}
	}
	
	public static void main(String[] args) {
		int vertex = 5; //정점의 개수 
		
		LinkedList<LinkedList<Integer>> adjacencyList = new LinkedList<LinkedList<Integer>>(); //참조변수 선언 & 빈 연결리스트 생성 
		for(int i = 0; i < vertex; i++) //정점의 개수만큼 연결리스트 노드 추가 (Add Last) 
			adjacencyList.add(new LinkedList<Integer>());
		
		//간선 추가 
		addEdge(adjacencyList, 0, 1);
		addEdge(adjacencyList, 0, 4);
		addEdge(adjacencyList, 1, 2);
		addEdge(adjacencyList, 1, 3);
		addEdge(adjacencyList, 1, 4);
		addEdge(adjacencyList, 2, 3);
		
		printAdjacencyList(adjacencyList);	
	}

}

추가)

1.

//위의 코드에서 작성한 for문
for(int v : adjacencyList.get(i)) //각 정점의 연결리스트의 노드들의 데이터값 반환 
	System.out.print(" -> " + v);
                
//위의 for문과 동일한 의미 
for(int j = 0; j < adjacencyList.get(i).size(); i++)
	System.out.print(" -> " + adjacencyList.get(i).get(j));

2.

LinkedList 클래스의 get() 메서드

-> 전달받은 index 위치(0 <= index < 연결리스트 size())에 해당하는 LinkedList의 노드의 데이터 필드 값 반환 

import java.util.LinkedList;

public class Main {
	public static void main(String[] args) {
		LinkedList<LinkedList<Integer>> list = new LinkedList<>();
		
		list.add(new LinkedList<Integer>());
		System.out.println(list.get(0)); //출력결과 : []
		
		list.get(0).add(1); 
		System.out.println(list.get(0)); //출력결과 : [1]
		
		list.get(0).add(2);
		System.out.println(list.get(0)); //출력결과 : [1,2]
		
		System.out.println(list.get(0).get(1)); //2 
	}
}

-> 이때 LinkedList 객체 출력 시 LinkedList의 원소 값들이 [?, ?, ?]의 형태로 출력되는데 그 이유는 LinkedList클래스가 상속받는 AbstractCollection 클래스에서 최상위 부모 클래스인 Object 클래스의 toString() 메서드를 오버라이딩하기 때문임

 

상황1) toString() 메서드를 오버라이딩 하지 않은 경우 

-> Object 클래스의 toString()이 실행됨

 

상황2) toString() 메서드를 오버라이딩 했을 경우

AbstractCollection 클래스의 toString()

-> 오버라이딩한 메서드가 실행됨

---

2가지 방식의 차이점 

• 메모리 측면

인접 행렬 방식의 경우 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨

인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리 효율적 사용 가능함

• 두 노드 간의 연결 확인 측면

인접 리스트 방식의 경우 각 노드별 인접 노드에 대해 리스트 형태로 저장되기 때문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 → 연결된 데이터를 하나씩 확인해야함 → 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우에 효과적임

 

 

참고)

https://www.geeksforgeeks.org/java-program-to-represent-graphs-using-linked-list/

https://keehyun2.tistory.com/entry/Linked-List연결리스트

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/AbstractCollection.html

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html