알고리즘 - 9(Graph Algorithm)

directed, undirectd

• undirected(방형성이 없음)
  • 보통 일반적인 그래프
  • 
  • V 2개에 E 1개
  • 각각을 집합으로 표현 {}
• directed(방향성이 있음)
  • 
  • 엣지를 집합으로 표현하지 않았음 ()

---

특성

• complte 그래프
  • 모든 V쌍에 대해 엣지가 다 연결됨
    • V가 n개면 E는 n(n-1)/2개
• 인접
  • v,w를 잇는 엣지가 있으면 v,w는 인접하다고 할 수 있고 vAw로 표시한다(adjacency)
• 경로 Path
  • 중간 경로가 distinct(중복이 없는)한 엣지의 집합
• connected
  • 그래프 내에서 어떤 두 V를 잡더라도 경로가 존재해야 connected하다고 함
• cycle
  • 시작과 끝 V가 같은 경로
  • acyclic -> 사이클이 없는 것
  • tree구조는 acyclic하면서 connected함
    • 
• 분할
  • 그래프가 connected하지 않으면 여러개의 서브 그래프로 분할 할 수 있음
  • 분할할때는 서브그래프가 최대로 connected하게 해야함
    • 
    • 이건 3개로 분할가능
• weight
  • 엣지에 가중치를 부여 가능

---

그래프의 저장

• 그래프의 관계를 저장하는 방법
• undirected 그래프는 대칭적인 매트릭스로 표현됨
  • 
• linked list로도 가능
  • 
  • 계속 연결시키는건 아니고
  • 연결된 노드를 다 연결시킨 것
• Weighted Diagram
  • 
  • linked list에 필드 1개를 추가
    • 

---

DFS, BFS

• 
• bfs는 큐를 사용(iterative)
• dfs는 스택(iterative), 재귀 둘다 가능
  • ABFEIGCH는 스택사용의 결과
• DFS로 tree를 만들 수 있음
  • 
  • 만약 undirected그래프면 cross, descendant엣지가 없음

---

Biconnected component

• articulation point : 제거하면 connected하지 않게 되는 지점
• 바이커넥티드는 articulation point가 없는 그래프
• 
• a에서 articulation point는 f,e,b임