[Data Structure] 그래프 - 인접행렬과 인접리스트

그래프 (Graph)

그래프는 정점과 간선으로 이루어진 비선형 자료 구조를 말한다.

 

🔹정점(V) (vertex) - 그래프 내의 하나의 개별적 요소
🔹간선(E) (edge) - 정점과 정점 사이를 연결하는 선 (흐름, 관계 표현)
🔹가중치(W) (weight) - 간선과 정점 사이에 드는 비용
🔹차수 (degree) - 정 정점에 연결된 간선의 수
        ◽out-degree: 다른 정점으로 나가는 간선 (수)
        ◽in-degree: 특정 정점으로 들어오는 간선 (수)
        ◽무방향 그래프에선 하나의 간선이 두 정점에 인접하므로 간선 수의 두 배

💡 비선형 자료 구조
비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.
일반적으로 트리나 그래프를 말한다.

 

방향 그래프(Diredted Graph)
그래프의 간선이 한 정점에서 다른 정점으로의 방향을 가짐

 

무방향 그래프(Undirected Graph)
그래프의 간선에 방향성이 없는 그래프

 

가중치 그래프(Weighted Graph)
간선에 비용이나 가중치가 할당된 그래프

 

 

그래프 구현

그래프를 구현하는 방식으로는 크게 인접 리스트와 인접 행렬을 사용하는 방식으로 나뉜다.

 

1️⃣인접 행렬(Adjacency Matrix)

정방 행렬을 사용하여 그래프의 정점 간 연결 관계를 표현하는 방식이다. 행렬의 각 원소(i,j)는 정점 i와 정점 j 사이의 간선 여부를 나타낸다. 보통 1인 경우는 간선이 존재한다는 의미이고, 0인 경우는 간선이 없어 연결되어 있지 않다는 것을 의미한다. 간선의 수가 정점의 수에 비해 많은 그래프에 효과적이다. (간선의 수가 적은 그래프를 표현할 때에는 낭비되는 행렬의 공간이 많아져 비효율적이다.)

 

🔹정점 수 가 n일 때, n*n크기의 행렬 필요
🔹각 행과 열은 정점을 의미, 각 원소 값들은 간선을 의미
🔹무방향 그래프는 대칭 구조
🔹가중치 그래프는 보통 가중치 값 저장

👉 장단점
두 정점의 간선 조회 시  O(1) 의 시간 소요
특정 정점 i의 차수를 구할 때  O(n)  의 시간 소요 (i번째 행의 값을 모두 더하여 구할 수 있음)
간선 수에 상관없이 무조건  n*n  크기의 배열 필요하므로 메모리 공간 낭비할 가능성 높음
그래프의 모든 간선의 수 알아낼 때  O(n^2) 소요

 

☕ in java

package dataStructure;

public class 그래프_인접행렬 {
    public static void main(String[] args) {

        GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(4);

        // 무방향 그래프(양방향 그래프) 간선 추가
        graph.addEdge(1, 2, true);
        graph.addEdge(2, 3, true);
        graph.addEdge(2, 4, true);
        graph.addEdge(3, 4, true);

        // 간선 조회
        System.out.println("Graph has edge between 1 and 2: " + graph.hasEdge(1, 2));
        System.out.println("Graph has edge between 1 and 4: " + graph.hasEdge(1, 4));
        graph.printGraph();
    }


    static class GraphAdjacencyMatrix {
        private int[][] graph;
        private int size;

        public GraphAdjacencyMatrix(int size) {
            // 편의상 +1 크기 배열 생성
            this.size = size;
            this.graph = new int[size+1][size+1];
        }

        // 간선 추가
        public void addEdge(int from, int to, boolean undirected) {
            graph[from][to] = 1;

            // 양방향 간선 추가
            if (undirected) {
                graph[to][from] = 1;
            }
        }

        // 간선 확인
        public boolean hasEdge(int from, int to) {
            return graph[from][to] == 1;
        }

        // 그래프 출력
        public void printGraph() {
            for(int i = 1; i <= size; i++) {
                for(int j = 1; j <= size; j++) {
                    System.out.print(" " + graph[i][j]);
                }
                System.out.println();
            }
        }
    }
}

Graph has edge between 1 and 2: true
Graph has edge between 1 and 4: false
 0 1 0 0
 1 0 1 1
 0 1 0 1
 0 1 1 0

 

2️⃣인접 리스트(Adjacency List)

그래프의 각 정점마다 그 정점과 연결된 다른 정점들의 목록을 저장하는 방식이다. 각 정점마다 연결된 정점들을 리스트나 배열로 표현하여 그래프의 구조를 효율적으로 나타낼 수 있다. 특히, 정점 수에 비해 간선 수가 적은 그래프에 효과적이다.

 

🔹정점 개수만큼 리스트 필요
🔹각 리스트엔 인접한 정점의 정보 저장
🔹무방향 그래프의 경우 간선 추가 시 각 정점의 반대 정점 리스트에도 노드 추가

 

아래 그림을 보면 각 정점마다 연결된 다른 정점들의 정보를 리스트 형태로 저장하고 있는데, 연결 리스트나 일반 리스트를 사용할 수 있다. 연결 리스트에 비해 일반 리스트를 사용하는 것이 구현이 용이하다.

👉 장단점
연결되어 있는 정점들의 정보(간선)만 관리하므로 메모리 사용 측면에서 효율적
두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해선 인접 리스트를 탐색
→ 정점의 차수만큼의 시간 필요  O(degree(v)) 

 

☕ in java

package dataStructure;
import java.util.ArrayList;

public class 그래프_인접리스트 {
    public static void main(String[] args) {
        int numNodes = 4;
        GraphAdjacencyList graph = new GraphAdjacencyList(numNodes);

        graph.addEdge(2, 1, false);
        graph.addEdge(2, 4, false);
        graph.addEdge(3, 2, false);
        graph.addEdge(4, 3, false);

        // 정점마다 연결된 정점들 확인
        for (int i = 1; i <= numNodes; i++) {
            ArrayList<Integer> neighbors = graph.getAdjacentNodes(i);
            System.out.println("Node " + i + " is adjacent to: " + neighbors);
        }
    }

    static public class GraphAdjacencyList {
        private int numNodes;
        private ArrayList<ArrayList<Integer>> adjList;

        // 생성자
        public GraphAdjacencyList(int numNodes) {
            // 그래프 정점 수만큼 리스트 생성
            // 노드 번호 1부터 시작하기 위해 편의상 + 1
            this.numNodes = numNodes + 1;
            adjList = new ArrayList<>(this.numNodes);

            // 각 노드마다 연결 정보 저장할 리스트 생성
            for (int i = 0; i <= numNodes; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        // 간선 추가
        public void addEdge(int u, int v, boolean undirected) {
            adjList.get(u).add(v);

            // 무방향 그래프일 때
            if(undirected){
                adjList.get(v).add(u);
            }
        }

        public ArrayList<Integer> getAdjacentNodes(int node) {
            return adjList.get(node);
        }
    }
}

Node 1 is adjacent to: []
Node 2 is adjacent to: [1, 4]
Node 3 is adjacent to: [2]
Node 4 is adjacent to: [3]