자료구조_그래프실습

그래프 자료구조 실습

• 다음 트리의 자료구조 DFS를 탐색해 보시오

  • 실행 결과 예
  • node : A
  • 방문지점 : ["A"]
  • node : B
  • 방문지점 : ["A", "B"]
  • node : C
  • 방문지점 : ["A", "B", "C"]
  • node : D
  • 방문지점 : ["A", "B", "C", "D"]
  • node : E
  • STOP

graph = {"A" : ["B", "C"],
        "B" : ["D", "E"],
        "C" : ["F", "G"],
        "D" : ["B"],
        "E" : ["B"],
        "F" : ["C"],
        "G" : ["C"]}


def dfs_recursive(graph, start, visited=None):

    if visited is None:
        visited = []

    visited.append(start)
    print(f"방문지점 : {visited}")
    
    for node in graph[start]:
        print(f"node : {node}")

        if node not in visited:
            if node == "C":
                print("STOP")
            else:
                dfs_result = dfs_recursive(graph, node, visited)
                if dfs_result is not None:
                    return dfs_result
    
    return None

• 다음의 트리 자료구조를 이용하여 BFS를 탐색해 보시오.

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start]) 

    while queue:
        node = queue.popleft()
        if node not in visited:

            if node == "E":
                print(f"node:{node}")
                print("STOP")
                break
            else:
                print(f"node : {node}")
                visited.append(node)
                print(f"방문지점 : {visited}")

            queue.extend(graph[node])  
            
    return None

graph = {"A" : ["B", "C"],
        "B" : ["D", "E"],
        "C" : ["F", "G"],
        "D" : ["B"],
        "E" : ["B"],
        "F" : ["C"],
        "G" : ["C"]}

bfs_result = bfs(graph, "A")