그래프 ( Graph )

그래프 ( Graph )

그래프는 정점 ( Vertex , Node ) 과 간선 ( Edge ) 으로 이러우진 자료구조이다.

객체 간의 관계를 표현하는데 사용한다.

정점은 개체를 나타내고 , 간선은 두 정점 간의 연결 관계를 의미한다.

 

 

▼정점 ( Vertex , Node )

정의 : 그래프에서 표현하는 대상 ( 객체 , 데이터 , 위치 등 )

예시 : 

• 소셜 네트워크 - 사람 한명
• 지도 - 도시 , 역
• 웹 - 웹 페이지

표현 방식 : 일반적으로 원 ( circle ) 으로 표시하고, 고유한 번호 ( ID ) 나 이름 ( Label ) 을 붙인다.

쉽게 말하면, "점" 자체를 나타낸다.

 

 

▼간선 ( Edge )

정의 : 두 정점을 연결하는 선 ( 관계나 경로 )

종류 :

• 무방향 간선 ( Undirected Edge ) : 양방향 관계 ( A 와 B 가 서로 연결됨 )
• 방향 간선 ( Directed Edge ) : 한쪽 방향만 가능 ( A 에서 B 로 가는 관계 )
• 가중치 간선 ( Weighted Edge ) : 비용이나 거리 같은 값이 붙은 간선 ( 지하철 거리 , 도로 시간 )

쉽게 말하면, "점과 점을 이어주는 선" 이다.

 

 

문법

▼인접 리스트 방식

Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();

 

 

▼정점 추가

graph[1] = new List<int> { 2, 3 };
graph[2] = new List<int> { 1, 4 };
graph[3] = new List<int> { 1 };
graph[4] = new List<int> { 2 };

 

 

 

예시 코드

▼DFS ( 깊이 우선 탐색 )

void DFS(int start, Dictionary<int, List<int>> graph, HashSet<int> visited)
{
    if (visited.Contains(start)) return;

    Console.WriteLine(start);
    visited.Add(start);

    foreach (var neighbor in graph[start])
    {
        DFS(neighbor, graph, visited);
    }
}

 

▼실행

var visited = new HashSet<int>();
DFS(1, graph, visited);

 

 

 

주의할 점

순환 ( Cycle ) 여부 : 그래프틑 순환이 존재할 수 있으므로 방문 여부 체크는 필수이다.

방향성 : 방향 그래프 ( Directed Graph ) 인지 무방향 그래프 ( Undirected Graph ) 인지 구분이 필요하다.

가중치 ( Weight ) : 간선에 비용이 붙을 수 있다. - 알고리즘 ( 다익스트라 , 크루스칼 등 ) 에서 중요하다.

저장 방식 : 인접 리스트 ( 메모리 효율적 ) vs 인접 행결 ( 연산 단순하지만 메모리 소모 큼 ) 선택 필요

 

 

정리

그래프는 정점과 간선으로 이루어진 비선형 자료구조로 개체 간의 복잡한 관계를 표현할 수 있다.