Graphs

G = (V,E) V: set of nodes(vertexes) E: set of Edges(arcs)

Directed Graph

• Directed: edges are ordered pairs
• Undirected: unordered (a,b) == (b,a)

Representation

1. Adjacency Matrix

   Mij=1 if (i,j) is edge

   

• O(V^2) 공간 복잡도
• (u,v) 확인하는 데에 O(1) 걸림
• 모든 edge 확인에 O(V^2) 걸림

1. Adjacency List

   linked list

   

• O(V+E) 공간 복잡도 → 작다
• (u,v) 확인하는 데에 O(min(deg(u),deg(v))) 걸림
• 모든 edge 확인에 O(V+E) 걸림

DFS

• DFS의 결과

  • DFS Tree 방문하지 않은 노드를 방문할 때 사용한 간선들의 집합이다 Tree Edge: 이 트리의 간선 Back Edge: 트리에 없는 간선

    • Back Edge의 두 점은 ancestor/descendant 관계를 가진다

    

<aside> 💡 증명: DFS를 통해 어떤 v에서 도달 가능한 모든 노드를 찾을 수 있다

</aside>

• 귀류)

  

  u는 v에서 reachable 하지만 DFS에서 u를 찾지 못했고, DFS가 z에서 끝났다고 하자. 그러면 z 바로 다음에 위치한 w 또한 탐색을 했어야 할 것! → 모순 따라서 무조건 u를 탐색하게 된다.

<aside> 💡 reachable 계산의 시간 복잡도는 O(V+E) 이다

</aside>