Graph

• 정점(node)의 집합과 간선(edge)의 집합으로 이루어져있다
  • 간선의 방향성에 따라 무방향과 방향 그래프로 나뉜다
  • 정점을 있는 선이 간선
  • 간선들에 값을 줄 수 있다
    • 비용이라 칭하며 간선들에 비용이 있는 그래프를 가중그래프(가중치그래프)라 한다
• 서로 다른 개체(혹은 객체)가 연결되어 있다면 높은 확률로 그래프 알고리즘
  
  
  
  
  

트리와의 차이점

• 컴퓨터공학 분야에서는 트리를 방향 그래프라 간주

	그래프	트리
방향성	방향 or 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드X	루트 노드O
노드간 관계성	부모-자식X	부모-자식O
모델의 종류	네트워크 모델	계층 모델

구현

인접 행렬(Adjacency Matrix) : 2차원 배열을 이용해 연결 관계 표현

• 간선 정보 저장하는데 O(V2)만큼의 메모리
  • V : 노드의 개수
  • 노드 수 적은 경우, 점 2개 연결 판단 필요한 경우(일반적인 조회)에 유리
• 특정 노드로부터 이어져있는 간선 찾을 때 O(1)의 시간걸림
• EX) 플로이드 워셜 알고리즘 : 인접 행렬 이용

인접 리스트(Adjacency List) : 리스트를 이용해 연결 관계 표현

• 연결 리스트(튜플 이용해 노드 간선 표현) 자료구조를 이용해 구현
  • 특정 점과 연결된 간선 순회 시에 유리
  • C++, JAVA의 경우 lib 이용, python의 경우 기본 자료형인 리시트 사용
• 간선 정보 저장하는데 O(E)만큼의 메모리
  • E : 간선의 개수
• 탐색하는데 O(V)만큼 시간 걸림