[문제풀이] 07-10. 그래프와 인접행렬

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0710. 그래프와 인접행렬

🗒️ 문제

🎈 나의 풀이

	public static void undirectionalGraph() {
        int[][] graph = new int[6][6];

        graph[1][2] = graph[2][1] = 1;
        graph[1][3] = graph[3][1] = 1;
        graph[2][4] = graph[4][2] = 1;
        graph[2][5] = graph[5][2] = 1;
        graph[3][4] = graph[4][3] = 1;
    }

    public static void directionalGraph() {
        int[][] graph = new int[6][6];

        graph[1][2] = 1;
        graph[1][3] = 1;
        graph[2][5] = 1;
        graph[3][4] = 1;
        graph[4][2] = 1;
    }

    public static void weightedOrientationGraph() {
        int[][] graph = new int[6][6];

        graph[1][2] = 2;
        graph[1][3] = 4;
        graph[2][5] = 5;
        graph[3][4] = 5;
        graph[4][2] = 2;
    }

💬 짚어가기

그래프와 인접행렬을 코드로 표현할 때 2차원 배열을 사용하여 구현할 수 있다.
n개의 정점으로 이루어진 무방향 그래프는 n*n 배열을 생성하여 표현한다.

▶︎ 무방향 그래프
각 간선이 연결된 정점에 해당하는 배열 요소 두 곳에 1을 보관한다.

정점 2와 5가 인접한 경우(둘을 잇는 간선이 존재하는 경우)
arr[2][5] = 1;
arr[5][2] = 1;
두 요소 모두 1을 보관한다.

▶︎ 방향 그래프
각 간선이 연결된 방향에 맞도록 정점에 해당하는 배열 요소에 1을 보관한다.

정점 1에서 3을 가르키는 간선이 존재하는 경우
arr[1][3] = 1;
해당 요소에 1을 보관한다.

▶︎ 가중치 방향 그래프
각 간선이 연결된 방향에 맞도록 정점에 해당하는 배열 요소에 가중치를 보관한다.

정점 4에서 2를 가르키는 간선이 존재하고, 가중치가 3인 경우
arr[4][2] = 3;
해당 요소에 가중치 3을 보관한다.