그래프

그래프란?

• 연결되어있는 개체간의 관계를 표현한 자료구조
• 정점과 간선의 집합으로 구성
  • 정점(Vertext) : 연결할 개체
  • 간선(Edge) : 개체 관의 관계, 개체를 연결하는 선

그래프 종류

• 방향성에 따라

  • 방향그래프(Directed Graph) : 정해진 방향 없이 양방향으로 갈 수 있다

    셀프엣지(자기자신을 가리키는 간선)를 갖는 그래프도 있다

  • 무방향그래프(Undirected Graph) : 간선에 방향성이 존재한다

• 순환성에 따라
  • 순환 그래프(Cyclic Graph) : 하나이상의 사이클이 있는 그래프
  • 비순환 그래프(Acyclic Graph) : 사이클이 하나도 없는 그래프
• 연결성에 따라
  • 연결그래프(Connected Graph) :
  • 단절그래프(Disconnected Graph)
• 기타
  • 가중치 그래프(Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
  • 완전 그래프(Complete Graph) : 모든 정점이 서로 연결되어 있는 그래프
  • 부분 그래프(Isolated Subgraphs) : 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다

그래프 표현 방법

• Adjacency Matrix : 이차원배열로 표현

  인접하게 연결된 노드들은 1, 그렇지 않은 노드들은 0으로 표현

  가중치 그래프일 경우 1 대신 가중치를 배열에 표현한다

• Adjacency List : linked list로 표현

  배열에 노드들을 나열하고 관계를 linked list로 표현하는 방법

• dictionary: 딕셔너리로 표현

• 방향 그래프 코드 구현

V, E = 5,6
edges = [(1,2), (2,3), (1,4), (2,4),(1,5),(3,5)]

# make Adjacent Matrix
AM = [[0]*(V+1) for i in range(V+1)]

for s,e in edges:
    AM[s][e] = 1
# 출력
for x in AM:
    print(x)

# make Adjacent List
AL = [[] for i in range(V+1)]

for s,e in edges:
    AL[s].append(e)
# 출력
for x in AL:
    print(x)

• 무방향 그래프 코드구현