Graph

• 그래프는 객체 간의 관계를 정점(Vertex)과 간선(Edge)으로 나타내는 자료구조입니다. 지금까지 살펴본 자료구조 중에서 가장 강력한 표현 능력을 지니며, 현실 세계의 다양한 문제를 효과적으로 모델링하기에 적합합니다.
• 일반적으로 그래프 자료구조를 설명하기 위해서 지하철 노선도를 생각하면 쉽습니다. 각 역이 정점(Vertex)가 되고 각 역 사이에 노선이 간선(Edge)라고 생각하면 됩니다.
• 여기에는 트리 구조에서 볼 수 있는 명확한 '부모-자식'의 관계는 존재하지 않습니다. 한 역이 다른 역보다 상위나 하위의 관계로 정의되지 않으며, 모든 역은 그 자체로 독립적인 존재로, 다른 역들과의 연결성을 통해 그래프 내에서 실제 지하철 공간을 표현할 수 있습니다.
• 요약하면, 그래프는 정점(Vertex)와 간선(Edge)의 집합입니다.

• Graph를 활용해서 표현할 수 있는 또 다른 것들
  • 소셜 네트워크: 사용자들을 노드로, 서로의 친구 관계나 팔로잉 관계를 간선으로 볼 수 있습니다. 여기서는 간선의 방향이 중요하게 될 수 있습니다. 예를 들어, A가 B를 팔로우하는 것과 B가 A를 팔로우하는 것은 다를 수 있습니다.
  • 도시와 도로 네트워크: 각 도시를 정점으로 생각하고, 도시들을 연결하는 도로를 간선으로 생각할 수 있습니다. 이때, 도로의 길이나 소요 시간을 간선의 가중치 표현할 수도 있습니다.
  • 인터넷: 각각의 웹페이지를 정점으로, 웹페이지들 사이의 링크를 간선으로 생각할 수 있습니다.

---

그래프 용어

• 인접 (Adjacent)
  • 두 노드(정점) 사이에 간선이 존재할 경우, 두 노드는 서로 '인접'되어 있다고 말합니다.
  • 그래프에서, 노드 0과 노드 1은 간선 (0, 1)에 의해 연결되므로 노드 0과 노드 1은 서로 인접해 있습니다.
• 부속 (Incidnet)
  • 두 노드를 연결하는 간선은 해당 두 노드에 '부속'되어 있다고 합니다.
  • 그래프에서, 간선 (0, 1)은 노드 0과 노드 1에 부속되어 있습니다.
• 차수 (Degree)
  • 한 노드에 부속된 간선의 개수를 그 노드의 '차수'라고 합니다.
  • 무방향 그래프에서, 노드의 차수는 그 노드에 연결된 간선의 개수와 같습니다.
  • 방향 그래프에서는 노드로 들어오는 간선의 개수를 '진입차수 (In-degree)', 노드에서 나가는 간선의 개수를 '진출차수 (Out-degree)'라고 부릅니다.
• 경로 (Path)
  • 정점 A (출발지)에서 정점 B (목적지)로 이어지는 일련의 간선들을 의미합니다.
  • 경로를 구성하는 간선의 개수를 '경로 길이 (Path Length)'라고 합니다.
  • '단순 경로 (Simple Path)'는 동일한 노드를 중복해서 포함하지 않는 경로를 의미합니다.
  • '사이클 (Cycle)'은 그래프 내에서 시작 노드와 종료 노드가 동일한 단순 경로를 의미합니다. 사이클은 최소한 3개 이상의 노드로 구성됩니다. (루프는 제외하기 때문) 예를 들어서 경로 A→B→C→A는 노드 A에서 시작해서 다시 노드 A로 돌아오므로 사이클입니다.
    
• 루프 (Loop)
  • 루프는 그래프 내의 특정 노드에서 시작해서 동일한 노드로 끝나는 간선을 의미합니다. 즉, 단일 노드를 연결하는 간선입니다.

Graph 종류

---

일반적으로 간선의 특성에 따라서 그래프의 종류가 구분됩니다.

무방향 그래프 & 방향 그래프

무방향 그래프 (Undirected Graph)

• 간선에 방향이 없는 그래프입니다.
• 두 노드 A와 B 사이에 간선이 있다면, A에서 B로의 연결과 B에서 A로의 연결 모두 가능합니다.

방향 그래프 (Directed Graph)

• 간선에 방향이 있는 그래프입니다.
• 두 노드 A와 B 사이에 방향성을 갖는 간선이 있으면, 해당 방향으로만 연결이 가능합니다. 예를 들어, A에서 B로의 방향성을 갖는 간선이 있다면 B에서 A로는 연결되어 있지 않습니다.

비가중 그래프 & 가중 그래프

비가중 그래프 (Unweighted Graph)

• 모든 간선이 동일한 값을 가진 그래프입니다. 보통 간선의 가중치에 대한 정보가 없거나 필요하지 않은 경우 사용됩니다.

가중 그래프 (Weighted Graph)

• 간선이 가중치(Weight)를 갖는 그래프입니다.

• 이 값은 간선 사이의 "비용", "길이", "거리" 등 다양한 것을 나타낼 수 있습니다.

• 무방향 가중 그래프 (Undirected Weighted Graph) = 무방향 그래프 + 가중치

• 방향 가중 그래프 (Directed Weighted Graph) = 방향 그래프 + 가중치

• 일반적으로 방향 가중 그래프를 네트워크(Network)라고 부른다.

• 가중 그래프는 노드 사이의 연결 관계에 추가로 비용 혹은 거리 등의 추가 속성을 정의할 수 있어 응용 분야가 포괄적인 그래프 모델이라 할 수 있습니다.

비순환 그래프 & 순환 그래프

비순환 그래프(Acyclic Graph)

• 비순환 그래프는 이름에서도 알 수 있듯이, 그래프 내에 어떠한 사이클(cycle)도 포함되어 있지 않은 그래프를 말합니다.
• 트리(Tree)는 가장 대표적인 비순환 그래프입니다. 트리는 연결된 그래프에서 사이클이 없는 구조로, 모든 노드 사이에는 정확히 하나의 경로만 존재합니다.
• 의존성 구조, 계층 구조 등에서 비순환 그래프는 자주 사용됩니다. 예를 들면, 프로젝트 작업 순서나 일정 계획에서 순환 구조는 피해야 하므로 비순환 그래프가 적합합니다.

순환 그래프(Cyclic Graph)

• 순환 그래프는 그래프 내에 하나 이상의 사이클(cycle)이 존재하는 그래프를 말합니다. 사이클은 시작 노드와 끝 노드가 같은 단순 경로(Simple Path)로, 동일한 노드를 두 번 이상 방문하지 않는 경로입니다.
• 예) 소셜 네트워크에서 친구 관계를 그래프로 나타낼 때, A와 B가 친구이고, B와 C가 친구이며, 다시 C와 A가 친구라면 A-B-C-A로 사이클이 형성됩니다.
• 예) 통신 네트워크는 여러 노드(기기나 중계소) 사이의 연결 구조를 갖습니다. 이러한 네트워크에서는 데이터가 여러 경로를 통해 전송될 수 있어야 합니다. 만약 어떤 노드나 연결이 실패할 경우, 다른 경로를 통해 데이터가 전송될 수 있어야 합니다. 이러한 이유로 통신 네트워크에는 여러 가능한 경로와 그 중 일부는 사이클을 형성할 수 있습니다.

기타 그래프

연결 그래프 (Connected Graph)

무방향 그래프에서 임의의 두 노드 사이에 경로가 항상 존재하는 그래프입니다.

비연결 그래프 (Disconnected Graph)

무방향 그래프에서 임의의 두 노드 사이에 경로가 존재하지 않을 수 있는 그래프입니다.

완전 그래프 (Complete Graph)

그래프 내의 모든 노드가 1:1 간선으로 연결된 경우, 즉 연결 가능한 최대 간선 수를 가진 그래프

부분 그래프(Sub Graph)

원래의 그래프에서 일부의 노드나 일부의 간선을 제외하여 만든 그래프를 부분 그래프라고 한다.

다중 그래프(Multi Graph)

두 노드 사이에 여러 개의 간선이 있을 수 있는 그래프입니다.

Graph의 표현

---

정점과 간선을 가진 그래프를 컴퓨터가 이해할 수 있는 형태로 표현해야 합니다. 그래프를 컴퓨터가 이해할 수 있도록 표현하는 대표적인 방법에는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)이 있습니다.

인접 행렬(Adjacency Matrix)

• 인접 행렬은 그래프의 정점들들 간의 연결 관계를 2차원 배열 (v x v)로 표현하는 방식입니다.
  여기서, v는 정점의 수를 의미합니다.
• 각 행렬의 원소 adjacencyMatrix[i][j]는 정점 i와 정점 j가 연결되어 있으면 1, 그렇지 않으면 0으로 표시합니다.
• 인접 행렬(Adjacency Matrix) 표현 방법은 구현하기 쉽고, 두 정점 간의 연결 여부를 직관적으로 확인할 수 있습니다.
• 단, 정점(Vertex)은 많지만 간선(Edge)가 적은 희소 그래프의 경우 비효율적일 수 있습니다.
  

예시

도시들이 있는데 그 사이에 길이 거의 없다고 생각하면 됩니다. 각 도시를 만드는 데는 많은 공간이 필요하지만, 도시 사이에는 길이 거의 없기 때문에 여행하기도 어렵고, 도시를 만드는 데 사용한 공간이 아까울 수 있습니다. 마찬가지로, 그래프에서 노드(도시)는 많지만 간선(길)이 적으면, 많은 메모리를 사용하지만 그만큼 효율적으로 사용되지 않습니다.

4-2. 인접 리스트(Adjacency List)

• 인접 리스트는 각 정점(vertex)이 인접하고 있는 정점을 연결 리스트(Linked List)로 표현하는 방식입니다.
• 인접 행렬에서는 간선(edge) 저장을 통해 그래프를 표현했다면, 인접 리스트는 각 정점마다 해당 정점과 연결된 정점들의 리스트를 가집니다.
• 연결 리스트를 이용하여 노드별 인접 노드를 저장하는 방식은 메모리를 절약할 수 있습니다.
  • 도시와 도로를 생각해보세요. 만약 모든 도시 사이에 도로가 있다면, 그 정보를 전부 기록해야 합니다. 그런데 실제로는 모든 도시 사이에 도로가 있는 것이 아닙니다. 인접 리스트는 실제 연결된 도로만 기록하기 때문에 필요한 정보만 저장하게 됩니다.
  • 많은 도시에 비해 적은 도로만 있는 경우 (희소 그래프)에 더 좋습니다.
• 연결이 많아지면 효과가 떨어질 수 있습니다.

예시

도시는 많지만, 도로는 몇 개 없다면? 그런 정보를 모두 기록하는 것은 공간 낭비입니다. 인접 리스트는 실제 연결된 도로만 기록하기 때문에 이런 경우에는 훨씬 효율적으로 정보를 저장할 수 있습니다.

만약 도시와 도로가 거의 비슷한 수로 많다면, 인접 리스트는 오히려 더 많은 정보를 저장해야 할 수도 있습니다.
각 도시에 연결된 도로 정보뿐만 아니라 그 도로를 통해 어디로 갈 수 있는지도 저장해야 하기 때문입니다.
따라서 이런 경우에는 인접 리스트가 메모리를 더 많이 사용할 수도 있습니다.

구현 코드

무방향 그래프를 인접 행렬로

class UndirectedGraphAdjacencyMatrix:
    def __init__(self, vertices):
        # 그래프 클래스를 초기화하는 생성자 함수
        self.vertices = vertices  # 그래프의 정점 수
        self.adjacency_matrix = [[0] * vertices for _ in range(vertices)]
        # 인접 행렬을 초기화하고, 모든 원소를 0으로 설정

    def add_edge(self, u, v):
        # 두 정점 u와 v 사이에 간선을 추가하는 함수
        self.adjacency_matrix[u][v] = 1  # 정점 u와 v 사이의 연결을 나타내는 값을 1로 설정
        self.adjacency_matrix[v][u] = 1  # 무방향 그래프이므로 반대 방향도 설정

    def __str__(self):
        # 그래프를 문자열로 표현하기 위한 함수
        return '\n'.join([' '.join(map(str, row)) for row in self.adjacency_matrix])
        # 인접 행렬을 문자열로 변환하여 반환

# 그래프 생성
vertices = 4
graph = UndirectedGraphAdjacencyMatrix(vertices)
# 4개의 정점을 가지는 무방향 그래프 생성

graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
# 간선을 추가하여 그래프를 구성

# 그래프 출력
print("무방향 그래프 인접 행렬:")
print(graph)
# 무방향 그래프를 인접 행렬로 표현한 결과를 출력

출력 결과

무방향 그래프 인접 행렬:
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

무방향 그래프를 인접리스트로

class UndirectedGraphAdjacencyList:
    def __init__(self, vertices):
        # 그래프 클래스를 초기화하는 생성자 함수
        self.vertices = vertices  # 그래프의 정점 수
        self.adjacency_list = [[] for _ in range(vertices)]
        # 인접 리스트를 초기화하고, 빈 리스트로 각 정점에 대한 연결 정보를 저장

    def add_edge(self, u, v):
        # 두 정점 u와 v 사이에 간선을 추가하는 함수
        self.adjacency_list[u].append(v)  # 정점 u의 연결 리스트에 정점 v를 추가
        self.adjacency_list[v].append(u)  # 무방향 그래프이므로 정점 v의 연결 리스트에 정점 u를 추가

    def __str__(self):
        # 그래프를 문자열로 표현하기 위한 함수
        result = ""
        for vertex, neighbors in enumerate(self.adjacency_list):
            result += f"{vertex}: "
            result += " ".join(map(str, neighbors))
            result += "\n"
        return result
        # 각 정점과 해당 정점에 인접한 정점들을 문자열로 변환하여 반환

# 그래프 생성
vertices = 4
graph = UndirectedGraphAdjacencyList(vertices)
# 4개의 정점을 가지는 무방향 그래프 생성

graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
# 간선을 추가하여 그래프를 구성

# 그래프 출력
print("무방향 그래프 인접 리스트:")
print(graph)
# 무방향 그래프를 인접 리스트로 표현한 결과를 출력

출력 결과

무방향 그래프 인접 리스트:
0: 1 2
1: 0 2
2: 0 1 3
3: 2

방향 그래프를 인접 리스트로

class DirectedGraphAdjacencyList:
    def __init__(self, vertices):
        # 그래프 클래스를 초기화하는 생성자 함수
        self.vertices = vertices  # 그래프의 정점 수
        self.adjacency_list = [[] for _ in range(vertices)]
        # 인접 리스트를 초기화하고, 빈 리스트로 각 정점에 대한 연결 정보를 저장

    def add_edge(self, u, v):
        # 정점 u에서 v로의 방향 간선을 추가하는 함수
        self.adjacency_list[u].append(v)  # 정점 u의 연결 리스트에 정점 v를 추가

    def __str__(self):
        # 그래프를 문자열로 표현하기 위한 함수
        result = ""
        for vertex, neighbors in enumerate(self.adjacency_list):
            result += f"{vertex} -> "
            result += " ".join(map(str, neighbors))
            result += "\n"
        return result
        # 각 정점과 해당 정점에서 나가는 간선의 목적지를 문자열로 변환하여 반환

# 그래프 생성
vertices = 4
graph = DirectedGraphAdjacencyList(vertices)
# 4개의 정점을 가지는 방향 그래프 생성

graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 0)
# 방향 간선을 추가하여 그래프를 구성

# 그래프 출력
print("방향 그래프 인접 리스트:")
print(graph)
# 방향 그래프를 인접 리스트로 표현한 결과를 출력

출력 결과

방향 그래프 인접 리스트:
0 -> 1
1 -> 2
2 -> 3
3 -> 0

방향 가중치 그래프 구현

class WeightedDirectedGraphAdjacencyList:
    def __init__(self, vertices):
        # 그래프 클래스를 초기화하는 생성자 함수
        self.vertices = vertices  # 그래프의 정점 수
        self.adjacency_list = [[] for _ in range(vertices)]
        # 인접 리스트를 초기화하고, 빈 리스트로 각 정점에 대한 연결 정보를 저장

    def add_edge(self, u, v, weight):
        # 정점 u에서 v로의 방향 간선과 가중치를 추가하는 함수
        self.adjacency_list[u].append((v, weight))
        # 정점 u의 연결 리스트에 정점 v와 가중치를 추가

    def __str__(self):
        # 그래프를 문자열로 표현하기 위한 함수
        result = ""
        for vertex, neighbors in enumerate(self.adjacency_list):
            result += f"{vertex} -> "
            result += " ".join([f"({neighbor[0]}, {neighbor[1]})" for neighbor in neighbors])
            result += "\n"
        return result
        # 각 정점과 해당 정점에서 나가는 간선의 목적지와 가중치를 문자열로 변환하여 반환

# 그래프 생성
vertices = 4
graph = WeightedDirectedGraphAdjacencyList(vertices)
# 4개의 정점을 가지는 방향 가중치 그래프 생성

graph.add_edge(0, 1, 2)
graph.add_edge(1, 2, 3)
graph.add_edge(2, 3, 1)
graph.add_edge(3, 0, 4)
# 방향 간선과 가중치를 추가하여 그래프를 구성

# 그래프 출력
print("방향 가중치 그래프 인접 리스트:")
print(graph)
# 방향 가중치 그래프를 인접 리스트로 표현한 결과를 출력

출력 결과

방향 가중치 그래프 인접 리스트:
0 -> (1, 2)
1 -> (2, 3)
2 -> (3, 1)
3 -> (0, 4)