컴퓨터 알고리즘 - 그래프 알고리즘 (5/22)

최수환·2023년 5월 22일
0

컴퓨터 알고리즘

목록 보기
12/14
post-thumbnail

그래프 알고리즘

그래프

  • 정점(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) # 이동한 노드로부터 재귀 호출 
            
profile
성실하게 열심히!

0개의 댓글