[Algorithm] - Graph( Node / Edge/ BFS / DFS )

1. Graph

---

Node와 Edge로 이루어진 자료구조

 

 

1-1) Direction fo Edge

---

• Degree = Node에 연결되어 있는 edge의 수

 

 

 

 

 

 

 

• Indegree = Node로 들어오는 edge의 수
• Outdegree = Node에서 나가는 edge의 수
• Airflow의 기본 구조

 

 

 

 

 

 

1-2) 싸이클

---

임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로

• 순환 그래프(Cyclic graph) = 싸이클이 한개 이상
• 비순환 그래프(Acyclic graph) = 싸이클이 X

 

1-3) 연결 그래프

---

• 서로 다른 Node 연결되어 있는 Edge를 보고 완전 그래프 / 연결 그래프인지 확인
• 주의점 : 일반적인 코딩테스트에 나오는 그래프는 단순 그래프(정점 사이의 Edge는 한개이며, 루프가 존재하지 않는다 ) 라는 정의가 있어야만 단순 그래프 형식으로 생각해야 된다!

 

1-4) 표현법

---

• 행렬

편의상 단순 그래프, 즉 두 정점 사이의 간선이 1개 이하인 그래프라고 할 때 연결된 두 정점에는 1을, 연결되지 않은 두 정점에는 0

• 무방향 그래프시 대칭 형태
• 두 점이 연결되어 있는지를 O(1)
• 공간복잡도 O(V²)
• Node와 연결된 Node를 확인 O(V)
• 효율 = 두점의 연결 여부 확인 / E가 V² 에 가까울수록

• 리스트

 인접 행렬과 비교했을 때 정점이 많고 간선은 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식

• 두 점이 연결되어 있는지를 O( min(deg(u) , deg(v) )
• 공간 복잡도 O(V+E)
• Node와 연결된 Node를 확인 O( deg(V) )

 

2. DFS

---

• STACK 혹은 재귀로 구현 가능 ( 재귀로 구현 시와 STACK이랑 구현 시 결과 값이 다를 수 있으니 주의 )

• BOJ 1260 - DFS

import sys
from collections import deque
input = sys.stdin.readline

dfs_answer = []

def dfs ( graph , visited , start ) :
    dfs_answer.append(start)
    visited[start] = 1
    if start in graph :
        graph[start].sort()
        for data in graph[start] :
            if visited[data] :
                continue
            dfs ( graph , visited , data )  

    return dfs_answer
    
def solution( ) :
    n , m , start = map ( int , input().split() )
    graph = dict()
    
    for _ in range( m ) :
        u , v = map ( int ,input().split() )
        if u in graph :
            graph[u].append( v )
        else :
            graph[u] = [v]
        
        if v in graph :
            graph[v].append( u )
        else :
            graph[v] = [u]

    #DFS
    print ( ' '.join ( str(x) for x in dfs ( graph , [False]* ( n + 1 ) , start ) ) )

3. BFS

---

• Queue를 이용하여 구현 가능

• BOJ 1260 - BFS

import sys
from collections import deque
input = sys.stdin.readline

def bfs ( graph , start , visited) :
    answer = []
    queue = deque()
    queue.append( start )
    visited[start] = True

    while ( queue ) :
        temp = queue.popleft()
        answer.append( temp )

        if temp in graph :
            for data in graph[temp] :
                if visited[data] :
                    continue
                visited[data] = True
                queue.append(data)
            
    return answer

def solution( ) :
    n , m , start = map ( int , input().split() )
    graph = dict()
    
    for _ in range( m ) :
        u , v = map ( int ,input().split() )
        if u in graph :
            graph[u].append( v )
        else :
            graph[u] = [v]
        
        if v in graph :
            graph[v].append( u )
        else :
            graph[v] = [u]

    #VFS
    print ( ' '.join ( str(x) for x in bfs ( graph , start , [False]* ( n + 1 ) ) ) )

solution()

 

참조

https://blog.encrypted.gg/1016