[Java | 자료구조] 그래프 - 인접행렬, 인접리스트

그래프

• 정점(vertex)과 간선(edge)들의 집합

특징

• 다음 특징들은 있는 경우와 없는 경우로 나뉨

  • 방향성
  • 가중치
  • 사이클 ➡️ 없는 그래프는 트리
  • 연결성 ➡️ 있으면 연결 그래프, 없으면 비연결 그래프

그래프 종류

그래프 사용 예시

무방향 그래프

• 친구 관계나 네트워크 연결
• BFS, DFS, MST(최소 신장 트리) 알고리즘 구현

방향 그래프

• 웹 페이지 간의 링크, 도로 네트워크 트래픽 흐름, 의사 결정 트리
• 최단 경로 알고리즘, 흐름 네트워크, 예산 할당 문제 등
• BFS, DFS, 위상정렬(Topological Sort) 알고리즘 구현

가중치 그래프

• 최단 경로 알고리즘, 흐름 네트워크, 예산 할당, 회로 설계
• MST, 최대 유량 알고리즘 구현

연결 그래프

• 인터넷 웹 페이지 간의 링크 관계, 도로 네트워크 연결성, 사회적 관계 네트워크
• 연결성 확인, MST, 오일러 경로 알고리즘 구현

비연결 그래프

• 도로 네트워크에서 도로가 각각의 도시를 연결하고 있지만 도시들 간에는 연결이 되어 있지 않은 경우
• 연결성 확인, MST, 오일러 경로 알고리즘 구현

순환 그래프

• 전기 회로에서 신호의 흐름, 사이클링 알고리즘, 경로 최적화
• 사이클 검사, 위상 정렬, 알고리즘 구현 가능

비순환 그래프

• 전기 회로에서 신호의 흐름, 사이클링 알고리즘, 경로 최적화
• 위상 정렬, 최단 경로 알고리즘 구현 가능

무방향 그래프(=양방향 그래프)

• 그래프가 이루어진 정점과 간선의 숫자 집합

  • 1 2
  • 1 3
  • 2 4
  • 2 5
  • 3 4
  • 3 1
  • 4 2
  • 5 2

• 인접행렬 구하기

  0	1	2	3	4	5
  1		1	1
  2	1			1	1
  3	1			1
  4		1	1
  5		1

방향 그래프

• 그래프가 이루어진 정점과 간선의 숫자 집합

  • 1 3
  • 1 2
  • 3 4
  • 4 2
  • 2 5

• 인접행렬 구하기

0	1	2	3	4	5
1		1	1
2					1
3				1
4		1
5

가중치 방향 그래프

• 그래프가 이루어진 정점과 간선의 숫자 집합
  • 1 4
  • 1 2
  • 3 4
  • 4 2
  • 2 5
• 인접행렬 구하기

0	1	2	3	4	5
1		2	4
2					5
3				5
4		2
5

연결 그래프

• 모든 노드가 최소한 하나의 경로로 연결된 그래프

비연결 그래프

• 일부 노드가 다른 노드와 연결되지 않은 그래프
• 하나 이상의 연결요소로 이루어져 있으며, 각 연결 요소는 자체적으로는 연결되어 있지만 다른 연결 요소와는 연결되어 있지 않음

💡 연결 요소(Connected Component)

• 그래프에서 어떤 정점으로부터 다른 정점으로 갈 수 있는 경로들의 집합
• 연결 요소들은 그래프의 최대로 연결된 부분 그래프가 됨
  

---

인접 행렬(Adjacency Materix)

• 2차원 배열의 형식
• 행렬 형식을 배열로 표현하기 위해 2차원 배열로 생성

장점

• 두 노드의 간선 정보 확인이 빠름
• 새로운 간선의 추가/제거가 빠름

단점

• 간선의 개수와 상관없이 배열의 크기는 항상 (노드의 개수*노드의 개수)임
  => O(N^2)의 메모리 사용
• 특정한 노드에 인접한 노드를 찾기 위해 모든 노드 순회
• 노드 추가/제거 오래걸림
  => O(N^2)
• 그래프의 모든 간선의 수를 찾는데 O(N^2)

사용예시

• 노드의 수가 적고, 간선의 수가 많을 때 적합
  => 밀집 그래프

구현

for (int i = 0; i < 간선의 수; i++) {
    st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken()); 
    int y = Integer.parseInt(st.nextToken());
    // 인접행렬 방법
    graph[x][y] = 1;
    graph[y][x] = 1;
}

총 노드 수: graph.length - 1

---

인접 리스트(Adjacency List)

• 그래프의 연결 상태를 연결 리스트로 나타내는 자료구조

  💡 연결 리스트

  • 데이터 요소가 노드로 구성된 선형 자료구조
  • 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 이루어져 있음
    

• 1차원 배열의 형식

• 배열의 크기 = 노드의 개수

• 행렬과 다르게 ArrayList의 자료구조를 이용해서 만드는 방식

• 동적할당이기 때문에 크기를 미리 정해주지 않아도 됨

장점

• 간선의 개수에 따라 메모리 사용량이 달라짐
• 특정 노드에 직접 접근할 수 있어 인접한 노드 찾기 쉬움
• 노드의 추가/제거 빠름
• 새로운 간선 빠르게 추가 가능
• 그래프의 모든 간선의 수를 찾는데 O(N+E)

단점

• 두 노드의 간선 정보를 확인하는데 오래걸림

사용예시

• 노드의 수가 많고, 간선의 수가 적을 때 적합
  => 최소 그래프

구현

Ver.1

int[][] graph = {
            {},
            {2,3,7},
            {1,3,5},
            {1,2},
            {6,8},
            {2},
            {4,7,8},
            {1,6},
            {4,6}
    };

위의 배열을 인접 리스트를 통해 그래프로 그릴 때,
각 배열의 인덱스는 그래프의 노드를 나타냄
해당 인덱스의 요소들은 해당 노드와 연결된 다른 노드들의 리스트를 표현

노드 1: {2, 3, 7}
노드 2: {1, 3, 5}
노드 3: {1, 2}
노드 4: {6, 8}
노드 5: {2}
노드 6: {4, 7, 8}
노드 7: {1, 6}
노드 8: {4, 6}
총 노드 수: graph.length - 1 (인덱스가 1부터 시작하기 때문)

Ver.2

N = Integer.parseInt(br.readLine());
ArrayList<Integer>[] map = new ArrayList[N + 1];
for(int i = 1; i <= N; i++) {
	map[i] = new ArrayList<>();
}

for(int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	int x = Integer.parseInt(st.nextToken());
	int y = Integer.parseInt(st.nextToken());
	map[x].add(y);
	map[y].add(x);
}

참고:자료구조 비선형 구조 이해하기