깊이우선탐색(DFS), 너비우선탐색 (BFS) - python으로 구현하기

* 수정

그런데 이 코드, 양방향 리스트인 경우 방문했던곳을 또 방문해버리는 오류가 있다.

 

그래서 양방향 리스트인 경우, 방문했던곳을 또 방문하지 않는 코드를 넣었다.

# 정점 개수 N, 간선 개수 M, 탐색 시작 번호 V
N, M, V = map(int, input().split())

edgeList = []
graph = [[] for vertex in range(N+1)]

for i in range(M):
    e0, e1 = map(int, input().split())
    edgeList.append((e0, e1))

for edge in edgeList:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

for i in range(len(graph)):
    graph[i].sort(reverse=True)

print(graph)

#DFS
def DFS(graph, V) :
    visited = []
    stack = [V]

    while stack :
        current = stack.pop()

        if current in visited:  # 이미 방문한 노드는 무시
            continue
     
        for n in graph[current]:
            if not n in visited:
                stack.append(n)
        visited.append(current)
   
    return visited

print(DFS(graph, V))

 

깊이우선탐색(DFS)

1. 우선 정점 리스트가 하나 필요하다.

vertexList = [’0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ’6’]

 

2. 연결되어있는거 리스트 안의 리스트로 표현

0에서 1가는거, 0에서 2가는거, 1에서 0가는거, 1에서 3가는거

edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4) ]

 

3. 인접 리스트를 만든다 → 정점리스트와 edgeList를 이용해서 리스트안의 리스트로 만들면 된다.

adjacencyList = [[] for vertex in vertexList]

 

# vertex는 변수임. 그냥 List 만큼 빈 리스트 [] 생성하는거

for edge in edgeList:
    adjacencyList[edge[0]].append(edge[1])

 

# 인덱스 edge[0]번에 edge[1]의 값을 추가하는것.

# 그러면 만들어진 결과는 정점인덱스의 리스트 안에 연결된 정점이 들어가는꼴.

[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
# 0번 정점에 1,2 연결
# 1번 정점에 0,3 연결

 

4. DFS 실행 코드

인접 리스트를 만들면 DFS를 실행할 수 있다.

스택 준비, current라는 변수를 만든다.

 

0이 처음 스택에 들어간다 → 0을 pop한다. → 0의 이웃들 1,2를 스택에 넣는다. → 0이 방문되었다고 표시한다.

그후 2를 pop한다 → 2 옆에있는 이웃들 4,5를 스택에 넣는다. (방문되었다고 표시된거 제외) → 2가 방문되었다고 표시한다.

5를 pop한다 → 5 옆에 있는 이웃들 없음

4를 pop한다 → 4의 근접 vertex를 스택에 넣는다 (방문되었다 표시한 2 제외) → 4가 방문되었다고 표시한다.

반복..

def DFS() :
    visitedVertex = []
    stack = [0]
    while stack:
        current = stack.pop()
        for neighbor in adjacencyList[current]:
            if not neighbor in visitedVertex:
                stack.append(neighbor)
        visitedVertex.append(current)
    return visitedVertex

 

어디에 사용될까? → 체스의 수, 그래프가 주어지고 그래프 안에 사이클이 있는지 없는지

 

최종 작성 코드

vertexList = ['0', '1', '2', '3', '4', '5', '6']

edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4) ]

# vertex는 변수임. 그냥 List 만큼 빈 리스트 [] 생성하는거
adjacencyList = [[] for vertex in vertexList]

for edge in edgeList:
    adjacencyList[edge[0]].append(edge[1])

# 인덱스 edge[0]번에 edge[1]의 값을 추가하는것.
# 그러면 만들어진 결과는 정점인덱스의 리스트 안에 연결된 정점이 들어가는꼴.

def DFS() :
    visitedVertex = []
    stack = [0]
    while stack:
        current = stack.pop()
        for neighbor in adjacencyList[current]:
            if not neighbor in visitedVertex:
                stack.append(neighbor)
        visitedVertex.append(current)
    return visitedVertex

print(DFS())

 

---

너비우선탐색(BFS)

1~3번은 동일하다.

 

4. BFS 실행코드

 

큐가 있어야한다.

0 → 0의 이웃 1,2 큐에 들어감 → 1 나옴 → 1의 이웃 3 큐에 들어감 → 2 나옴

 

어디에 사용될까? 최근접 거리 구할때 - 다익스트라도 BFS이다.

def BFS():
    visitedList = []
    queue = [0]

    while queue:
        current = queue.pop()
        for neigbor in adjacencyList[current]:
            if not neigbor in visitedList:
                queue.insert(0, neigbor)
        visitedList.append(current)
    return visitedList

print(BFS())

 

최종 작성 코드

vertexList = ['0', '1', '2', '3', '4', '5', '6']

edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4) ]

# vertex는 변수임. 그냥 List 만큼 빈 리스트 [] 생성하는거
adjacencyList = [[] for vertex in vertexList]

for edge in edgeList:
    adjacencyList[edge[0]].append(edge[1])

# 인덱스 edge[0]번에 edge[1]의 값을 추가하는것.
# 그러면 만들어진 결과는 정점인덱스의 리스트 안에 연결된 정점이 들어가는꼴.

def BFS():
    visitedList = []
    queue = [0]

    while queue:
        current = queue.pop()
        for neigbor in adjacencyList[current]:
            if not neigbor in visitedList:
                queue.insert(0, neigbor)
        visitedList.append(current)
    return visitedList

print(BFS())

---

https://youtu.be/BLc3wzvycH8?si=eF15hTVnQ7IBjHP-

위의 강의를 보고 작성한 코드입니다

---

강의자분이 작성한 코드

vertexList = ['0', '1', '2', '3', '4', '5', '6']
edgeList = [(0,1), (0,2), (1,0) , (1,3) , (2,0) , (2,4) , (2,5) , (3,1), (4,2) , (4,6), (5,2), (6,4)]
graphs = (vertexList, edgeList)

def dfs(graph, start):
    vertexList, edgeList = graph
    visitedVertex = []
    stack = [start]
    adjacencyList = [[] for vertex in vertexList]

    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])

    while stack:
        current = stack.pop()
        for neighbor in adjacencyList[current]:
            if not neighbor in visitedVertex:
                stack.append(neighbor)
        visitedVertex.append(current)
    return visitedVertex

print(dfs(graphs, 0))

vertexList = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
edgeList = [(0,1), (1,2), (1,3), (3,4), (4,5), (1,6)]
graphs = (vertexList, edgeList)

def bfs(graph, start):
    vertexList, edgeList = graph
    visitedList = []
    queue = [start]
    adjacencyList = [[] for vertex in vertexList]

    # fill adjacencyList from graph
    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])

    # bfs
    while queue:
        current = queue.pop()
        for neighbor in adjacencyList[current]:
            if not neighbor in visitedList:
                queue.insert(0,neighbor)
        visitedList.append(current)
    return visitedList

print(bfs(graphs, 0))

 

이건 start 지점을 지정할 수 있다. 코딩테스트를 볼땐 이렇게 작성해야할듯.