[Graph] 최단경로검색, Dijkstra algorithm(다익스트라)
Dijkstra algorithm(다익스트라 알고리즘) 열심히 그렸는데, 맞겠지. stack에 값을 넣어놓고 pop해서 꺼내면 된다. *A에서 D로 가는 경우, A에서 B를 거쳐 D로 가게되면 8이 됨으로, 7A를 저장해 준다. class Graph: def __init__(self): self.node = set() self.edges = {} self.distances = {} def add_node(self, value): self.nodes.add(value) def add_edge(self, from_node, to_node, distance): self._add_edge(from_node, to_node, distance) self._add_edge(to_node, from_node, dist..
2018. 9. 25.
[Graph] BFS(Breadth first Search), 넓이우선탐색
[Graph] DFS(Depth first Search), 깊이우선탐색에서는 stack을 이용하고, BFS에서는 queue를 이용하면 된다. vertextList = [0, 1, 2, 3, 4, 5, 6] edgeList = [(0, 1), (1, 0), (0, 2), (2, 0), (1, 3), (3, 1), (2, 4), (4, 2), (2, 5), (5, 2), (4, 6), (6, 4)] graphs = (vertextList, edgeList) def bfs(graph, start): vertextList, edgeList = graph visitedVertex = [] queue = [start] adjacencyList = [[] for vertex in vertextList] for edg..
2018. 9. 25.
