인접 행렬과 인접 리스트

황은하·2021년 6월 21일

알고리즘

목록 보기

57/100

내용 추가 필요

인접 행렬

#1 정의

그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬.
그래프의 연결 관계를 이차원 배열로 나타내는 방식.

인접 행렬을 adj[][] 라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있다.

adj[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1, 없으면 0

c.f. 만약 간선에 가중치가 있는 그래프라면 1 대신 가중치의 값을 직접 넣어준다.

무방향 그래프일 경우 대각성분(adj[i][j] (i=j일 때))을 기준으로 대칭이다.

#2 예시

#3 장단점

장점:
구현이 쉽다.
노드 i와 노드 j가 연결되었는지 확인할 때 O(1)의 시간복잡도를 갖는다.
adj[i][j] 만 보면 된다.

단점:
노드 i에 연결된 모든 노드를 방문하려고 할 때는 O(V)의 시간복잡도를 갖는다.
adj[i][1] ~ adj[i][j] 까지 돌아야 하기 때문이다.
노드에 비해 간선의 개수가 적을 경우 쓸모없이 공간을 많이 차지한다.

#4 구현

그래프에 대한 정보

노드의 개수
간선의 개수
각 간선의 양 끝 노드

가 주어졌을 때 작성법

import java.util.Arrays;
import java.util.Scanner;

public class AdjMatrix {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt();
        int e = sc.nextInt();

        int[][] matrix = new int[v][v];

        for (int i = 0; i < e; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            matrix[x - 1][y - 1] = 1;
            matrix[y - 1][x - 1] = 1;
        }

        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }
}

출력
[0, 1, 1, 1][1, 0, 1, 0]
[1, 1, 0, 1][1, 0, 1, 0]

출처

인접 리스트

#1 정의

그래프의 연결 관계를 연결 리스트로 구현한 것이다.
그래프의 각 정점에 인접한 정점을 연결리스트로 표현하는 방법이다.

특정 정점에 접근하려면 연결된 모든 정점을 방문해야 한다.
공간복잡도: O(V+E)

#2 특징

필요한 만큼만 메모리를 사용한다.
노드 i와 j의 연결상태를 보려면 모든 원소를 돌아야 하므로 시간이 오래 걸린다.

인접 리스트
연결리스트의 노드는 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 갖는 배열로 갖는다.
= 정점의 번호만 알고 있으면 각 정점의 연결 리스트에 쉽게 접근이 가능하다.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class AdjList2 {
    private LinkedList<Object>[] adjLists;
    private int vertex;

    private static class GraphNode {
        int vertex;
        GraphNode link;
    }

    GraphNode[] head = new GraphNode[10];
    int totalVertex = 0;

    void insertVertex(int v) {
        totalVertex++;
    }

    void insertEdge(int v1, int v2) {
        if (totalVertex <= v1 || totalVertex <= v2) {
            System.out.println("그래프에 없는 정점입니다.");
        } else {
            GraphNode node = new GraphNode();
            node.vertex = v2;
            node.link = head[v1];
            head[v1] = node;
        }
    }
}

출처

가중치가 없는 그래프

인접리스트를 하나 생성하고 노드 개수만큼 반복을 돌며 ArrayList 객체를 할당해준다.
그리고 간선의 수만큼 반복을 또 돌며 그래프 연결 상태를 입력 받고 각각의 그래프에 추가해준다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;

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

        int v = 4;
        int e = 5;

        //인접리스트
        List<ArrayList<Integer>> graph = new ArrayList<>();

        //인접리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }

        /*입력 예시
        1 2
        1 3
        1 4
        2 4
        3 4
        */
        for (int i = 0; i < e; i++) {
            String[] points = br.readLine().split(" ");
            int startPoint = Integer.parseInt(points[0]);
            int endPoint = Integer.parseInt(points[1]);

            graph.get(startPoint).add(endPoint);
            graph.get(endPoint).add(startPoint);
        }

        // 1번 인접 리스트에서 4번 인접 리스트까지 출력
        for (int i = 1; i < 5; i++) {
            bw.write(graph.get(i).toString());
        }
        bw.flush();
        bw.close();
    }
}