dfs/bfs 정리(2)

인접 행렬 : 2차원 배열로 그래피의 연결로 표현하는 방식

public class AdjacencyMatrix {
    public static int INF = Integer.MAX_VALUE;

    public static List<List<Integer>> graph = new ArrayList<>();

    public static void input() {
        // INF는 이동이 불가능한 경우를 뜻한다.
        graph.add(Arrays.asList(0, 7, 5));
        graph.add(Arrays.asList(7, 0, INF));
        graph.add(Arrays.asList(5, INF, 0));
    }

    public static void print() {
        input();
        System.out.println(graph);
    }

    public static void main(String[] args) {
        print();
    }
}

 

인접 행렬은 주로 표 형식으로 그려서 문제를 해결한다.

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

 

인접리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식

class Node {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}
public class AdjacencyList {
    public static List<List<Node>> graph = new LinkedList<>();

    public static void input() {
        for (int i = 0; i < 3; i++) {
            graph.add(new LinkedList<>());
        }

        graph.get(0).add(new Node(1,7));
        graph.get(0).add(new Node(2,5));
        graph.get(1).add(new Node(0,7));
        graph.get(2).add(new Node(0,5));

    }

    public static void print() {
        input();
        System.out.println(graph);
    }

    public static void main(String[] args) {
        print();
    }
}

 

인접 리스트는 표 형식보다

노드와 간선의 그림으로 표현된다.

 

간단히 0번 노드만 그려보았다.

 

여기서 알수 있는건 인접행렬은 결국 integer 로 받아지는데...

인접 리스트는 클래스로 받아진다는 걸 알 수 있다. 

 

코드상에서 두드려지는 차이점은 값을 어떻게 추가하는냐에 많이 달라지는 것 같다.

하나는 그냥 배열로 넣어버리지만

다른 하나는 노드 하나하나당 정성스럽게? 넣어주는 느낌을 받았다.

즉, 인접 행렬이나 인접 리스트는 데이터의 저장 방식에 따라 달라진다는 것을 알 수 있다.

* 인접리스트는 '연결 리스트' 자료 구조를 이용해 구현한다.