[Java] Graph (Adjacency Matrix, Adjacency List)

정점(Vertex)과 간선(Edge)로 구성된 것, Graph(G) = (Vertex(V), Edge(E))

 

Graph 용어

 

정점(Vertex) - 노드, 특정할 수 있는 실체

간선(Edge) - 정점 간 이어져 있는 선

가중치(Weight) - 정점 간에 거리, 비용 (간선의 길이라고 생각해도 좋음)

경로(Path) - 출발 정점에서 도착 정점까지의 거쳐 간 순서

순환(Cycle) - 경로의 출발 정점과 도착 정점이 같은 경우

차수(Degree) - 정점에 붙은 간선 수

진입 차수(In-Degree) - 정점으로 들어오는 간선 수

진출 차수(Out-Degree) - 정점에서 나가는 간선 수

Graph 종류

 

유향 그래프(Directed Graph) - 특정 정점에서 특정 정점으로 이동하는 그래프

무향 그래프(UnDirected Graph) - 특정 정점과 특정 정점이 연결된 그래프 (양방향 이동 가능)

가중 그래프(Weighted Graph) - 간선에 가중치(Weight)가 붙음 (유향, 무향으로 표현가능)

비순환 그래프(Acyclic Graph) - 순환이 없는 그래프 

부분 그래프(Sub Graph) - 특정 그래프 내에 존재하는 그래프 

단절 그래프(Disconnection Graph) - 모든 정점이 연결되어 있지 않은 그래프 (여러 그래프가 존재 가능)

 

Tip

 

1. 보통 유향 그래프 또는 무향 그래프이다.

2. 무향 그래프의 경우 A - B 두 정점간에 사이클로 인식할 수 있으므로 방문처리 필수

3. 각 그래프를 조합해서 특정 성질을 띠는 그래프 생성가능 ex) 유향 비순환 그래프 (DAG)

4. 단절 그래프는 알고리즘 문제에서 까먹기 쉬운 성질이다. (보통 Connection Graph로 생각함)

 

구현 (인접 행렬 방식과 인접 리스트 방식)

 

인접 행렬(Adjacency Matrix)

package com.study.datastructrue.graph;

public class AdjacencyMatrix {
    private int[][] directedGraph;
    private int[][] unDirectedGraph;

    public AdjacencyMatrix(int size) {
       this.directedGraph = new int[size][size];
       this.unDirectedGraph = new int[size][size];
    }

    public void dirAdd(int u, int v) {
       directedGraph[u][v] = 1;
    }

    public void dirAdd(int u, int v, int w) {
       directedGraph[u][v] = w;
    }

    public void dirPrint() {
       for (int i = 0; i < directedGraph.length; i++) {
          System.out.print((char)(i + 'A'));
          for (int j = 0; j < directedGraph[0].length; j++) {
             System.out.printf("%2d", directedGraph[i][j]);
          }
          System.out.println();
       }
    }

    public void unDirAdd(int u, int v) {
       unDirectedGraph[u][v] = unDirectedGraph[v][u] = 1;
    }

    public void unDirAdd(int u, int v, int w) {
       unDirectedGraph[u][v] = unDirectedGraph[v][u] = w;
    }

    public void unDirPrint() {
       for (int i = 0; i < unDirectedGraph.length; i++) {
          System.out.print((char)(i + 'A'));
          for (int j = 0; j < unDirectedGraph[0].length; j++) {
             System.out.printf("%2d", unDirectedGraph[i][j]);
          }
          System.out.println();
       }
    }

}

 

인접 리스트(Adjacency List)

package com.study.datastructrue.graph;

import java.util.ArrayList;
import java.util.Objects;

public class AdjacnecyList {

    private ArrayList<ArrayList<Object>> directedGraph = new ArrayList<>();
    private ArrayList<ArrayList<Object>> unDirectedGraph = new ArrayList<>();

    public AdjacnecyList(int size) {
       for (int i = 0; i <= size; i++) {
          directedGraph.add(new ArrayList<>());
          unDirectedGraph.add(new ArrayList<>());
       }
    }

    public void dirAdd(int u, int v) {
       directedGraph.get(u).add(v);
    }

    public void dirAdd(int u, int v, int w) {
       directedGraph.get(u).add(new Edge(v, w));
    }

    public void dirPrint() {
       for (int i = 0; i < directedGraph.size(); i++) {
          System.out.print((char)(i + 'A') + ": ");
          for (Object obj : directedGraph.get(i)) {
             if (obj instanceof Integer) {
                System.out.print((char)((int)obj + 'A'));
             } else if (obj instanceof Edge) {
                Edge edge = (Edge) obj;
                System.out.print("{" + (char)(edge.vertex + 'A') + ", " + edge.weight + "}");
             }
             System.out.print(" -> ");
          }
          System.out.println();
       }
    }

    public void unDirAdd(int u, int v) {
       unDirectedGraph.get(u).add(v);
       unDirectedGraph.get(v).add(u);
    }

    public void unDirAdd(int u, int v, int w) {
       directedGraph.get(u).add(new Edge(v, w));
       directedGraph.get(v).add(new Edge(u, w));
    }

    public void unDirPrint() {
       for (int i = 0; i < unDirectedGraph.size(); i++) {
          System.out.print((char)(i + 'A') + ": ");
          for (Object obj : unDirectedGraph.get(i)) {
             if (obj instanceof Integer) {
                System.out.print((char)((int)obj + 'A'));
             } else if (obj instanceof Edge) {
                Edge edge = (Edge) obj;
                System.out.print("{" + (char)(edge.vertex + 'A') + ", " + edge.weight + "}");
             }
             System.out.print(" -> ");
          }
          System.out.println();
       }
    }
    private class Edge {

       int vertex;
       int weight;

       Edge(int vertex, int weight) {
          this.vertex = vertex;
          this.weight = weight;
       }

    }
}

---

Main

package com.study.datastructrue.graph;

public class Main {

    public static void main(String[] args) {
       AdjacencyMatrix matGraph = new AdjacencyMatrix(5);
       AdjacnecyList listGraph = new AdjacnecyList(5);
       // a -> b, a -> c, a -> d
       // b -> d, d -> e, e -> b
       System.out.println("Directed Adj Matrix Graph");
       System.out.println("  A B C D E");
       matGraph.dirAdd(0, 1);       matGraph.dirAdd(0, 2);
       matGraph.dirAdd(0, 3);       matGraph.dirAdd(1, 3);
       matGraph.dirAdd(3, 4);       matGraph.dirAdd(4, 1);
       matGraph.dirPrint();

       System.out.println();
       System.out.println("Directed Adj List Graph");
       listGraph.dirAdd(0, 1);          listGraph.dirAdd(0, 2);
       listGraph.dirAdd(0, 3);          listGraph.dirAdd(1, 3);
       listGraph.dirAdd(3, 4);          listGraph.dirAdd(4, 1);
       listGraph.dirPrint();

       System.out.println();
       // a - b, a - c, a - d
       // c - d, d - e
       System.out.println("UnDirected Adj Matrix Graph");
       System.out.println("  A B C D E");
       matGraph.unDirAdd(0, 1);      matGraph.unDirAdd(0, 2);
       matGraph.unDirAdd(0, 3);      matGraph.unDirAdd(2, 3);
       matGraph.unDirAdd(3, 4);
       matGraph.unDirPrint();

       System.out.println();
       System.out.println("UnDirected Adj List Graph");
       listGraph.unDirAdd(0, 1);     listGraph.unDirAdd(0, 2);
       listGraph.unDirAdd(0, 3);     listGraph.unDirAdd(2, 3);
       listGraph.unDirAdd(3, 4);
       listGraph.unDirPrint();

    }

}

 

※ Overloading 으로 인해 dirAdd 또는 unDirAdd 메소드에 Argument를 하나 더 추가하면 가중치가 할당된다.

 

 

Result

 (Directed & UnDirected)

Weight Graph

 

인접행렬 vs 인접리스트

 

인접행렬은 두 정점 간에 1번만에 접근할 수 있다.

인접리스트는 두 정점 간에 출발 정점의 간선 개수만에 접근할 수도 있다.

 

인접행렬은 공간을 효율적으로 사용할 수 없다.

인접리스트는 공간을 효율적으로 사용한다.

 

정리 : 인접행렬, 인접리스트 중 구현하기 더 쉬운걸 쓰자. 다만 N > 10,000 인 경우는 무조건 인접리스트!