그래프 알고리즘

그래프

• 정점(Vertex) , 간선(Edge) , 가중치(Weight) 총 세가지 정보가 필요하다
• 무향 그래프 : 방향이 존재하지 않는다. 정점간 가중치가 없으며, 양방향이다
• 유향 그래프 : 단방향이거나, 가중치가 다른 양방향 그래프

<인접행렬>

• 정점의 개수 n -> nxn 행렬
• n제곱의 공간이 필요하다
• 순차탐색인 경우 n제곱의 시간이 걸린다
• 무향 그래프, 유향 그래프, 가중치가 있는 경우, 가중치가 없는 경우 모두 표현 가능
• 간선의 밀도가 낮으면 비효율적일 것이다 (대부분 0으로 채워지기 때문)

<인접 리스트>

• 연결 리스트 사용
• 필요할 때마다 공간을 할당해 사용하기 때문에 간선의 밀도가 낮아도 상관이 없다.
• 가중치가 있는 경우 주소가 가리키는 값과 해당 값에 갈 수 있는 가중치를 같이 적어준다.

<인접 배열>

• 각 정점에 연결된 정점들을 연결 리스트 대신 배열로 표현
• 배열을 정렬된 형태로 구성 -> 이진 탐색 가능
• 이진 탐색시 간선 여부 확인을 위한 비교 횟수
  -> 인접한 정점 개수가 k개이면 O(logk)번 이내의 비교
• 각 노드마다 자신이 갈 수 있는 노드의 개수를 적어주고, 주소가 가리키는 배열에는 갈 수 있는 노드의 번호를 오름차순으로 나열해준다
• 정점 개수 대신 끝 인덱스를 표시하는 경우 아래와 같이 나타낸다
  
  -> 노드의 번호가 적힌 배열과 실제 배열 총 두개의 배열만 관리하면 된다

BFS 와 DFS

• 두 알고리즘 모두 브루트포스(완전탐색) 알고리즘에 기반한 알고리즘이다.

< BFS >

• Python에서는 while문과 for문, Deque를 이용해서 구현할 수 있다.
• BFS는 다음 블로그에서 자세히 다룰 예정이다

< DFS >

• Python에서는 재귀문을 이용하여 구현할 수 있다.
• 탐색순서 : 1->2->4->9->5->6->10->11->3->7->8->12->13
• 중복 탐색을 방지하기 위해 방문여부를 체크해야 한다.
  -> 주로 visited라는 배열을 통해 기록한다.
  -> True/False의 불리안 값이나, 정수값으로 표현해 방문여부를 기록한다.
  📌 정수값으로 방문여부를 체크할경우 방문여부뿐 아니라 해당 노드까지 걸린 거리/시간 등을 체크할 수 있다.

DFS(v)
    visited[v]=True # 방문 기록 
    for x->L(v) # L(v) : v의 인접 정점들의 집합 
        if visited[x]==False # 방문 여부 체크
            DFS(x) # 이동한 노드로부터 재귀 호출