Python Algorithm class (Graph - 2)

nathan29849·2021년 5월 13일
0

Python Algorithm class

목록 보기
18/27

Graph

3. Graph 표현

그래프의 표현 방법으로는 크게 두 가지가 있다.

1) 인접 행렬
2) 인접 리스트

  • n : |V| (그래프의 정점 수)
  • m : |E| (그래프의 에지 수)
  • 그래프의 정점 집합 : V = {v0, v1, ..., vn-1}
  • 그래프 G의 n개의 정점들을 0부터 n-1의 정수로 대응시킨다.
    (정점 vi를 정수 i에 대응 시킨다고 가정)

1) 인접 행렬 (Adjacency Matrix) 표현

(1) 그래프 G의 인접 행렬 A = (aij) 표현

  • aij = 1 ((vi, vj)가 E에 속하는 경우 - 인접하는 경우)
  • aij = 0 ((vi, vj)가 E에 속하지 않는 경우 - 인접하지 않는 경우)
  • 무향 그래프에 대한 인접 행렬은 대칭적이다.

무향 그래프 인접 행렬 표현 예시

  • 단, 에지가 없는 것(인접하지 않는것)도 0이라는 하나의 값으로 표현하고 있기 때문에 낭비적이라고 볼 수 있다. (공간적 낭비)

  • 그래프의 입력
    ex.

9 9 	# n m
0 1	# a b
0 3	# a d
0 4     # a e
2 4	# c e
2 3	# c d
5 6	# f g
5 8	# f i
6 8	# g i
6 7	# g h
  • Python Code
class Graph:
   def __init__(self, size):
      self.adjMatrix = [[0 for j in range(size)] for i in range(size)]
      self.size = size
   
   def insertEdge(self, v1, v2):
      self.adjMatrix[v1][v2] = 1
      self.adjMatrix[v2][v1] = 1 # in case of undirected graph
   
   def printGraph(self):
      for i in range(self.size):
         for j in self.adjMatrix[i]
             print(j, end = ' ')
         print()

def main():
   n, m = input().split()
   n, m = int(n), int(m)
   g = Graph(n)
   for i in range(m):
      v1, v2 = input().split()
      v1, v2 = int(v1), int(v2)
      g.insertEdge(v1, v2)
   g.printGraph()

if __name__ = "__main__":
   main()

(2) 가중치 그래프 G = (V, E, W)의 인접 행렬 A = (aij) 표현

  • aij = weight(i, j) ((vi, vj)가 E에 속하는 경우 - 인접하는 경우)
    (weight(i, j)는 에지(vi, vj)의 가중치)

  • aij = c ((vi, vj)가 E에 속하지 않는 경우 - 인접하지 않는 경우)
    (c는 문제에 따라 0 혹은 ∞)

  • (에지에) 가중치가 있는 그래프의 입력

    n : vertex 수
    m : edge 수
    i0, j0 : wt0 (에지 (i0, j0)의 가중치)
    i1, j1 : wt1 (에지 (i1, j1)의 가중치)
    ...
    in-1, jn-1 : wtn-1 (에지 (in-1, jn-1)의 가중치)

2) 인접 리스트 (Adjacency List) 표현

(1) 연결 리스트(Linked List)로 표현

  • 각 정점에 대하여, 이 정점과 인접한 모든 정점들을 연결리스트로 만듦
  • 리스트 i번째의 원소 : vi와 인접한 정점들의 연결리스트를 참조함
  • 인접하지 않은 것의 정보는 갖고 있지 않다.(인접 행렬과의 차이점 - 공간 효율 ↑)
  • Python Code
class Node:
   def __init__(self, vertex):
      self.vertex = vertex
      self.link = None

class Graph:
   def __init__(self, size):
      self.adjList = [None] * size
      self.size = size
   
   def insertEdge(self, v1, v2):
      newNode = Node(v2)
      newNode.link = self.adjList[v1]
      self.adjList[v1] = newNode
      
      # in case of undirected graph
      newNode = Node(v1)
      newNode.link = self.adjList[v2]
      self.adjList[v2] = newNode
   
   def printGraph(self):
      for v in range(self.size):
         print(v, end = ': ')
         current = self.adjList[v]
         while current is not None:
            print(current.vertex, end =' ')
            current = current.link
         print()
    
   def main():
      n, m = input().split()
      n, m = int(n), int(m)
      g = Graph(n)
      for i in range(m):
         v1, v2 = input().split()
         v1, v2 = int(v1), int(v2)
         g.insertEdge(v1, v2)
      g.printGraph()
      
   if __name__ == "__main__":
      main()

(2) List of lists 로 표현

  • Node로 따로 표현하지 않고, 리스트 속에 리스트를 넣어 인접한 정점들을 관리한다.

  • Python Code

class Graph:
   def __init__(self, size):
      self.adjList = [[] for i in range(size)]
      self.size = size
   
   def insertEdge(self, v1, v2):
      self.adjList[v1].append(v2)	# 인접 정점들을 리스트의 마지막에 집어 넣음
      # in case of undirected graph
      self.adjList[v2].append(v1) 	# 인접 정점들을 리스트의 마지막에 집어 넣음
      
   def printGraph(self):
      for v in range(self.size):
         print(v, end = ': ')
         for x in self.adjList[v]:
            print(x, end = ' ')
         print()

n, m = [int(x) for x in input().split()]	# 이렇게도 표현할 수 있구나.. map(int, input().split()) 이거랑 같음
g = Graph(n)
for i in range(m):
   v1, v2 = [int(x) for x in input().split()]
   g.insertEdge(v1, v2)
g.printGraph()
  • append : 동적으로 배열 크기가 할당된다. (amortized : 기본적인 크기가 먼저 주어지고, 점점 커짐, 줄기도 함)
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글