[자료구조] Undirected Graph - 2차원 배열

Undirected Graph - 2차원 배열

그래프라 하면 꼭지점(vertex)와 간선(edge)가 존재합니다.

가중치가 있을 수도 있고, 또는 방향성이 존재할 수도 있습니다.

하지만 그 둘다 없는 방향성도 가중치도 없는 그래프를 2차원 배열로 만들어보고자 합니다.

 

 

만약 그래프가 이렇다면, 마치 직사각형 같다고 생각해봅시다.

여기서 꼭지점은 1, 2, 3, 4 이고 간선은 1-2, 2-4, 3-4, 1-3입니다.

결국 꼭지점의 갯수는 4개이고 간선의 갯수도 4개입니다.

이걸 코드로 표현한다면 아래와 같습니다.

 

public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int vertex = 4; // 꼭지점
        int edge = 4; // 간선
        int u, v; // 꼭지점들
        int[][] node = new int[vertex+1][vertex+1];
        
        node[1][2] = node[2][1] = 1;
        node[2][4] = node[4][2] = 1;
        node[3][4] = node[4][3] = 1; // undirected라서 둘 다 해줍니다.
        node[1][3] = node[3][1] = 1; // 둘이 연결되어 있다면 1
        
        for (int i = 0;i < vertex + 1;i++){
            for (int j = 0;j < vertex + 1;j++){
                if (node[i][j]==1){
                    System.out.println(i+" "+j); //출력
                }
            }
        }
    }

 

이런 식으로 됩니다.

vertex에 1을 더해준 이유는 보통 그래프는 1부터 시작하기 때문입니다. 그리고 끝 번호도 포함하는게 대부분입니다.