[자료구조와 알고리즘] 그래프 표현방법

인접행렬 (Adjacency Matrix)

• G=(V, E)는 정점의 수가 n인 그래프
• 인접행렬: n x n인 2차원 배열
  • 행, 열 => 그래프의 정점
  • 간선 (Vi, Vj) ∈ E(G) => a[i][j] = 1 (인접한 경우)
  • 간선 (Vi, Vj) ∉ E(G) => a[i][j] = 0 (인접하지 않은 경우)
• 무방향 그래프 : 어떤 정점 i의 차수는 그 행 또는 열의 합
• 방향 그래프 : 행의 합은 진출차수, 열의 합은 진입차수

• 정점 0의 인접 정점 : 1, 2
• 정점 1의 인접 정점 : 0, 3
• 정점 2의 인접 정점 : 0. 3
• 정점 3의 인접 정점 : 1, 2

인접행렬 소스코드

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

class Graph {
    private int[][] adjGraph;

    public Graph(int size) { // 그래프 초기화
        this.adjGraph = new int[size][size];
    }

    public void insertDouble(int v1, int v2) { // 무방향 그래프 간선 추가
        adjGraph[v1][v2] = adjGraph[v2][v1] = 1;
    }

    public void insertSingle(int v1, int v2) { // 방향 그래프 간선 추가
        adjGraph[v1][v2] = 1;
    }

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

public class GraphMatrix {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = 4;
        int edge = 4;

        Graph arr = new Graph(size);

        for(int i=0;i<edge;i++) {
            String str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            arr.insertDouble(v1, v2);

            // 방향 그래프일 경우에는 arr.insertSingle(v1, v2);
        }
        /*
         입력(무방향 그래프)

         0 1, 정점 0과 1 사이의 간선 추가
         0 2, 정점 0과 2 사이의 간선 추가
         1 3, 정점 1과 3 사이의 간선 추가
         2 3, 정점 2와 3 사이의 간선 추가

         */
        System.out.println();

        arr.printGraph();

        /*출력

           0 1 1 0
           1 0 0 1
           1 0 0 1
           0 1 1 0

        */

    }

}

 

• 인접행렬의 수행 시간 : 최소 O(n2)
• 인접행렬의 단점
  • n개의 정점을 가지는 그래프를 항상 n x n개의 메모리를 사용해야 한다.
  • 정점의 개수에 비해 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생

인접 리스트 (Adjacency Lists)

• 각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트 -> 인접 행렬의 각 행을 연결 리스트로
• 각 정점의 차수만큼 노드를 연결
  • 리스트 내의 노드들은 인접 정점에 대하여 오름차순으로 연결
• 인접 리스트의 각 노드
  • 정점과 다음 인접 정점을 연결하는 링크 필드
• 정점의 헤드 노드
  • 정점에 대한 리스트의 시작을 표현

• n개의 정점, e개의 간선을 가진 무향 그래프의 인접 리스트
  • 헤드 노드 배열의 크기 : n
  • 연결하는 노드의 수 : 2e
  • 각 정점의 헤드에 연결된 노드의 수 : 정점의 차수
• n개의 정점, e개의 간선을 가진 방향 그래프의 인접 리스트
  • 헤드 노드 배열의 크기 : n
  • 연결하는 노드의 수 : e
  • 각 정점의 헤드에 연결된 노드의 수 : 정점의 진출 차수
  • 역인접리스트 : 진입 차수
• 위의 그림에서 정점 0에는 노드 2개가 있는데, 이는 정점 0의 차수는 2라는 의미이다.
• 인접 리스트 소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Graph {
    private ArrayList<ArrayList<Integer>> listGraph;

    public Graph(int size) {
        this.listGraph = new ArrayList<ArrayList<Integer>>();

        for(int i=0;i<=size;i++) {
            listGraph.add(new ArrayList<>());
        }
    }

    public void insertDouble(int v1, int v2) {
        listGraph.get(v1).add(v2);
        listGraph.get(v2).add(v1);
    }

    public void insertSingle(int v1, int v2) {
        listGraph.get(v1).add(v2);
    }

    public void printGraph() {
        for(int i=0;i<listGraph.size()-1;i++) {
            System.out.print("Vertex "+i+" 인접리스트");
            for(int j=0;j<listGraph.get(i).size();j++) {
                System.out.print("-> " + listGraph.get(i).get(j));
            }
            System.out.println();
        }
    }
}

public class GraphList {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Graph graph = new Graph(4); // 정점 4개 있는 그래프 생성
        int edge = 4; // 간선의 개수 4개

        for(int i=0;i<edge;i++) {
            String str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            graph.insertDouble(v1, v2);

            /*

             입력(무방향 그래프)

             0 1
             0 2
             1 3
             2 3

             */
        }

        graph.printGraph();
        /*
         출력

         Vertex 0 인접리스트-> 1-> 2
         Vertex 1 인접리스트-> 0-> 3
         Vertex 2 인접리스트-> 0-> 3
         Vertex 3 인접리스트-> 1-> 2

         */

    }

}

참고자료

 

https://freestrokes.tistory.com/87

Java 인접행렬과 인접리스트를 이용하여 그래프 구현하기

 

https://wonit.tistory.com/238

[자료 구조] Java로 그래프 구현하기 :: 인접 리스트로 구현한 그래프