[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 26

* 수업은 JS 기반이지만 Python으로 구현

Section 26

 

그래프 소개

• 그래프란 유한한고 변할 수 있는 꼭지점/노드/점들의 집합으로 구성된 데이터 구조이다.
• 꼭지접들의 집합에 순서가 없는 경우 무방향 그래프, 순서가 있는 경우 유방향 그래프라고 한다.

그래프 사용하는 경우

• SNS
• 지도의 방향 안내, 위치, 길 찾기
• 추천 알고리즘
• 라우팅, 사이트를 요청하고 전체 네트워크에 퍼져있는 것 중 일부 연결 부위를 주는 것

그래프 유형

• vertex: node
• edge: node들 사이의 연결
• 무방향 그래프: edge에 방향이 없는 그래프
• 유방향 그래프: edge에 방향이 있는 그래프
• 가중 그래프: edge에 부여된 값이 있는 그래프
• 비가중 그래프: edge에 부여된 값이 없는 그래프

그래프 정렬

• 인접 행렬
  • 보통 중첩 행렬을 이용하여 boolean 값을 활용한다. 두 개의 노드(각 행과 열의 값)에 연결이 있다면 1, 없다면 0으로 표시한다.
  • 공간을 더 차지한다.
    • 퍼져있는 데이터를 다룰 때 좋지 않다.
  • 모든 edge를 루프를 돌아 확인할 때 더 느리다.
  • 특정 edge를 확인하는데에 빠르다.
• 인접 리스트
  • 인덱스가 노드의 값인데, 그 노드에 연결된 노드의 숫자값을 리스트로 가진다.
  • 만약 노드의 값이 숫자가 아니거나 순서를 갖지 않는 경우, 문자이거나 숫자 사이에 큰 차이가 있는 경우에는 해시 테이블을 활용한다.
  • 공간을 덜 차지한다.
  • 모든 edge를 루프를 돌아 확인할 때 더 빠르다.
  • 특정 edge를 확인하는데에 느릴 수 있다.
• 인접 행렬과 인접 리스트의 Big O
  • |V|: vertices의 숫자
  • |E|: edges의 숫자

동작	인접 리스트	인접행렬
add Vertex	O(1)	O(|V^2|)
add Edge	O(1)	O(1)
remove Vertex	O(|V|+|E|)	O(|V^2|)
remove Edge	O(|E|)	O(1)
query	O(|V|+|E|)	O(1)
storage	O(|V|+|E|)	O(|V^2|)

 

class 소개

• vertex 사이의 연결, edge를 저장할 adjacencyList라는 속성을 선언한다.

addVertex method 소개

• 추가할 vertex를 입력받는 함수를 만든다.
• 정점의 이름을 인접 리스트에 key로 추가하며, value는 빈 배열로 한다.

addEdge method 소개

• vertex1, vertex2를 입력받는 함수를 만든다.
• 인접 리스트에 vertex1 키를 찾아서 vertex2를 그 배열에 넣어주어야 한다.
• 인접 리스트에 vertex2 키를 찾아서 vertex1을 그 배열에 넣어주어야 한다.

 

 

removeEdge method 소개

• vertex1, vertex2를 입력받는 함수를 만든다.
• 인접 리스트에 vertex1 키를 찾아서 vertex2를 그 배열에서 제거해야 한다.
• 인접 리스트에 vertex2 키를 찾아서 vertex1을 그 배열에서 제거해야 한다.

removeVertex method 소개

• 제거할 vertex를 입력받는 함수를 만든다.
• 인접 리스트에 제거할 vertex가 있는 다른 vertex가 있는지 확인하기 위해 모든 로프를 돌아야 한다.
• 루프 내에서 removeEdge 함수를 이용해 제거하고 싶은 vertex와 관련된 모든 edge를 제거해야 한다.
• 인접 리스트에 있는 제거하고 싶은 vertex의 키를 삭제해야 한다.

 

method 구현

class Graph:
    #constructor
    def __init__(self):
        self.adjacencyList = {}

    def addVertex(self, v):
        if not v in self.adjacencyList:
            self.adjacencyList[v] = []

    def addEdge(self, v1, v2):
        self.adjacencyList[v1].append(v2)
        self.adjacencyList[v2].append(v1)

    def removeEdge(self, v1, v2):
        self.adjacencyList[v1] = list(filter(lambda x: x != v2, self.adjacencyList[v1]))
        self.adjacencyList[v2] = list(filter(lambda x: x != v1, self.adjacencyList[v2]))

    def removeVertex(self, v):
        while(len(self.adjacencyList[v])):
            adjacentV = self.adjacencyList[v].pop()
            self.removeEdge(v, adjacentV)
        del self.adjacencyList[v]
        

# addVertex, addEdge, 아래 두 결과가 같은지 확인
# 1
g = Graph()
g.addVertex("Tokyo")
g.addVertex("Dallas")
g.addVertex("Aspen")

g.addEdge("Tokyo", "Dallas")
g.adjacencyList

# 2
g = Graph()
g.addVertex("Tokyo")
g.addVertex("Dallas")
g.addVertex("Aspen")

g.addEdge("Dallas", "Tokyo")
g.adjacencyList


# removeVertex, removeEdge 확인
g = Graph()
g.addVertex("Dallas")
g.addVertex("Tokyo")
g.addVertex("Aspen")
g.addVertex("Los Angeles")
g.addVertex("Hong Kong")
g.addEdge("Dallas", "Tokyo")
g.addEdge("Dallas", "Aspen")
g.addEdge("Hong Kong", "Tokyo")
g.addEdge("Hong Kong", "Dallas")
g.addEdge("Los Angeles", "Hong Kong")
g.addEdge("Los Angeles", "Aspen")
g.adjacencyList

g.removeVertex("Hong Kong")
g.adjacencyList