탐색 - 6. 그래프 탐색 개요 (Graph Search)

📌 6. 그래프 탐색 개요 (Graph Search)

---

6.1 그래프(Graph)란?

🔹 그래프의 개념

그래프(Graph)는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료구조로, 다양한 연결 관계를 표현하는 데 사용됩니다.

💡 그래프의 활용 예시

• 소셜 네트워크 → 친구 관계(정점: 사람, 간선: 친구 관계)
• 지도와 길 찾기 → 도시 간 최단 경로(정점: 도시, 간선: 도로)
• 웹 크롤링 → 웹페이지 간의 연결(정점: 웹페이지, 간선: 하이퍼링크)
• 컴퓨터 네트워크 → 라우터 간 연결 구조

---

🔹 그래프의 구성 요소

1. 정점(Vertex, Node): 데이터를 저장하는 요소
2. 간선(Edge): 정점 간의 연결 관계
3. 가중치(Weight, 선택적): 간선에 부여된 값 (예: 도로 거리, 비용)
4. 방향성(Directionality)
   • 무방향 그래프 (Undirected Graph): 양방향 이동 가능
   • 방향 그래프 (Directed Graph, DAG): 한쪽 방향으로만 이동 가능

---

6.2 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 소개

🔹 1) 인접 행렬 (Adjacency Matrix)

• 2차원 배열을 사용하여 그래프를 표현하는 방법
• matrix[i][j] = 1 → i번 정점에서 j번 정점으로 이동 가능
• 공간 복잡도: O(V²) (V는 정점의 개수)
• 빠른 연결 확인: O(1) (임의의 두 정점이 연결되었는지 확인 가능)
• 메모리 낭비 가능: 간선이 적은 경우(희소 그래프) 불필요한 0이 많음

✔ 적합한 경우: 그래프가 빽빽하게 연결된 경우(완전 그래프)

---

🔹 2) 인접 리스트 (Adjacency List)

• 연결 리스트(Linked List)를 사용하여 그래프를 표현하는 방법
• list[i]는 i번 정점과 연결된 정점들의 리스트를 저장
• 공간 복잡도: O(V + E) (E는 간선의 개수)
• 빠른 간선 추가: 새로운 간선 추가 시 O(1) 가능
• 느린 연결 확인: 특정 간선이 존재하는지 확인하려면 O(V) 필요

✔ 적합한 경우: 간선이 적은 경우(희소 그래프)

---

6.3 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)의 차이점

탐색 방식	동작 방식	사용 자료구조	시간 복잡도	특징
DFS (Depth First Search)	한 방향으로 끝까지 탐색 후 되돌아감 (백트래킹)	스택(Stack) / 재귀(Recursive)	O(V + E)	미로 찾기, 백트래킹
BFS (Breadth First Search)	가까운 정점부터 차례대로 탐색	큐(Queue)	O(V + E)	최단 경로 탐색

💡 언제 DFS/BFS를 사용해야 할까?

• DFS → 모든 경로 탐색이 필요할 때 (예: 미로 탐색, 백트래킹)
• BFS → 최단 경로 탐색이 필요할 때 (예: 길 찾기, 네트워크 거리 계산)

---

🔍 실습: 인접 행렬과 인접 리스트를 사용하여 그래프 구현

1️⃣ 인접 행렬 (Adjacency Matrix) 구현

#include <stdio.h>

#define V 5 // 정점 개수

// 그래프 출력 함수
void printGraph(int graph[V][V]) {
    printf("인접 행렬 그래프 표현:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    // 5개의 정점을 가진 그래프 초기화
    int graph[V][V] = { {0, 1, 1, 0, 0},
                         {1, 0, 0, 1, 0},
                         {1, 0, 0, 1, 1},
                         {0, 1, 1, 0, 1},
                         {0, 0, 1, 1, 0} };

    printGraph(graph);
    return 0;
}

📌 실행 결과

인접 행렬 그래프 표현:
0 1 1 0 0 
1 0 0 1 0 
1 0 0 1 1 
0 1 1 0 1 
0 0 1 1 0 

---

2️⃣ 인접 리스트 (Adjacency List) 구현

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

#define V 5 // 정점 개수

// 연결 리스트 노드 구조체
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 그래프 구조체
typedef struct {
    Node* head[V]; // 정점별 인접 리스트
} Graph;

// 그래프 초기화
Graph* createGraph() {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    for (int i = 0; i < V; i++) {
        graph->head[i] = NULL;
    }
    return graph;
}

// 간선 추가 (양방향 그래프)
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->head[src];
    graph->head[src] = newNode;

    // 반대 방향도 추가 (무방향 그래프)
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->head[dest];
    graph->head[dest] = newNode;
}

// 그래프 출력
void printGraph(Graph* graph) {
    for (int i = 0; i < V; i++) {
        printf("정점 %d: ", i);
        Node* temp = graph->head[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

// 메모리 해제
void freeGraph(Graph* graph) {
    for (int i = 0; i < V; i++) {
        Node* temp = graph->head[i];
        while (temp) {
            Node* prev = temp;
            temp = temp->next;
            free(prev);
        }
    }
    free(graph);
}

int main() {
    Graph* graph = createGraph();

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

    printGraph(graph);
    freeGraph(graph);

    return 0;
}

📌 실행 결과

정점 0: 2 -> 1 -> NULL
정점 1: 3 -> 0 -> NULL
정점 2: 4 -> 3 -> 0 -> NULL
정점 3: 4 -> 2 -> 1 -> NULL
정점 4: 3 -> 2 -> NULL

---

📌 마무리 및 정리

• 그래프(Graph): 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
• 그래프 표현 방식
  • 인접 행렬 → 빠른 연결 확인, O(V²) 공간 복잡도
  • 인접 리스트 → 적은 메모리 사용, O(V + E) 공간 복잡도
• DFS vs BFS
  • DFS: 백트래킹, 미로 찾기, 깊이 있는 탐색
  • BFS: 최단 경로 탐색, 네트워크 분석