[자료구조] 그래프

Graph

Definition

• Node(Vertex)

• Edge

  • undirected edge(무방향 간선)
    • 무방향 그래프

    • 

  • directed edge(방향 간선)
    • 방향 그래프

    • 

  • weighted edge
    • 가중치 그래프(방향/무방향 그래프)

    • 

• Subgraph

  • 그래프의 부분이면서 그 자체로 그래프인 것

• Connected Graph

  • 한 노드에서 출발했을 때 모든 노드를 방문할 수 있는 그래프

• Disconnected Graph

  • 한 노드에서 출발했을 때 모든 노드를 방문할 수 없는 그래프

• Adjacent Nodes

  • edge로 서로 연결되어있는 인접한 두 개의 노드

• Complete(Connected) Graph

  • 모든 노드가 다른 노드의 인접한 노드인 그래프

Graph Algorithms

• Graph representation
• Graph traversal
• Spanning tree
• Minimum spanning tree
• Minimum spanning tree Algorithms
• Transtive closure Algorithms

Graph Representation

• Adjacency Matrix
  • n x n 2차원 행렬을 만든다
    • n은 그래프의 노드 개수
  • 노드가 인접해있으면 1, 아니면 0으로 채운다

  • 

• Adjacency Lists
  • 각 노드들에 대해 인접한 노드를 연결리스트로 만든다

  •