[자료구조] 그래프(Graph)

그래프(Graph)

👉 그래프란?

정점(Vertex)과 정점 사이를 이어주는 간선(Edge)

---

그래프 용어

• 단순 그래프(Simple Graph)

  • '루프'와 '다중 간선'이 없는 그래프

다중 간선	루프

• 연결 그래프(Connected Graph)

  • 모든 정점이 직,간접적으로 연결되어 있는 그래프

• 연결 컴포넌트(Connected Component)

• 무방향 그래프(Undirected Graph)

  • $(v_1,v_2) = (v_2,v_1)$

• 방향 그래프(Directed Graph)

  • $(v_1,v_2) \neq (v_2,v_1)$

• 완전 그래프(Complete Graph)

  • $n$ : 정점의 수
    
    
  • $K_n$
    
    
  • 모든 정점의 개수 : $nC_2$

• 부분 그래프(SubGraph)

• 클릭(Clique)

• 정점의 차수(Degree)

  • 하나의 정점과 연결된 간선의 수

• 진입 차수(In-Degree)

  • 방향그래프에서 들어오는 간선의 수

• 진출 차수(Out-Degree)

  • 방향그래프에서 나가는 간선의 수

• 경로(Path)

  • 시작점과 끝점 까지의 간선

• 단순경로(SimplePath)

  • 한 정점을 여러 번 지나지 않는 경로

• Cycle(회로)

  • 단순경로에서 시작 정점과 끝 정점이 동일한 경우

• DAG(Directed Acyclic Graph)

  • Cycle이 없는 방향그래프

• 트리 그래프 (TreeGraph)

  • 사이클이 없는 무방향 연결그래프
    = 임의의 두 정점 사이에 정확히 하나의 경로만 존재하는 무방향 그래프
    = 간선의 개수가 정점의 개수보다 하나 적은 연결 그래프

---

그래프 표현

• 인접행렬 Adjacency Matrix
• 인접리스트 Adjacency list