[Data Structure] 그래프

그래프란

그래프(Graph): 정점(Vertex, 노드)과 간선(Edge)으로 이루어진 자료구조.
정점들 사이의 관계(연결 여부, 방향, 거리 등)를 표현하는 데 사용된다.

velog Sue_

그래프 용어

정점(Vertex): 그래프를 구성하는 기본 단위. 노드라고 부르기도 한다.

간선(Edge): 두 정점을 연결하는 선. 관계/연결을 표현한다.

인접(Adjacent): 두 정점이 간선으로 직접 연결되어 있을 때 두 정점이 인접한다고 한다.

차수(Degree): 정점에 연결된 간선의 수.
무방향 그래프에서는 한 정점에 붙어 있는 간선 개수.
방향 그래프에서는 진입 차수(in-degree), 진출 차수(out-degree)를 나누어 말하기도 한다.

경로(Path): 한 정점에서 다른 정점으로 이동할 때 거치는 정점들의 순서.

단순 경로(Simple Path): 정점을 중복해서 지나지 않는 경로.

사이클(Cycle): 시작 정점과 끝 정점이 같고, 중간에 정점이 중복되지 않는 닫힌 경로.

연결 그래프(Connected Graph): 무향 그래프에서 모든 정점 쌍 사이에 경로가 존재하는 그래프.

가중치(Weight): 간선에 부여된 비용, 거리, 시간, 용량 같은 값. 가중 그래프에서 사용.

그래프의 종류

무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프. (u, v)와 (v, u)가 같은 간선.

1 ---- 2 ---- 3 ---- 4

방향 그래프(Directed Graph, Digraph): 간선에 방향이 있는 그래프. (u → v)와 (v → u)는 다른 간선.

1 → 2 → 3 → 4

가중 그래프(Weighted Graph): 간선에 가중치(거리, 비용 등)가 있는 그래프.

1 --(3)-- 2 --(5)-- 3 --(2)-- 4

사이클 그래프(Cycle Graph): 모든 정점이 하나의 사이클을 이루는 그래프.

1 —— 2
|    |
4 —— 3

 

그래프의 표현 방식

인접 행렬(Adjacency Matrix)
정점 개수가 n일 때 n × n 크기의 2차원 배열을 사용하는 방식.
행 i, 열 j 의 값이 1(또는 가중치)이면 i번 정점에서 j번 정점으로 간선이 존재함을 의미하고, 0이면 간선이 없음을 의미한다.

장점:

• 구현이 간단하고, 두 정점 사이에 간선이 있는지 확인하는 연산이 O(1)이다.
• 행렬 형태라서 행렬 연산, DP 등과 함께 쓰기 좋다.

인접 리스트(Adjacency List)
각 정점마다 연결된 이웃 정점들의 리스트를 따로 관리하는 방식.
예: vector<int> adj[정점수]; 처럼 “정점 → 연결된 정점들” 구조로 표현.

장점:

• 필요한 간선 정보만 저장해서 메모리를 O(V + E) 정도만 사용한다.
• 정점 수가 많고 간선이 적은 그래프(희소 그래프)에 적합하다.

간선 리스트(Edge List)
간선만 (u, v) 쌍으로 저장하는 방식.

그래프 탐색 기법

그래프 탐색은 “정점들을 어떤 순서로 방문할 것인가”에 대한 알고리즘이다.
대표적인 방법은 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다.

 

DFS(Depth-First Search, 깊이 우선 탐색)
한 정점에서 시작해서 한 방향으로 갈 수 있을 때까지 최대한 깊게 내려간 뒤, 더 이상 갈 수 없으면 한 단계 위로 돌아가서 다른 방향으로 탐색하는 방식.
재귀 호출이나 스택(Stack)을 사용해서 구현한다.
모든 정점을 방문하는 데 O(V + E) 시간이 걸린다.
연결 여부 확인, 사이클 존재 여부 검사, 위상 정렬, 백트래킹 등에서 많이 사용된다.

 

BFS(Breadth-First Search, 너비 우선 탐색)
시작 정점에서 가까운 정점부터, 즉 레벨 순서대로 탐색하는 방식.
큐(Queue)를 사용해서 구현한다.
무가중 그래프에서 “간선 수 기준 최단 거리”를 구할 때 사용한다.
마찬가지로 전체 탐색 시간은 O(V + E)이다.

행렬 그래프의 구현

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10

int adj[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertexCount;

void initGraph(int n) {
    int i, j;
    vertexCount = n;
    for (i = 0; i < vertexCount; i++) {
        for (j = 0; j < vertexCount; j++) {
            adj[i][j] = 0;
        }
        visited[i] = 0;
    }
}

void resetVisited() {
    int i;
    for (i = 0; i < vertexCount; i++) {
        visited[i] = 0;
    }
}

void addEdge(int u, int v) {
    if (u < 0 || v < 0 || u >= vertexCount || v >= vertexCount) return;
    adj[u][v] = 1;
    adj[v][u] = 1;
}

void printAdjMatrix() {
    int i, j;
    printf("Adjacency Matrix:\n");
    for (i = 0; i < vertexCount; i++) {
        for (j = 0; j < vertexCount; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}

void dfs(int v) {
    int i;
    visited[v] = 1;
    printf("%d ", v);
    for (i = 0; i < vertexCount; i++) {
        if (adj[v][i] && !visited[i]) {
            dfs(i);
        }
    }
}

typedef struct {
    int data[MAX_VERTICES];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, int x) {
    if (q->rear >= MAX_VERTICES) exit(1);
    q->data[q->rear++] = x;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) exit(1);
    return q->data[q->front++];
}

void bfs(int start) {
    Queue q;
    int v, i;

    initQueue(&q);
    visited[start] = 1;
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        v = dequeue(&q);
        printf("%d ", v);
        for (i = 0; i < vertexCount; i++) {
            if (adj[v][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

int main(void) {
    initGraph(5);

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);

    printAdjMatrix();

    resetVisited();
    printf("DFS: ");
    dfs(0);
    printf("\n");

    resetVisited();
    printf("BFS: ");
    bfs(0);
    printf("\n");

    return 0;
}

      0
     / \
    1   2
   / \
  3   4

 

 

출처: 교과서, C로 배우는 쉬운 자료구조, ChatGPT