무방향 그래프(Undirected Graph)

무방향 그래프(Undirected Graph) 는 각 간선(Edge)에 방향성이 없는 그래프이다.
즉, 정점 A와 정점 B가 간선으로 연결되어 있으면, A에서 B로 가는 것과 B에서 A로 가는 것이 동일하다.

무방향 그래프 특징

간선이 양방향(↔)으로 연결됨
정점 간 이동에 방향성이 없음
정점의 차수(Degree)는 해당 정점과 연결된 간선의 개수
DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 알고리즘이 적용 가능
연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph) 개념 적용 가능

무방향 그래프의 표현 방법

1
2
3
  A — B
  |   |
  C — D

A - B (A와 B는 서로 연결됨)
A - C (A와 C는 서로 연결됨)
B - D (B와 D는 서로 연결됨)
C - D (C와 D는 서로 연결됨)

무방향 그래프의 인접 행렬(Adjacency Matrix) 표현

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

설명

A - B, A - C, B - D, C - D가 존재하므로 1로 표시됨
무방향 그래프는 대칭 행렬(Symmetric Matrix)의 형태를 가짐

무방향 그래프의 인접 리스트(Adjacency List) 표현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# 그래프 출력
for node in graph:
    print(node, ":", graph[node])

출력 결과

1
2
3
4
A : ['B', 'C']
B : ['A', 'D']
C : ['A', 'D']
D : ['B', 'C']

설명

각 정점이 연결된 다른 정점들을 리스트 형태로 저장
A와 B가 연결되었으면, A 리스트에도 B가 포함되고, B 리스트에도 A가 포함됨

무방향 그래프의 특성

정점의 차수(Degree)
- 무방향 그래프에서 차수(Degree) 는 해당 정점과 연결된 간선의 개수
- 위 예제에서:
  - A의 차수: 2 (B, C와 연결)
  - B의 차수: 2 (A, D와 연결)
  - C의 차수: 2 (A, D와 연결)
  - D의 차수: 2 (B, C와 연결)
연결 그래프(Connected Graph)
- 모든 정점이 서로 연결되어 있는 경우 → 연결 그래프
- 위 그래프는 연결 그래프 (모든 정점 간 최소 한 개의 경로 존재)
비연결 그래프(Disconnected Graph)
- 일부 정점이 연결되지 않은 경우 → 비연결 그래프
예제:
1 2 3
A — B E — F | C — D
여기서 E, F는 A, B, C, D와 연결되지 않아 비연결 그래프

무방향 그래프의 종류

단순 무방향 그래프(Simple Undirected Graph)
- 자기 루프(self-loop)가 없고 정점 쌍 사이에 최대 하나의 간선만 존재하는 그래프
다중 무방향 그래프(Multigraph)
- 두 정점 사이에 여러 개의 간선이 허용되는 그래프
완전 그래프(Complete Graph)
- 모든 정점 쌍이 간선으로 연결된 그래프
- n개의 정점을 가진 완전 그래프는 n(n-1)/2개의 간선을 가지며, K_n으로 표기
정규 그래프(Regular Graph)
- 모든 정점의 차수가 동일한 그래프
- k-정규 그래프는 모든 정점의 차수가 k인 그래프
이분 그래프(Bipartite Graph)
- 정점 집합을 두 그룹으로 나눌 수 있어, 같은 그룹 내 정점 간에는 간선이 없는 그래프
가중치 그래프(Weighted Graph)
- 각 간선에 가중치(비용, 거리, 시간 등)가 할당된 그래프

무방향 그래프의 구현

무방향 그래프 생성 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class UndirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)  # 양방향 연결

    def display(self):
        for node in self.graph:
            print(node, ":", self.graph[node])

# 그래프 생성
g = UndirectedGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')

# 그래프 출력
g.display()

출력 결과

1
2
3
4
A : ['B', 'C']
B : ['A', 'D']
C : ['A', 'D']
D : ['B', 'C']

무방향 그래프의 탐색 알고리즘

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

한 경로를 끝까지 탐색 후 백트래킹
스택(Stack) 또는 재귀(Recursion) 사용

1
2
3
4
5
6
7
8
9
def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=" ")
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
dfs(graph, 'A', set())  # A B D C

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

가까운 노드부터 탐색 (큐 사용)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set()

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(graph[node])

graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
bfs(graph, 'A')  # A B C D

무방향 그래프의 활용

네트워크 연결
- 컴퓨터 네트워크에서 노드 간 연결을 표현
도로 지도 & 네비게이션
- 도시 간 도로는 양방향으로 연결되는 경우가 많음
소셜 네트워크 분석 (Facebook, LinkedIn)
- 친구 관계(양방향)
통신 시스템
- 전화망, 인터넷 네트워크 등
전자 회로 설계
- 노드(컴포넌트) 간 연결 분석

무방향 그래프(Undirected Graph)#

무방향 그래프 특징#

무방향 그래프의 표현 방법#

무방향 그래프의 인접 행렬(Adjacency Matrix) 표현#

무방향 그래프의 인접 리스트(Adjacency List) 표현#

무방향 그래프의 특성#

무방향 그래프의 종류#

무방향 그래프의 구현#

무방향 그래프의 탐색 알고리즘#

무방향 그래프의 활용#

참고 및 출처#