[Computer Science] 자료구조 - 그래프

데이터 간의 관계를 표현하기 위한 자료구조
비선형 구조, 트리도 일종의 그래프 중 하나. 

2021.10.04 - [Computer Science] - [Computer Science] 자료구조 - 트리 tree, 순회 traversal 알고리즘

 

그래프와 트리의 차이점 특징

 

 

• 노드 간에 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있다.
• 트리에서는 노드의 탐색에 제한이 있지만, 그래프는 루프 형성이 가능하다. (순환, 사이클)
  • object간의 관계를 표현을 할 때 유용하다.(SNS, 도로 상의 차량 검색, 운송시스템)
• 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다. 
  • 트리에만 있는것 : 계층 개념 

 

그래프 기본 구조

그래프는 vert(노드 또는 정점)와 edge(간선)으로 연결되어있다.

그래프의 유형 특성

1. 방향성 그래프(directed graph)
   방향성 그래프에는 순서가 있으므로 leaf node(마지막 노드, 리프)가 있다. 
   1. One-way directed graph (일방향)
      

      

   2. Bidirectional graph (양방향)
      

      

      
      
      
2. 무방향성 그래프 (undirected graph)
   • 관계의 목적이 상호 교환
   • '교환'관계는 항상 상호 이고, 항상 동일한 노드에 재방문 할 수 있으므로 순환그래프(Cycle graph)이다.
   • edge로 연결된 노드들끼리는 서로 인접(adjacent)해있다고 하며 이웃(neigbor)라고 한다.

   • 

     무방향성은 방향(화살표)이 따로 지정되지 않는다

Cyclic and Acyclic Graphs(순환 및 비순환 그래프)

1. Cyclic graph (순환그래프)
   • 순환(루프)를 형성할 수 있는 경우

   • 

2. Acyclic graph (비순환 그래프)
   • 순환을 형성할 수 없는 경우
   • 모서리를 따라 이미 방문한 노드에 다시 방문할 수 없는 경우

   • 

Directed Acyclic Graphs (DAGs; 방향성 비순환 그래프)

• 순환되지 않는 특정한 단방향 그래프
• edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬 할 수 있다.

• 

 

Weighted Graphs(가중 그래프)

• edge(간선)과 관련된 값 = 가중치
• 각 edge의 가중치에 할당된 특정값을 호출
• 가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타낸다.
• 그래프에서 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다.
  • 모든 경로 비교시 가중치에따라 어떤 경로를 선택할지 사용된다.
    • 예) 도로 구간을 나타내는 그래프에서 가중치는 도로의 길이를 나타낼 수 있다.
•  

  

그래프 탐색

1. 순회(travesal)개념을 사용한다.
2. 중요한것은 아직 방문하지 않은 노드의 순회 순서, 이 순서에 따라 순회 알고리즘이 달라짐
   • 순회 알고리즘 : DFS, BFS 
3. 2021.10.11 - [파이썬] - [Computer Science] 자료구조 - 그래프 탐색 DFS, BFS

그래프 활용

그래프를 나타내는 방법

인전리스트와 인접행렬을 모두 구하면 vertex(정점)및 edge(간선)클래스를 포함하여 더 많은 정보를 파악 할 수 있다.

1. 인접 리스트 (Adjacency List)
   • 전체 노드 목록을 저장, 리스트 개념을 활
   • vert(정점)dms O(1)상수시간에 각 edge(간선)에 접근 할 수 있다.
   • 단점
     • 특정 노드간의 연결관계를 확인하기 위해서는 반복문이 활용되어야 한다.
     • 따라서 O(n)이상의 시간복잡도 요구

   • 

   • # 위 그림에 대해 딕셔너리를 사용한 인접리스트 예시
     # 노드가 키가 되고, 인접노드가 값이 되는 딕셔너리이다.
     # 가장자리 노드들은 set으로 구현되어 있다.
     
     class Graph:
         def __init__(self):
             self.vertices = {
                                 "A": {"B"},  			# 여기서 {"B"}가 set의 형태이다.
                                 "B": {"C", "D"}, 		# {"B" : {}}의 형태는 딕셔너리
                                 "C": {"E"},    		 	# 즉, 딕셔너리 안에 set이 있는 것이다.
                                 "D": {"F":3, "G": 2}, 	# 가중치 부여
                                 "E": {"C": 2},			# 가중치 부여
                                 "F": {"C"},
                                 "G": {"A", "F"}
                             }

2. 인접 행렬 (adjacency martices)
   • 구현이 쉽다. 
   • 행노드와 열결되는 열노드에 대해서 값이 1이 된다.
   • 행렬은 2차원 배열(리스트 안에 리스트가있는)로 표현된다.
   • 기본 제공되는 행렬간에 edge weights(간선 가중치)를 알 수 있다. 
   • 0은 관계가 없음을 나타내고, 다른값은 edge label 또는 edge weight
   • 단점
     • 노드값과 해당 인덱스 사이에 연관성이 없다. 
     • 특정 노드에 방문한 노드들을 알기 위해서는 모든 노드를 확인 해야한다 (시간복잡도 O(n))

   • 

   • # 리스트로 구현한 인접행렬
     
     class Graph:
         def __init__(self):
             self.edges = [[0,1,0,0,0],
                           [0,0,3,2,0],	# 가중치 표현
                           [0,0,0,0,0],
                           [0,0,0,0,0],
                           [0,0,0,1,0]]

그래프 복잡도

 

---

ref.

 

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

https://m.blog.naver.com/occidere/220923695595

[그래프] 쉽게 쓴 그래프 알고리즘 기초 (2018.03.06 수정완료)

https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-graph-%EA%B7%B8%EB%9E%98%ED%94%84/

[자료구조] Graph 그래프 - 하나몬

https://laboputer.github.io/ps/2017/09/29/graph/

[자료구조 1] 그래프(Graph) 이해하기

 

ref. https://itholic.github.io/python-bfs-dfs/

[python] 파이썬으로 bfs, dfs 구현해보기

https://codingcocoon.tistory.com/129

[파이썬][알고리즘] 최단 경로 알고리즘