1. Graph 란?
- 비선형: 여러 방향으로 연결될 수 있음 (한 줄로 순서 있게 나열되는 선형 자료구조와 다름)
- 다대다: 한 노드가 여러 노드와 연결될 수 있음 (1:n or n:n)
- ✅ edge로 정점간의 관계를 표현합니다.
- ✅ 계층적 형식 or 네트워크 형식. (명확한 부모-자식 관계가 존재 X)
- ➡️ 현실세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다.
예시) 현실세계 모델링
더보기
| 정점 | 간선 | |
| SNS | 사람 | 친구 관계 |
| 도로망 | 도시 | 도로 |
| 인터넷 | 웹페이지 | 링크 |
| 추천 시스템 | 사용자 | 상품 관계 |
용어
| 용어 | 설명 |
| Vertex(정점) | 정점 |
| Edge(간선) | 정점과 정점을 연결하는 간선을 의미합니다. |
| Adjacent(인접) | 두 정점이 간선으로 연결되어 있을 경우, 두 정점은 "인접하다" 표현합니다. |
| Incident(부속) | 정점간의 연결을 담당하는 간선을 "부속되었다" 표현합니다. |
| Degree(차수) | 한 정점에 부속된 간선의 개수를 그 정점의 "차수"라 표현합니다. |
| Path(경로) | 출발지에서 목적지로 이어지는 일련의 간선들을 의미합니다. |
| Cycle(사이클) | 시작노드와 종료노드가 동일한 경로를 의미합니다. (경로 상의 노드는 중복 허용 X) |
| Loop(루프) | 자기 자신을 가리키는 간선입니다. |
예시
더보기
A----B----C
| |
| |
| |
D----E
|
F- 인접 : A와 B는 인접합니다.
- 부속 : 간선 DE는 D와 E에 부속되어 있습니다.
- 차수 : 노드 D의 차수는 3이다 (AD, DE, DF).
- 경로(A-E) : A-D-E 또는 A-B-E가 있습니다.
- 사이클 : A-D-E-B-A
- 루프 : 위 그래프에서는 루프가 없습니다.
2. 종류
| 분류 기준 | 종류 | 의미 | 예시 |
| 간선 방향 존재 여부 | 무방향 그래프 (Undirected Graph) |
간선에 방향이 없다.
|
A—B는 A↔B 모두 가능.
|
| 방향 그래프 (Directed Graph, DAG 포함) |
간선에 방향이 있다.
|
A→B는 A에서 B로만 이동 가능.
|
|
| 가중치 존재 여부 | 비가중 그래프 (Unweighted Graph) |
간선마다 가중치가 없음.
|
모든 이동 비용이 동일.
|
| 가중 그래프 (Weighted Graph) | 간선에 가중치가 존재함. | ||
| 사이클 존재 여부 | 비순환 그래프 (Acyclic Graph) |
그래프에 사이클이 없음.
|
|
| 순환 그래프 (Cyclic Graph) | 그래프에 사이클이 존재함. |
예시) 무방향 vs 방향
더보기
무방향 그래프
A-----B
| |
| |
C-----D- 양방향으로 연결이 가능합니다.
방향 그래프
A---->B
^ |
| v
C<----D- 특정 방향으로만 연결이 가능합니다.
예시) 비가중 vs 가중
더보기
비가중 그래프
A-----B
| |
| |
C-----D- 가중치가 없거나 필요하지 않은 경우에 사용됩니다.
가중 그래프
A--5--B
| |
3 2
| |
C--1--D- 간선에 가중치를 가지는 그래프입니다.
- 간선의 가중치는 다양한 것을 나타낼 수 있습니다. (비용, 거리 등)
예시) 비순환 vs 순환
더보기
비순환 그래프
A---->B---->C
|
v
D- 그래프 내에 어떠한 사이클도 포함되지 않는 그래프
순환 그래프
A---->B---->C
^ |
| v
D<----------E- 그래프 내에 하나 이상의 사이클이 존재하는 그래프
- 소셜 네트워크, 통신 네트워크
3. 표현
A-----B
| |
| |
D-----C| 구분 | 인접행렬 (Adjacency Matrix) | 인접리스트 (Adjacency List) |
간선리스트 (Edge List)
|
| 구조 | V×V 2차원 배열에 i→j 연결 여부(1/0) 저장 | 각 정점에 연결된 정점 목록을 리스트 형태로 저장 |
모든 간선을 (u, v) 쌍 형태로 리스트에 저장
|
| 메모리 | O(V²) | O(V + E) | O(E) |
| 장점 | - 간선 존재 여부 빠름(O(1)) - 밀집 그래프에서 효율적 - 구현 단순 |
- 인접 정점 순회가 빠름(O(deg(v))) - 메모리 효율적(희소 그래프) - 간선 추가 쉬움 |
- 메모리 효율적(희소 그래프) - 구현 단순 |
| 단점 | - 매우 큰 메모리 필요(V가 크면 비효율적) - 희소 그래프에서 낭비 큼 |
- 간선 존재 여부 확인 느림(O(deg(v))) - 간선 삭제 느림 - 무방향 그래프는 양쪽 리스트 삭제 필요 |
- 특정 정점의 인접 정점 찾기 느림(O(E))
|
| 적합한 경우 | 밀집 그래프(Dense) 정점 수 작은 문제 |
희소 그래프(Sparse) |
간선 기반 문제
|
| 예시 사용 알고리즘 | 플로이드-와샬, 전이폐쇄 | BFS, DFS, 다익스트라(힙), 위상정렬 |
크루스칼(MST)
Bellman-Ford 사이클 검출(DSU) |
코드) 인접행렬
더보기
A |
B | C | D | |
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
public class UDGWithMatrix {
private final int vCnt;
private BitSet[] adjacency;
UDGWithMatrix(int size) {
this.size = size;
for (int i = 0; i < size; i++) this.adjacency[i] = new BitSet(size);
}
public void addEdge(int src, int dest) {
adjacency[src].set(dest);
adjacency[dest].set(src);
}
public boolean hasEdge(int src, int dest) {
return adjacency[src].get(dest);
}
public void removeEdge(int src, int dest) {
adjacency[src].clear(dest);
adjacency[dest].clear(src);
}
public int[] getAdjVertices(int v) {
return IntStream.range(0, size).filter(i -> adjacency[v].get(i)).toArray();
}
public int getDegree(int v) {
return adjacency[v].cardinality();
}
}
코드) 인접리스트
더보기
public class UGWithLinkedList {
private final Scanner sc;
private final Node[] adjList;
private final Queue<Integer> queue;
private final BitSet visited;
public static void main(String[] args) {
UGWithLinkedList ugWithLinkedList = new UGWithLinkedList();
ugWithLinkedList.bfs(0);
}
public UGWithLinkedList() {
sc = new Scanner(System.in);
adjList = init();
queue = new ArrayDeque<>();
visited = new BitSet();
}
public boolean hasEdge(int src, int dest) {
for (Node cur = adjList[src]; cur != null; cur = cur.next) {
if (cur.val == dest) return true;
}
return false;
}
public void bfs(int start) {
queue.clear();
visited.clear();
queue.offer(start);
visited.set(start);
while (!queue.isEmpty()) {
int val = queue.poll();
System.out.println((char) (val + 65));
for (Node cur = adjList[val]; cur != null; cur = cur.next) {
if (visited.get(cur.val)) continue;
visited.set(cur.val);
queue.offer(cur.val);
}
}
}
private Node[] init() {
int vCnt = sc.nextInt();
int eCnt = sc.nextInt();
Node[] adjList = new Node[vCnt];
for (int i = 0; i < eCnt; i++) {
int src = sc.nextInt();
int dest = sc.nextInt();
adjList[src] = new Node(dest, adjList[src]);
adjList[dest] = new Node(src, adjList[dest]);
}
return adjList;
}
class Node {
final int val;
final Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
}
코드) 간선 리스트
더보기
public class UGWithEdges {
int vCnt;
List<Edge> edges;
public UGWithEdges(int vCnt) {
this.vCnt = vCnt;
edges = new ArrayList<>();
}
public void addEdge(int src, int dest) {
if (hasEdge(src, dest)) return;
edges.add(new Edge(src, dest));
}
public boolean hasEdge(int src, int dest) {
return edges.stream()
.anyMatch(e -> (e.src == src && e.dest == dest) || (e.src == dest && e.dest == src));
}
public List<Integer> getAdjVertices(int vertex) {
return edges.stream()
.filter(e -> e.isAdjVertex(vertex))
.map(e -> e.getAdjVertex(vertex))
.toList();
}
class Edge {
final int src, dest;
public Edge(int src, int dest) {
this.src = src;
this.dest = dest;
}
public boolean isAdjVertex(int vertex) {
return src == vertex || dest == vertex;
}
public int getAdjVertex(int vertex) {
return src == vertex ? dest : src;
}
}
}
출처
'Data Structure' 카테고리의 다른 글
| [고급 자료구조] Tree: Heap (0) | 2023.10.26 |
|---|---|
| [고급 자료구조] Tree: Trie (0) | 2023.10.26 |
| [자료구조] Tree (0) | 2023.10.26 |
| [기초 자료구조] HashTable (1) | 2023.10.26 |
| [기초 자료구조] Stack (0) | 2023.10.26 |