파이썬 인접행렬과 인접리스트 사용하기

서론

 

요즘 소홀히 하던 알고리즘은 다시 좀 오랜만에 풀어보려한다. 알고리즘도 어찌보면 수학과 비슷한 점이 많다. 수학도 한 2주 정도만 안풀다풀면 뭔가 개념도 기억이 잘 안나고 막히는 게 좀 많다. 알고리즘도 오랜만에 풀면, 개념도 잊어먹고, 막히는게 많은 것이다. 그래서 나도 알고리즘을 소홀히 하지 않기 위해 노력중이다. 자주 풀진 않더라도 감을 잃지 않을 정도만 하려한다.

 

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

 

인접행렬, 인접리스트가 뭐야?

 

인접행렬과 인접리스트는 알고리즘에서 그래프를 표현하기 위한 방법이다.

 

인접행렬

 

인접행렬은 그래프를 표현할 수 있는 방법 중 가장 간단한 방법이다.

인접행렬은 이중리스트를 통해 표현한다.

만약 그래프의 노드의 수가 n개라고 치면 인접행렬의 크기는 n*n이 될 것이다.

그렇기에 그래프가 커지면 잡아먹는 공간도 커지고, 탐색 시간도 비효율적이게 되므로, 그래프의 크기가 작을때 주로 사용한다.

 

예를 들어 4개의 노드가 있고

0번 노드는 1,2번 노드와 연결되어있고, 2번 노드가 3번 노드와 연결 되있다면.

	[0]	[1]	[2]	[3]
[0]	0	1	1	0
[1]	1	0	0	0
[2]	1	0	0	1
[3]	0	0	1	0

이런식으로 이중리스트를 구성하여 구현할 수 있다.(무방향 그래프의 경우)

무방향 그래프는 이렇게 대각선을 기준으로 대칭이 필요하다.

0번노드와 1번노드가 연결되있으면, 0번에서 1번으로 갈 수 있고 반대로 1번에서 0번으로 갈 수 있기 때문.

방향이 있는 그래프의 경우 대칭 없이 표현해야한다.

예를 들어 4개의 노드가 있고

0번 노드는 1번 노드를 향하고 1번 노드가 2번과 3번 노드를 향하고 3번 노드가 0번 노드를 향한다면

	[0]	[1]	[2]	[3]
[0]	0	1	0	0
[1]	0	0	1	1
[2]	0	0	0	0
[3]	1	0	0	0

이런 식으로 구현할 수 있다.

 

인접리스트

 

인접리스트는 인접행렬보다 구현하기 어렵지만, 메모리 공간을 덜 잡아먹고, 탐색시간도 짧은 게 장점이다.

언어마다 차이가 있지만, 파이썬을 사용하는 경우, 난 딕셔너리와 set을 사용하여 인접리스트를 만든다.

 

예를 들어 4개의 노드가 있고,

0번 노드가 1,2번 노드와 연결되어있고, 2번노드가 3번노드와 연결되어있다고하면

 

{0: {1,2}, 1: {0}, 2:{0,3}, 3:{2}}

 

이런식으로 만들 수 있다.

무방향 그래프의 경우 이렇고

 

방향이 있는 그래프라면,

예를 들어 4개의 노드가 있고

0번 노드는 1번 노드를 향하고 1번 노드가 2번과 3번 노드를 향하고 3번 노드가 0번 노드를 향한다면

 

{0:{1}, 1:{1,2},3:{0}}

 

이런식으로 만들 수 있다.

 

만드는 코드

 

인접행렬은 이중리스트이기 때문에 매우 간단히 만들 수 있어 생략한다.

 

인접리스트 코드

k = 4 #k는 간선의 수

graph = {}
    for _ in range(k):
        x, y = map(int, input().split())
        if x not in graph.keys():
            graph[x] = set([y])
        else:
            graph[x].add(y)
        if y not in graph.keys():
            graph[y] = set([x])
        else:
            graph[y].add(x)