• 노드간에 연결될수 있다는 점에서 트리와 비슷하며 루프를 형성할수도 있다.
• 트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프 형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조이다. (ex. object간의 관계를 표현할때 유용)

• 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다.

• 트리에는 계층 개념이 있지만 그래프에는 없다.

  

  그래프 유형:

  • Directed/Undirected (방향성/무방향성)

  • 그래프가 한쪽 방향으로 가면 directed

    

  • 그래프가 양방향으로 갈수 있는거 역시 directed

    

  • 그래프의 노드 연결관계가 상호 교환이라면 undirected

    

    Cyclic vs. Acyclic Graphs(순환 vs 비순환 그래프)

    • Cyclic:

      • 방문한 노드를 다시 방문 할수 있음

      • **Undirected Graph는 노드를 재방문 할수 있기 때문에 순환그래프이다

        

    • Acyclic

      • 모서리를 따라 이미 방문한 노드를 방문할수 없음

        

  Weighted Graphs (가중 그래프)

  • 각 edge(간선)의 가중치에 할당된 특정값을 호출한다.
  • 가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타낸다.
  • 그래프에서 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다.

    • 가중치는 모든 경로 비교시, 어떤 경로를 선택할지에 사용된다.

      

  Traversal (순회)

  • 순회는 그래프에 연결된 노드를 탐색한다.
  • 중요한것은 아직 방문하지 않은 노드의 순회 순서이다
  • 순회 개념은 DFS/BFS와 같은 순회 알고리즘과 연관 되어있다

  

  Directed Acyclic Graphs (DAGs)

  • 방향성 비순환 그래프(DAG)는 순환되지 않고 특정한 단방향 그래프이다.

  • 아래 그림처럼 edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬할 수 있다.

    

Graph의 활용

• Adjacency List(인접리스트) - 그래프의 전체 노드 목록을 저장한다

  • 리스트를 사용한다
  • 실제 연결된 관계만 저장해주기 때문에 실행시간에 영향을 적게 준다
  • 단점: 특정 노드간의 연결관계를 확인 하기 위해서는 반복문이 활용되어야 하며 O(N)이상의 시간복잡도가 된다

  

• Adjacency Matrices(인접행렬)- 0과 1로 구성되는 행렬부분(노드간 연결)이 어떤 부분인지 그려본다

  • 배열을 사용한다
  • 구현이 쉽다
  • 단점: 특정노드에 방문한 노드들을 알기 위해서는 모든 노드를 확인해야된다 (시간 복잡도 O(N))