위상 자료구조를 사용한 그래프에서 특정 노드에 접근해야 할 때, 노드의 인접 노드만 가지고 있다면, 다음 방법을 사용할 수 있습니다.
1. 깊이 우선 탐색 (DFS): 인접 노드 중 하나를 선택하여 방문하고, 그 노드의 인접 노드를 방문하는 과정을 반복합니다. 이 과정을 통해 모든 노드에 접근할 수 있습니다.
2. 너비 우선 탐색 (BFS): 인접 노드 중 하나를 선택하여 방문하고, 그 노드의 인접 노드를 방문하는 과정을 반복합니다. 이 과정을 통해 모든 노드에 접근할 수 있습니다.
3. 탐색 알고리즘 사용: 그래프 탐색 알고리즘을 사용하여 노드에 접근할 수 있습니다. 예를 들어, Dijkstra 알고리즘, Bellman-Ford 알고리즘, 또는 Floyd-Warshall 알고리즘을 사용할 수 있습니다.
위의 방법 중 하나를 선택하여 노드에 접근할 수 있습니다.
#hostingforum.kr
python
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 예제 그래프
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
위의 코드는 너비 우선 탐색 알고리즘을 사용하여 노드에 접근하는 방법을 보여줍니다.
#hostingforum.kr
python
def dfs(graph, start_node):
visited = set()
stack = [start_node]
visited.add(start_node)
while stack:
node = stack.pop()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
visited.add(neighbor)
# 예제 그래프
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A')
위의 코드는 깊이 우선 탐색 알고리즘을 사용하여 노드에 접근하는 방법을 보여줍니다.
#hostingforum.kr
python
import heapq
def dijkstra(graph, start_node):
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
queue = [(0, start_node)]
while queue:
current_distance, current_node = heapq.heappop(queue)
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 예제 그래프
graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'D': 2, 'E': 4},
'C': {'A': 3, 'F': 5},
'D': {'B': 2},
'E': {'B': 4, 'F': 1},
'F': {'C': 5, 'E': 1}
}
print(dijkstra(graph, 'A'))
위의 코드는 Dijkstra 알고리즘을 사용하여 노드에 접근하는 방법을 보여줍니다.
위의 방법 중 하나를 선택하여 노드에 접근할 수 있습니다.
2025-03-06 03:57