[자료 구조] 자바를 이용한 그래프의 구현-인접 행렬 구현 :: Graph implementation by using adjacency matrix in java.

인접 행렬

인접 행렬은 G= {V, E} 의 그래프를 boolean의 행렬로 나타낸 것이다.

행렬의 상태에는 두 가지가 있다.

• M[i][j] = 1인 경우
• M[i][j] = 0인 경우

행렬의 상태값이 1인 경우는 그래프가 간선에 의해 연결되어 있을 때, 즉 i, j가 그래프에 존재할 때를 뜻하고 그렇지 않을 때는 0이라고 표현한다.

인접 행렬의 특징

인접 행렬을 이용하는데 가장 큰 장점은 바로 간선의 존재 유뮤이다.

 

정점 u와 정점 v를 연결하는 간선이 존재하는지 확인하기 위해서는 M[u][v]의 값이 1인 경우와 0인 경우만 조사하면 되기 때문에 시간 복잡도가 O(1)인 상수 시간이 나온다.

또한 인접 행렬은 n개의 정점을 갖는 그래프를 인접 행렬로 표현하고자 한다면 간선의 수와는 무관하게 항상 n^2의 메모리 공간이 필요하다는 것도 하나의 특징이다.

인접 행렬의 장점

• 간선의 삽입, 삭제, 탐색에 대한 속도가 엄청나게 효율적이다.
• 그래프의 밀도가 높거나 크기가 클 때 많이 사용된다.
• 행렬에 대한 연산이 요즘 GPU의 성능으로 인해서 많이 발전되었기 때문에 매우 강력하다.
• 간선과 노드 사이의 관계를 쉽게 파악할 수 있다.

인접 행렬의 구현

 

출처 : https://www.programiz.com/dsa/graph-adjacency-matrix

 

class Adjacency_Matrix {
    private boolean[][] adjMatrix;
    private int vertex;

    public Adjacency_Matrix(int vertex){
        adjMatrix = new boolean[vertex][vertex];
    }

    void addEdge(int i, int j){
        adjMatrix[i][j] = true;
        adjMatrix[j][i] = true;
    }

    void removeEdge(int i, int j){
        adjMatrix[i][j] = false;
        adjMatrix[j][i] = false;
    }
}