무향 그래프 - 방향 없는 그래프
유향 그래프
가중치 그래프
사이클 없는 방향 그래프
완전그래프 - 정점들에 대해 가능한 모든 간선들을 가진 그래프
부분 그래프 - 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
인접(Adjacency)
간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정
인접행렬
|V| x |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장
배열의 배열
무향 그래프
유향 그래프
- 행 i의 합 = Vi의 진출 차수
- 열 i의 합 = Vi의 진입 차수
V, E = map(int, input().split())
edge = list(map(int, input().split())
adj = [[0]*(V+1) for _ in range(V+1)]
for i in range(E):
n1 = edge[i*2]
n2 = edge[i*2+1]
adj[n1][n2] = 1
adj[n2][n1] = 1 # 무향 그래프인 경우 대칭
인접 리스트
각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
각 정점에 대한 인접 정점들을 순차적으로 표현
하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
V, E = map(int, input().split())
edge = list(map(int, input().split())
adj_list = [[]*(V+1) for _ in range(V+1)]
for i in range(E):
n1 = edge[i*2]
n2 = edge[i*2+1]
adj[n1].append(n2)
adj[n2].append(n1) # 무향 그래프인 경우 대칭
간선의 배열
시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법
가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용
stack사용한 코드
STACK s
visited[]
DFS(v)
push( s, v )
WHILE NOT isEmpty( s )
v <- poop(s)
IF NOT visited[v]
visited ( v )
FOR each w in adjacency( v )
IF NOT visited[w]
push(s, w)
재귀를 사용한 코드
DFS_Recursive(G, v)
visited[ v ] <- TRUE // v 방문 설정
FOR each all w in adjacency( G, V )
IF visited[w] is not TRUE
DFS_Recursive(G, w)
탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
BFS(G, v)
큐 생성
시작점에 v를 큐에 삽입
점 v를 방문한 것으로 표시
WHILE 큐가 비어있지 않은 경우
t <- 큐의 첫번째 원소 반환
FOR t와 연결된 모든 선에 대해
u <- t의 이웃점
u가 방문되지 않은 곳이면,
u를 큐에 넣고, 방문한 것으로 표시