1
2
3
4
5
6
7
8
9
10
11
12
13
14
from __future__ import annotations
from dataclasses import dataclass


@dataclass  # __init__ 자동 생성
class Edge:
    u:int   # 정점(from)
    v:int   # 정점(to)

    def reversed(self) -> Edge:
        return Edge(self.v, self.u)

    def __repr__(self) -> str:
        return f"{self.u} -> {self.v}"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from typing import TypeVar, Generic, List, Optional
from edge import Edge

V = TypeVar("V")    # 그래프 정점(vertice) 타입


class Graph(Generic[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[Edge]] = [[] for _ in vertices]

    @property
    def vertex_count(self) -> int:
        return len(self._vertices)          # 반환: 정점의 수

    @property
    def edge_count(self) -> int:
        return sum(map(len, self._edges))   # 반환: Edge의 수
        # map 함수를 통해 _edges 리스트의 각 항목의 길이를 구한 뒤, sum 함수를 사용해 모두 합친다. 

    def add_vertex(self, vertex:V) -> int:
        self._vertices.append(vertex)
        self._edges.append([])
        return self.vertex_count - 1        # 반환: 정점의 인덱스

    # Edge 추가
    def add_edge(self, edge:Edge) -> None:
        self._edges[edge.u].append(edge)
        self._edges[edge.v].append(edge.reversed())
        # 정점 a: a -> b
        # 정점 b: b -> a

    # 정점 인덱스를 사용하여 Edge 추가
    def add_edge_by_indices(self, u:int, v:int) -> None:
        edge:Edge = Edge(u, v)
        self.add_edge(edge)

    # 정점 인덱스를 참조하여 Edge 추가
    def add_edge_by_vertices(self, first:V, second:V) -> None:
        u:int = self._vertices.index(first)
        v:int = self._vertices.index(second)
        self.add_edge_by_indices(u, v)
        # index 함수를 사용하면 위치를 찾을 수 있다.

    # 인덱스 -> 정점
    def vertex_at(self, index:int) -> V:
        return self._vertices[index]

    # 정점 -> 인덱스
    def index_of(self, vertex:V) -> int:
        return self._vertices.index(vertex)

    # 정점 인덱스에 연결된 정점
    def neighbors_for_index(self, index:int) -> List[V]:
        return list(map(self.vertex_at, [e.v for e in self._edges[index]]))
        # 엣지의 모든 끝 점(v)의 각 인덱스에 해당하는 정점의 리스트

    # 정점에 연결된 이웃 정점
    def neighbors_for_vertex(self, vertex:V) -> List[V]:
        return self.neighbors_for_index(self.index_of(vertex))

    # 정점 인덱스에 연결된 Edge
    def edges_for_index(self, index:int) -> List[Edge]:
        return self._edges[index]

    # 정점에 연결된 Edge
    def edges_for_vertex(self, vertex:V) -> List[Edge]:
        return self.edges_for_index(self.index_of(vertex))

    # 그래프 출력
    def __repr__(self) -> str:
        desc:str = ""
        for i in range(self.vertex_count):
            desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index(i)}\n"
        return desc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
if __name__ == "__main__":
    city_graph:Graph[str] = Graph(
        ["시애틀"       , "샌프란시스코", "로스앤젤레스",
         "리버사이드"   , "피닉스"      , "시카고",
         "보스턴"       , "뉴욕"        , "애틀랜타",
         "마이애미"     , "댈러스"      , "휴스턴",
         "디트로이트"   , "필라델피아"  , "워싱턴"])
                                   
    city_graph.add_edge_by_vertices("시애틀"      , "시카고")
    city_graph.add_edge_by_vertices("시애틀"      , "샌프란시스코")
    city_graph.add_edge_by_vertices("샌프란시스코", "리버사이드")
    city_graph.add_edge_by_vertices("샌프란시스코", "로스앤젤레스")
    city_graph.add_edge_by_vertices("로스앤젤레스", "리버사이드")
    city_graph.add_edge_by_vertices("로스앤젤레스", "피닉스")
    city_graph.add_edge_by_vertices("리버사이드"  , "피닉스")
    city_graph.add_edge_by_vertices("리버사이드"  , "시카고")
    city_graph.add_edge_by_vertices("피닉스"      , "댈러스")
    city_graph.add_edge_by_vertices("피닉스"      , "휴스턴")
    city_graph.add_edge_by_vertices("댈러스"      , "시카고")
    city_graph.add_edge_by_vertices("댈러스"      , "애틀랜타")
    city_graph.add_edge_by_vertices("댈러스"      , "휴스턴")
    city_graph.add_edge_by_vertices("휴스턴"      , "애틀랜타")
    city_graph.add_edge_by_vertices("휴스턴"      , "마이애미")
    city_graph.add_edge_by_vertices("애틀랜타"    , "시카고")
    city_graph.add_edge_by_vertices("애틀랜타"    , "워싱턴")
    city_graph.add_edge_by_vertices("애틀랜타"    , "마이애미")
    city_graph.add_edge_by_vertices("마이애미"    , "워싱턴")
    city_graph.add_edge_by_vertices("시카고"      , "디트로이트")
    city_graph.add_edge_by_vertices("디트로이트"  , "보스턴")
    city_graph.add_edge_by_vertices("디트로이트"  , "워싱턴")
    city_graph.add_edge_by_vertices("디트로이트"  , "뉴욕")
    city_graph.add_edge_by_vertices("보스턴"      , "뉴욕")
    city_graph.add_edge_by_vertices("뉴욕"        , "필라델피아")
    city_graph.add_edge_by_vertices("필라델피아"  , "워싱턴")
    
    print(city_graph) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if __name__ == "__main__":
	from generic_search import bfs, Node, node_to_path
    
    root = "보스턴"
    goal = "마이애미"

    bfs_result:Optional[Node[V]] = bfs(root, 
                                       lambda x: x == goal, 
                                       city_graph.neighbors_for_vertex)
    if bfs_result is None:
        print("너비 우선 탐색으로 답을 찾을 수 없습니다!")
    else:
        path:List[V] = node_to_path(bfs_result)
        print(f"{root}에서 {goal}까지 최단 경로: ")
        print(path)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from __future__ import annotations
from dataclasses import dataclass
from edge import Edge


@dataclass
class WeightedEdge(Edge):
    weight:float

    def reversed(self) -> WeightedEdge:
        return WeightedEdge(self.v, self.u, self.weight)

    def __lt__(self, other:WeightedEdge) -> bool:
        return self.weight < other.weight

    def __repr__(self) -> str:
        return f"{self.u} {self.weight} -> {self.v}"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from typing import TypeVar, Generic, List, Tuple
from graph import Graph
from weighted_edge import WeightedEdge

V = TypeVar("V")    # 그래프 정점(vertice) 타입


class WeightedGraph(Generic[V], Graph[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[WeightedEdge]] = [[] for _ in vertices]

    def add_edge_by_indices(self, u:int, v:int, weight:float) -> None:
        edge:WeightedEdge = WeightedEdge(u, v, weight)
        self.add_edge(edge)

    def add_edge_by_vertices(self, first:V, second:V, weight:float) -> None:
        u:int = self._vertices.index(first)
        v:int = self._vertices.index(second)
        self.add_edge_by_indices(u, v, weight)

    def neighbors_for_index_with_weights(self, index:int) -> List[Tuple[V, float]]:
        distance_tuples:List[Tuple[V, float]] = []
        for edge in self.edges_for_index(index):
            distance_tuples.append((self.vertex_at(edge.v), edge.weight))
        return distance_tuples

    def __repr__(self) -> str:
        desc:str = ""
        for i in range(self.vertex_count):
            desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index_with_weights(i)}\n"
        return desc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
if __name__ == "__main__":
    city_graph2:WeightedGraph[str] = WeightedGraph(
        ["시애틀"       , "샌프란시스코", "로스앤젤레스",
         "리버사이드"   , "피닉스"      , "시카고",
         "보스턴"       , "뉴욕"        , "애틀랜타",
         "마이애미"     , "댈러스"      , "휴스턴",
         "디트로이트"   , "필라델피아"  , "워싱턴"])
                                   
    city_graph2.add_edge_by_vertices("시애틀"      , "시카고"      , 1737)
    city_graph2.add_edge_by_vertices("시애틀"      , "샌프란시스코", 678)
    city_graph2.add_edge_by_vertices("샌프란시스코", "리버사이드"  , 386)
    city_graph2.add_edge_by_vertices("샌프란시스코", "로스앤젤레스", 348)
    city_graph2.add_edge_by_vertices("로스앤젤레스", "리버사이드"  , 50)
    city_graph2.add_edge_by_vertices("로스앤젤레스", "피닉스"      , 357)
    city_graph2.add_edge_by_vertices("리버사이드"  , "피닉스"      , 307)
    city_graph2.add_edge_by_vertices("리버사이드"  , "시카고"      , 1704)
    city_graph2.add_edge_by_vertices("피닉스"      , "댈러스"      , 887)
    city_graph2.add_edge_by_vertices("피닉스"      , "휴스턴"      , 1015)
    city_graph2.add_edge_by_vertices("댈러스"      , "시카고"      , 805)
    city_graph2.add_edge_by_vertices("댈러스"      , "애틀랜타"    , 721)
    city_graph2.add_edge_by_vertices("댈러스"      , "휴스턴"      , 225)
    city_graph2.add_edge_by_vertices("휴스턴"      , "애틀랜타"    , 702)
    city_graph2.add_edge_by_vertices("휴스턴"      , "마이애미"    , 968)
    city_graph2.add_edge_by_vertices("애틀랜타"    , "시카고"      , 588)
    city_graph2.add_edge_by_vertices("애틀랜타"    , "워싱턴"      , 543)
    city_graph2.add_edge_by_vertices("애틀랜타"    , "마이애미"    , 604)
    city_graph2.add_edge_by_vertices("마이애미"    , "워싱턴"      , 923)
    city_graph2.add_edge_by_vertices("시카고"      , "디트로이트"  , 238)
    city_graph2.add_edge_by_vertices("디트로이트"  , "보스턴"      , 613)
    city_graph2.add_edge_by_vertices("디트로이트"  , "워싱턴"      , 396)
    city_graph2.add_edge_by_vertices("디트로이트"  , "뉴욕"        , 482)
    city_graph2.add_edge_by_vertices("보스턴"      , "뉴욕"        , 190)
    city_graph2.add_edge_by_vertices("뉴욕"        , "필라델피아"  , 81)
    city_graph2.add_edge_by_vertices("필라델피아"  , "워싱턴"      , 123)
    
    print(city_graph2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from typing import TypeVar, Generic, List
from heapq import heappush, heappop

T = TypeVar("T")


class PriorityQueue(Generic[T]):
    def __init__(self) -> None:
        self._container:List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container

    def push(self, item:T) -> None:
        heappush(self._container, item)

    def pop(self) -> T:
        return heappop(self._container)

    def __repr__(self) -> str:
        return repr(self._container)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from typing import TypeVar, List, Optional
from weighted_graph import WeightedGraph
from weighted_edge import WeightedEdge
from priority_queue import PriorityQueue

V = TypeVar("V")    # 그래프 정점(vertice) 타입
WeightedPath = List[WeightedEdge]


def total_weight(wp:WeightedPath) -> float:
    return sum([e.weight for e in wp])


def mst(wg:WeightedGraph[V], start:int = 0) -> Optional[WeightedPath]:
    """minimum spanning tree"""

    # 시작 정점이 유효하지 않은 경우 None
    if start > (wg.vertex_count - 1) or start < 0:
        return None

    result:WeightedPath = []
    pq:PriorityQueue[WeightedEdge] = PriorityQueue()
    visited:List[bool] = [False] * wg.vertex_count  # 방문한 곳
    def visit(index:int):
        visited[index] = True
        for edge in wg.edges_for_index(index):
            if not visited[edge.v]:
                pq.push(edge)

    visit(start)
    while not pq.empty:
        edge = pq.pop()
        if visited[edge.v]:
            continue
        result.append(edge)
        visit(edge.v)
    return result


def print_weighted_path(wg:WeightedGraph, wp:WeightedPath) -> None:
    for edge in wp:
        print(f"{wg.vertex_at(edge.u)} {edge.weight}> {wg.vertex_at(edge.v)}")
    print(f"가중치 총합: {total_weight(wp)}")

1
2
3
4
5
6
7
if __name__ == "__main__":
    ...
    result:Optional[WeightedPath] = mst(city_graph2)
    if result is None:
        print("최소 신장 트리로 답을 찾을 수 없습니다!")
    else:
        print_weighted_path(city_graph2, result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from __future__ import annotations
from turtle import distance
from typing import TypeVar, List, Optional, Tuple, Dict
from dataclasses import dataclass
from priority_queue import PriorityQueue
from mst import WeightedPath, print_weighted_path
from weighted_graph import WeightedGraph
from weighted_edge import WeightedEdge
from priority_queue import PriorityQueue

V = TypeVar("V")    # 그래프 정점(vertice) 타입


@dataclass
class DijkstraNode:
    vertex:int
    distance:float

    def __lt__(self, other:DijkstraNode) -> bool:
        return self.distance < other.distance

    def __eq__(self, other:DijkstraNode) -> bool:
        return self.distance == other.distance


def dijkstra(wg:WeightedGraph[V], root:V) -> Tuple[List[Optional[float]], Dict[int, WeightedEdge]]:
    first:int = wg.index_of(root)
    distances:List[Optional[float]] = [None] * wg.vertex_count
    distances[first] = 0
    path_dict:Dict[int, WeightedEdge] = {}
    pq:PriorityQueue[DijkstraNode] = PriorityQueue()
    pq.push(DijkstraNode(first, 0))

    while not pq.empty:
        u:int = pq.pop().vertex
        dist_u:float = distances[u]
        for we in wg.edges_for_index(u):
            dist_v:float = distances[we.v]
            if dist_v is None or dist_v > we.weight + dist_u:
                distances[we.v] = we.weight + dist_u
                path_dict[we.v] = we
                pq.push(DijkstraNode(we.v, we.weight + dist_u))
    return distances, path_dict


def distance_array_to_vertex_dict(wg:WeightedGraph[V], distances:List[Optional[float]]) -> Dict[V, Optional[float]]:
    distance_dict:Dict[V, Optional[float]] = {}
    for i in range(len(distances)):
        distance_dict[wg.vertex_at(i)] = distances[i]
    return distance_dict


def path_dict_to_path(start:int, end:int, path_dict:Dict[int, WeightedEdge]) -> WeightedPath:
    if len(path_dict) == 0:
        return []
    edge_path:WeightedPath = []
    e:WeightedEdge = path_dict[end]
    edge_path.append(e)
    while e.u != start:
        e = path_dict[e.u]
        edge_path.append(e)
    return list(reversed(edge_path))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if __name__ == "__main__":
   	 ...
    root = "로스앤젤레스"
    distances, path_dict = dijkstra(city_graph2, root)
    name_distance:Dict[str, Optional[int]] = distance_array_to_vertex_dict(city_graph2, distances)
    print(f"{root}에서의 거리:")
    for key, value in name_distance.items():
        print(f"{key} : {value}")
    print("")

    goal = "보스턴"
    print(f"{root}에서 {goal}까지의 최단 경로:")
    path:WeightedPath = path_dict_to_path(city_graph2.index_of(root), 
                                          city_graph2.index_of(goal), 
                                          path_dict)
    print_weighted_path(city_graph2, path)

1
2
3
4
5
6
from __future__ import annotations
from typing import TypeVar, List
from edge import Edge
from graph import Graph

V = TypeVar("V")    # 그래프 정점(vertice) 타입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class RemovableGraph(Graph[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[Edge]] = [[] for _ in vertices]

    def remove_vertex(self, vertex:V) -> None:
        target:int = self._vertices.index(vertex)
        self._edges[target] = []
        self._vertices[target] = None

    def remove_edge(self, edge:Edge) -> None:
        self._edges[edge.u].remove(edge)
        self._edges[edge.v].remove(edge.reversed())

    def remove_edge_by_indices(self, u:int, v:int) -> None:
        edge:Edge = Edge(u, v)
        self.remove_edge(edge)

    def remove_edge_by_vertices(self, first:V, second:V) -> None:
        u:int = self._vertices.index(first)
        v:int = self._vertices.index(second)
        self.remove_edge_by_indices(u, v)

    def neighbors_for_index(self, index:int) -> List[V]:
        return list(filter(lambda x: x, map(self.vertex_at, [e.v for e in self._edges[index]])))

    def __repr__(self) -> str:
        desc:str = ""
        for i in range(self.vertex_count):
            if not self.vertex_at(i):
                continue
            desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index(i)}\n"
        return desc

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
    ex41:RemovableGraph[str] = RemovableGraph(["A", "B", "C"])

    ex41.add_edge_by_vertices("A", "B")
    ex41.add_edge_by_vertices("B", "C")
    ex41.add_edge_by_vertices("C", "A")
    print(ex41)

    ex41.remove_edge_by_vertices("A", "C")
    print(ex41)
    ex41.remove_vertex("A")
    print(ex41)

1
2
3
4
def remove_vertex(self, vertex:V) -> None:
    target:int = self._vertices.index(vertex)
    del self._edges[target]
    del self._vertices[target]

1
2
3
4
def remove_vertex(self, vertex:V) -> None:
    target:int = self._vertices.index(vertex)
    self._edges[target] = []
    self._vertices[target] = None

1
2
3
4
5
6
7
def __repr__(self) -> str:
    desc:str = ""
    for i in range(self.vertex_count):
        if not self.vertex_at(i):
            continue
        desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index(i)}\n"
    return desc

1
2
def neighbors_for_index(self, index:int) -> List[V]:
    return list(map(self.vertex_at, filter(lambda x: x, [e.v for e in self._edges[index]])))

1
2
def neighbors_for_index(self, index:int) -> List[V]:
    return list(filter(lambda x: x, map(self.vertex_at, [e.v for e in self._edges[index]])))

1
2
3
4
5
6
7
8
class Digraph(Graph[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[Edge]] = [[] for _ in vertices]

    def add_edge(self, edge:Edge) -> None:
        self._edges[edge.u].append(edge)
        # self._edges[edge.v].append(edge.reversed())

1
2
3
4
5
6
7
8
9
10
11
if __name__ == "__main__":
    ex42:Digraph[str] = Digraph(["A", "B", "C"])

    ex42.add_edge_by_vertices("A", "B")
    ex42.add_edge_by_vertices("A", "C")
    ex42.add_edge_by_vertices("B", "A")
    ex42.add_edge_by_vertices("B", "C")
    ex42.add_edge_by_vertices("C", "A")
    ex42.add_edge_by_vertices("C", "B")

    print(ex42)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Digraph(Graph[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[Edge]] = [[] for _ in vertices]

    def add_edge(self, edge:Edge, direction:bool = False) -> None:
        self._edges[edge.u].append(edge)
        if not direction:
            self._edges[edge.v].append(edge.reversed())

    def add_edge_by_indices(self, u:int, v:int, direction:bool = False) -> None:
        edge:Edge = Edge(u, v)
        self.add_edge(edge, direction)

    def add_edge_by_vertices(self, first:V, second:V, direction:bool = False) -> None:
        u:int = self._vertices.index(first)
        v:int = self._vertices.index(second)
        self.add_edge_by_indices(u, v, direction)

1
2
3
4
5
6
7
8
if __name__ == "__main__":
    ex42:Digraph[str] = Digraph(["A", "B", "C"])

    ex42.add_edge_by_vertices("A", "C", False)  # 무향
    ex42.add_edge_by_vertices("B", "A", True)   # 유향
    ex42.add_edge_by_vertices("B", "C", True)   # 유향

    print(ex42)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@dataclass
class bridgeEdge(Edge):
    id:int  # 식별자

    def reversed(self) -> bridgeEdge:
        return Edge(self.v, self.u, self.id)

    def __repr__(self) -> str:
        return f"<{self.id}> {self.u} -> {self.v}"


class BridgeGraph(Graph[V]):
    def __init__(self, vertices:List[V] = []) -> None:
        self._vertices:List[V] = vertices
        self._edges:List[List[BridgeEdge]] = [[] for _ in vertices]

    def add_edge_by_indices(self, u:int, v:int, name:str) -> None:
        edge:BridgeEdge = BridgeEdge(u, v, name)
        self.add_edge(edge)

    def add_edge_by_vertices(self, first:V, second:V, name:str) -> None:
        u:int = self._vertices.index(first)
        v:int = self._vertices.index(second)
        self.add_edge_by_indices(u, v, name)

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
    ex43:BridgeGraph[str] = BridgeGraph(["A", "B", "C", "D"])
                                   
    ex43.add_edge_by_vertices("A", "B", "a")
    ex43.add_edge_by_vertices("A", "B", "b")
    ex43.add_edge_by_vertices("A", "C", "c")
    ex43.add_edge_by_vertices("A", "C", "d")
    ex43.add_edge_by_vertices("A", "D", "e")
    ex43.add_edge_by_vertices("B", "D", "f")
    ex43.add_edge_by_vertices("C", "D", "g")

    print(ex43)

1
2
3
4
5
6
7
8
9
10
if __name__ == "__main__":
    ex43:BridgeGraph[str] = BridgeGraph(["A", "B", "C", "D"])
    ex43.add_edge_by_vertices("A", "B", "a")
    ex43.add_edge_by_vertices("A", "B", "b")
    ex43.add_edge_by_vertices("A", "C", "c")
    ex43.add_edge_by_vertices("A", "C", "d")
    ex43.add_edge_by_vertices("A", "D", "e")
    ex43.add_edge_by_vertices("B", "D", "f")
    ex43.add_edge_by_vertices("C", "D", "g")
    print(ex43)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
def visit(current:BridgeEdge, explored:List[BridgeEdge]):

    # 종료 조건: 모든 다리를 한 번씩 건넌다.
    if len(explored) == (ex43.edge_count / 2):
        print(explored) # 출력
        exit()          # 종료
        
    # 이동 가능한 곳
    promise:List[BridgeEdge] = list(filter(lambda x: False if (x.name in current.name) else True, 
                                            ex43.edges_by_edge(current)))

    print(f"-----{current}-------------------------")
    print(f"이미 지난 곳: {explored}")
    print(f"이동 가능한 곳: {promise}")

    # promise의 모든 BridgeEdge에 대한 탐색 시행
    for edge in promise:

        # 건널 수 없으면 continue
        if edge.name in explored:
            print(f"{edge.name} -> 불가능", end=" ")
            continue

        # 건널 수 있으면 재귀
        print(f"{edge.name} -> 가능")
        print(f"{edge.name}로 이동합니다.")
        print("\n\n")
        explored.append(edge.name)
        visit(edge, explored)

    # promise가 존재하지 않으면 되추적
    explored.remove(current.name)
    print()

1
2
3
4
5
...
initial = ex43._edges[1][0]
explored:List[str] = [initial.name]
visit(initial, explored)
print("실패!")  # 출력

1
2
3
4
5
6
7
8
9
10
11
if __name__ == "__main__":
    ex43:BridgeGraph[str] = BridgeGraph(["A", "B", "C", "D"])
    ex43.add_edge_by_vertices("A", "B", "a")
    ex43.add_edge_by_vertices("A", "B", "b")
    ex43.add_edge_by_vertices("A", "C", "c")
    ex43.add_edge_by_vertices("A", "C", "d")
    ex43.add_edge_by_vertices("A", "D", "e")
    ex43.add_edge_by_vertices("B", "D", "f")
    ex43.add_edge_by_vertices("C", "D", "g")
    ex43.add_edge_by_vertices("A", "D", "h")    # 추가된 경로
    print(ex43)