그래프

정의

 연결 데이터를 저장할 수 있는 자료 구조

 

용어

 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체

 엣지 : 그래프에서 두 노드의 직접적인 연결 관계 데이터

 인접 :  두 노드가 엣지로 연결되어 있을 때  

 경로 :  한 노드에서 다른 노드까지 가는 길

 차수 :  한 노드가 갖고 있는 엣지의 수, 하나의 노드에 연결된 엣지들의 수

 

종류

 무방향 그래프 : 노드의 엣지가 쌍방향일때

 방향 그래프 : 엣지가 떠나는 노드를 앞에 쓰고 들어가는 노드를 뒤에 적는 방식, ex) 팔로우 기능, A -> B (A,B)

  - 출력 차수 : 노드에서 나가는 엣지의 수

  - 입력 차수 : 노드에서 들어오는 엣지의 수

 가중치 그래프 : 한 경로에 있는 엣지의 가중치의 합

 비가중치 그래프 : 한 경로에 있는 엣지의 수

 

구현(노드, 엣지)

# 지하철역
class StationNonde:
	"""지하철 역 노드를 나타내는 클래스"""
    def __init__(self, name, num_exits):
    	self.name = name
        self.num_exits = num_exits
    
# 지하철 역 노드 인스턴스 생성
station_0 = StaionNode("교대역", 14)
station_1 = StaionNode("사당역", 14)
station_2 = StaionNode("종로3가역", 16)
station_3 = StaionNode("서울역", 16)

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

# 지하철 역 노드들을 파이썬 딕셔너리에 저장한다
stations = {
	"교대역" : station_0,
    "사당역" : station_1,
    "종로3가역" : station_2,
    "서울역" : station_3
}

node_1 = stations["교대역"]
node_2 = stations["서울역"]

# 노드 구현
class StationNode:
    """간단한 지하철 역 노드 클래스"""
    def __init__(self, station_name):
        self.station_name = station_name
        


def create_station_nodes(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("-")  # 앞 뒤 띄어쓰기를 없애고 "-"를 기준점으로 데이터를 나눈다

            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로 저장한다

    return stations



stations = create_station_nodes("./stations.txt")  # stations.txt 파일로 그래프 노드들을 만든다

# 테스트 코드
# stations에 저장한 역들 이름 출력 (채점을 위해 역 이름 순서대로 출력)
for station in sorted(stations.keys()):
    print(stations[station].station_name)

 

구현(엣지, 인접행렬)

 인접행렬

  1. 노드들의 연결 관계(엣지)를 나타내는 2차원 리스트

  2. 각 노드를 리스트에 저장해 고유 정수 인덱스를 준다.(2차원 행렬)

  3. 노드 수 x 노드 수 크기의 행렬을 만든다.

  4. 노드들의 엣지 유무 및 가중치에 따라 행렬의 요소를 채운다.

인접 행렬

가중치 그래프

방향 그래프

구현(인접 행렬)

adjacency_matrix = [[0 for i in range(6)] for i in range(6)]

adjacency_matrix[0][1] = 1
adjacency_matrix[1][0] = 1

adjacency_matrix[0][2] = 1
adjacency_matrix[2][0] = 1

adjacency_matrix[1][5] = 1
adjacency_matrix[5][1] = 1

adjacency_matrix[1][3] = 1
adjacency_matrix[3][1] = 1

adjacency_matrix[2][5] = 1
adjacency_matrix[5][2] = 1

adjacency_matrix[3][5] = 1
adjacency_matrix[5][3] = 1

adjacency_matrix[3][4] = 1
adjacency_matrix[4][3] = 1

adjacency_matrix[4][5] = 1
adjacency_matrix[5][4] = 1

print(adjacency_matrix)

 

구현(인접 리스트)

 인접 리스트 : 노드들의 인접 데이터를 리스트에 저장하는 방법

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)


    def __str__(self):
        """지하철 노드 문자열 메소드. 지하철 역 이름과 연결된 역들을 모두 출력해준다"""
        res_str = f"{self.station_name}: "  # 리턴할 문자열

        # 리턴할 문자열에 인접한 역 이름들 저장
        for station in self.adjacent_stations:
            res_str += f"{station.station_name} "

        return res_str
       

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:  # 파일을 한 줄씩 받아온다
            previous_station = None  # 엣지를 저장하기 위한 도우미 변수. 현재 보고 있는 역 전 역을 저장한다
            subway_line = line.strip().split("-")  # 앞 뒤 띄어쓰기를 없애고 "-"를 기준점으로 데이터를 나눈다

            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]  # 이미 저장한 역이면 stations에서 역 인스턴스를 갖고 온다

                if previous_station is not None:
                    current_station.add_connection(previous_station)  # 현재 역과 전 역의 엣지를 연결한다

                previous_station = current_station  # 현재 역을 전 역으로 저장

    return stations


stations = create_subway_graph("./stations.txt")  # stations.txt 파일로 그래프를 만든다

# stations에 저장한 역 인접 역들 출력 (채점을 위해 역 이름 순서대로 출력)
for station in sorted(stations.keys()):
        print(stations[station])