🔥 목차 🔥

1. Graph

🧐 그렇다면 꼬! 🧐

💡 Graph

• 나같은 경우는 처음에 보고 X,Y축이 있는 수학시간에나 볼법한 그래프 인줄 알았다
• 하지만 컴퓨터 공학에서의 그래프는 조금 다른모습을 가지고 있다
  
• 위 사진처럼 관계성없이 얽히고 섥혀있는데 복잡한 네트워크 망처럼 생겼다

Graph의 구조

• 직접적인 관계가 있는 경우에 두 점 사이를 이어주는 선이 있음
• 간접적 관계라면 몇개의 점과 선에 걸쳐서 이어짐
• 하나의 점을 그래프에서는 정점(vertex)라고 하고 하나의 선은 간선(Edge)라고 한다

Graph의 표현 방식

• 인접 행렬
  • 두 정점을 이어주는 간선이 있다면 두 정점은 인접하다 라고 이야기함
  • 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
  • 만약 이어져있다면 1(true), 이어져있지 않다면 0(false)로 표시한 일종의 표임
  • 만약 가중치 그래프라면 1대신 관계에서 의미있는 값을 저장함
• 인접 행렬은 언제 사용하는지?
  • 한개의 큰 표와 같은 모습을 하고 있기 때문에 두 정점 사이에 관계가 있는지 없는지를 확인하기가 좋음
  • 가장 빠른 경로를 찾고자 할때 주로 사용됨
• 인접리스트
  • 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현함
  • 각 정점마다 하나의 리스트를 가지고있고 이 리스트는 자신과 인접한 다른 정점의 정보를 가지고있음
    
  • 위와같은 형태를 띄고있고 순서가 딱히 중요하지는 않음
  • 우선순위를 다뤄야 한다면 더 적합한 자료구조를 사용하는게 합리적임(언제나 예외는 있을 수 있음)
• 인접 리스트는 언제 사용하는지?
  • 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용함
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함

알아둬야 할 Graph 용어들

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
• 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프임
  • 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능함
  • 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능함(혹은 그 반대)
  • 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다.
  • 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다
  • 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.