TIL_40 : 그래프

🙄 그래프

---

➡ 그래프란?

• 연결 데이터를 저장할 수 있는 자료 구조
  연결 관계 데이터 예시

1. 위치 데이터
   • 장소들 사이의 거리, 걸리는 시간, 최단 경로 계산 등
2. 사회 연결망
   • 팔로우, 팔로잉 관계, 친구 추천 프로그램

➡ 그래프 기본 개념들

• 그래프 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체
• 엣지 : 두 노드의 직접적인 연결 관계 데이터
• 인접해 있다 : 엣지로 연결된 두 노드
• 경로 : 한 노드에서 다른 노드까지 가는 길
• 거리 : 경로에 있는 엣지의 수
• 사이클 : 특정 노드에서 다시 그 노드로 돌아오는 경로
• 차수 : 한 노드가 갖고 있는 엣지의 수

🙄 다양한 그래프

---

➡ 무방향 그래프

• 엣지가 쌍방향인 그래프
• 차수 : 단순히 노드가 가지는 엣지의 수

➡ 방향 그래프

• 엣지가 방향을 가지는 그래프
• A ➡ B : A를 떠나서 B로 들어가는 엣지라고 표현
• 출력 차수 : 노드에서 나가는 엣지의 수
• 입력 차수 : 노드로 들어오는 엣지의 수

➡ 무가중치 그래프

• 모든 엣지의 값이 동일한 그래프
• 거리 : 단순히 경로에 있는 엣지의 수

➡ 가중치 그래프

• 엣지에 특정 숫자값을 지정해 줄 수 있는 그래프
• 거리 : 경로에 있는 모든 엣지 가중치의 합

🙄 그래프 구현

---

➡ 그래프 노드 구현

• 연결 관계를 나타내는 그래프에서는 일반적으로 모든 노드가 동등한 위치에 있다
• 따라서 항상 모든 노드에 바로 접근할 수 있도록 만들어 준다
  1. 노드들을 파이썬 리스트에 저장함으로써 각 노드는 자신에만 해당하는 인덱스를 지정받음
  2. 노드들을 해시 테이블(딕셔너리)에 저장

class StationNode:
    """지하철 역 노드를 나타내는 클래스"""
    def __init__(self, name, num_exits):
        self.name = name
        self.num_exits = num_exits


# 지하철 역 노드 인스턴스 생성
station_0 = StationNode("교대역", 14)
station_1 = StationNode("사당역", 14)
station_2 = StationNode("종로3가역", 16)
station_3 = StationNode("서울역", 16)


# 노드들을 리스트에 저장
stations = [station_0, station_1, station_2, station_3]

# 노드들을 해시 테이블에 저장
stations_1 = {
    "교대역": station_0,
    "사당역": station_1,
    "종로3가역": station_2,
    "서울역": station_3,
}

➡ 엣지 구현_1 : 인접 행렬

인접 행렬

• 노드들의 연결 관계(엣지)를 나타내는 2차원 리스트
• 각 노드를 리스트에 저장해 고유 정수 인덱스를 준다
• 노드 수 X 노드 수 크기의 행렬을 만든다
• 노드들의 엣지 유무 및 가중치에 따라 행렬의 요소를 채운다

# 모든 요소를 0으로 초기화시킨 크기 6 x 6 인접 행렬
adjacency_matrix = [[0 for i in range(6)] for i in range(6)]

# 무가중치 그래프라서 1을 채우고 가중치 그래프라면 가중치를 채워준다
adjacency_matrix[0][1] = 1
adjacency_matrix[0][2] = 1
adjacency_matrix[1][3] = 1
adjacency_matrix[1][5] = 1
adjacency_matrix[2][5] = 1
adjacency_matrix[3][4] = 1
adjacency_matrix[3][5] = 1
adjacency_matrix[4][5] = 1

# 무방향 그래프라서 대칭을 만들어 준다
for i in range(6):
    for j in range(6):
        if adjacency_matrix[i][j] == 1:
            adjacency_matrix[j][i] = 1
print(adjacency_matrix)

➡ 엣지 구현_2 : 인접 리스트

인접 리스트

• 각 노드의 엣지를 리스트에 저장하는 방법
• 노드 클래스에 인접 리스트를 추가시켜줘야 함

class StationNode:
    """간단한 지하철 역 노드 클래스"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.adjacent_stations = []  # 인접 리스트


    def add_connection(self, other_station):
        """지하철 역 노드 사이 엣지 저장하기"""
        self.adjacent_stations.append(other_station)
        other_station.adjacent_stations.append(self)
        
        
from StationNode import *


def create_subway_graph(input_file):
    """input_file에서 데이터를 읽어 와서 지하철 그래프를 리턴하는 함수"""
    stations = {}  # 지하철 역 노드들을 담을 딕셔너리

    # 파라미터로 받은 input_file 파일을 연다
    with open(input_file) as stations_raw_file:
        for line in stations_raw_file:  # 파일을 한 줄씩 받아온다
            subway_line = line.strip().split("-")  # 앞 뒤 띄어쓰기를 없애고 "-"를 기준점으로 데이터를 나눈다
            previous_station = None
            
            for name in subway_line:
                station_name = name.strip()  # 앞 뒤 띄어쓰기 없애기

                # 지하철 역 이름이 이미 저장한 key 인지 확인
                if station_name not in stations:
                    current_station = StationNode(station_name)  # 새로운 인스턴스를 생성하고
                    stations[station_name] = current_station  # dictionary에 역 이름은 key로, 역 노드 인스턴스를 value로 저장한다
                else:
                    current_station = stations[station_name]
                if previous_station is not None:
                    current_station.add_connection(previous_station)
                previous_station = current_station
                    
    return stations

🙄 인접 행렬 vs 인접 리스트

---

➡ 노드를 저장하는 공간

• 노드의 개수 : $V$
• 엣지의 개수 : $E$
• 인접 행렬, 인접 리스트 모두 노드를 저장하는 데는 $O(V)$의 공간 사용

➡ 인접 행렬이 차지하는 공간

• $V$ X $V$ 크기의 행렬을 저장하고 총 $V^2$개의 정수를 저장
• $O(V^2)$의 공간을 사용

➡ 인접 리스트가 차지하는 공간

노드 저장 공간

• 인접 리스트는 각 노드가 자신과 인접한 노드들을 가리키는 레퍼런스를 저장
• 모든 노드는 하나의 인접 리스트를 가짐, $V$개의 배열 또는 파이썬 리스트
• 최소 $O(V)$의 공간 사용

엣지 저장 공간

• 모든 노드에 저장된 엣지 데이터를 다 합치면 무방향 그래프일 때 $2E$, 방향 그래프일 때 $E$
• 총 저장하는 레퍼런스 수는 $E$에 비례 = $O(E)$
• 노드 저장 공간 + 엣지 저장 공간 = $O(V+E)$

➡ 두 노드가 연결됐는지 확인하는 데 걸리는 시간

인접 행렬

• 인덱스를 사용하여 두 노드가 인접했는지 아닌지를 $O(1)$으로 알아낼 수 있다

인접 리스트

• 한 노드의 리스트 안에 특정 역이 저장됐는지를 탐색해야 함
• 선형 탐색을 해야되기 때문에 최악의 경우 $V$개 요소 확인

➡ 한 노드에 연결된 모든 노드를 알아내는 데 걸리는 시간

인접 행렬

• 한 노드를 나타내는 리스트 전체를 다 돌아야지만 그 노드가 연결된 다른 노드들을 갖고 올 수 있다
• $V$개 요소 확인

인접 리스트

• 각 노드가 자신과 인접한 노드들에 대한 레퍼런스를 갖고 있으므로 인접 행렬보다 빠름