Vertex/Node (정점)
Edge (간선)
Weight (가중치)
Undirected graph (무방향 그래프)

그래프 표현

• Adjacency list (인접 리스트): dictionary
  • better for sparse graphs
• Adjacency matrix (인접 행렬): 2D list
  • better for dense graphs

Search

Breadth First Search (BFS, 너비 우선 탐색)

• traverse the nodes layer by layer in the order of increasing distance from the starting node
  • all the nodes in the same layer are visited before we process the next layer
• only iterative (queue): FIFO

from collections import deque

def bfs(start_v)
	discovered = [start_v]
    queue = deque()
    queue.append(start_v)
    while queue:
    	v = queue.popleft()
        for w in graph[v]:
          if w not in discovered:
              discovered.append(w)
              queue.append(w)
    return discovered

• O(V+E)
  • we check over V nodes and total of E edges (once for directed, twice for undirected)
• O(E) if the graph is connected

Applications

• shortest path in an unweighted graph
• finding connected components
• finding strongly conected components in a directed graph

Depth First Search (DFS, 깊이 우선 탐색)

• recursively explore the graph, backtracking when necessary (reach a "dead end")

def dfs(v, discovered=[]):
	discovered.append(v)
    for w in graph[v]:
    	if w not in discovered:
        	discovered = recursive_dfs(w, discovered)
    return discovered

• O(V+E)
  • we check over V nodes and total of E edges (once for directed, twice for undirected)
• O(E) if the graph is connected

Iterative version (stack): LIFO

def dfs(start_v):
	discovered = []
	stack = [start_v]
    while stack:
    	v = stack.pop()
        if v not in discovered:
        	discovered.append(v)
            for w in graph[v]:
            	stack.append(w)
    return discovered

• here, list is used to implement stack (could use deque instead)

Applications

Modified DFS is very versatile

• Cycle Detection
• Topological Sort for Directed Acyclic Graph (DAG)

Backtracking

• 가능성이 없다고 판단되는 즉시 후보를 포기 (백트랙)
• DFS의 범주에 속함? (DFS+pruning?)
• 제약 충족 문제(CSP, Constraint Satisfaction Problem)에 유용
  • 수많은 제약 조건(constraints)을 충족하는 상태(states)를 찾아내는 수학 문제

Shortest Path

Shortest Paths are not applicable for negatice cycles.
For negative cycles, only detection is possible

• no shortest path can be found in negative cycles
• Belllman-Ford, Floyd-Warshall

Single Source

Summary

Algorithm	-ve Edge	Cycle	Detect -ve Cycle	Representation	Time	Space
In DAG	y	n	n	Adj list	O(V+E)	O(V)
Bellman-Ford	y	y	y	Adj list	O(VE)	O(V)
Dijkstra	n	y	n	Adj list	O(ElogV)	O(V)

Dijkstra

• always choose the unvisited node with smallest d value available
• very similar to Prim's algorithm

All Pairs