Graph Search

Graph Search

---

아래와 같은 Graph가 있다고 가정한다.

Depth Frist Search (DFS)

• 임의의 노드n을 선택
• n을 방문했다고 표시
• n의 방문하지 않은 인접 vertex를 방문한다.

Breadth First Search (BFS)

• 노드 n부터 시작하고, 방문했다고 표시하면서 큐에 삽입
• 큐가 empty일때까지 계속 반복하면서,
• 큐에서 첫번째 원소를 뽑는다. 그리고 뽑은 원소의 방문하지 않은 이웃들을 방문했다고 표시 후에 큐의 끝에 지어넣는다.

class graph:
    def __init__(self, vertexList, edgeList):
        self.vertexList = vertexList
        self.edgeList = edgeList
        self.adjacentList = [[] for id in range(len(vertexList))]
        for edge in edgeList:
            self.adjacentList[edge[0]].append(edge[1])

def recursiveDFS(graph,node, visited=[]):
    visited.append(node)
    for neighbor in graph.adjacentList[node]:
        if neighbor not in visited:
            recursiveDFS(graph, neighbor, visited)
    return visited

# queue에 insert 할 때 넣는 방법
def BFS(graph,node, visited=[]):
    queue = [node] # 맨 처음 버텍스를 삽입 한다.
    visited.append(node) # 방문한 리스트에 맨 처음 버텍스를 넣는다.
    while queue: # 큐가 비었는지 확인 한다
        current = queue.pop() # 큐에서 데이터를 꺼내온다.
        for neighbor in graph.adjacentList[current]: # 인접 vertex에서 값을 하나 가져온다.
            if not neighbor in visited: # 현재 인접 노드의 값이 방문한 것이 아닌지 확인 한다.
                queue.insert(0,neighbor)
                visited.append(neighbor)
    return visited

# queue에 pop할 때 visit 하는 방법
def BFS2(graph,node, visited=[]):
    queue = [node]
    #visited.append(node)

    while queue:
        current = queue.pop()
        for vertex in graph.adjacentList[current]:
            if vertex not in visited:
                queue.insert(0, vertex)
        visited.append(current)
    return visited



if __name__ == "__main__":

    # Depth First Search (DFS)
    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)]

    graphObj = graph(vertexList, edgeList)
    print("vertex list")
    print(graphObj.vertexList)
    print("edge list")
    print(graphObj.edgeList)
    print("adjacent list")
    print(graphObj.adjacentList)

    print("DFS Traverse:")
    print(recursiveDFS(graphObj,0))
    print("BFS Traverse:")
    print(BFS(graphObj,0))

실행결과

vertex list
['0', '1', '2', '3', '4', '5', '6']
edge list
[(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 4), (2, 5), (3, 1), (4, 2), (4, 6), (5, 2), (6, 4)]
adjacent list
[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]
DFS Traverse:
[0, 1, 3, 2, 4, 6, 5]
BFS Traverse:
[0, 1, 2, 3, 4, 5, 6]

참고자료
https://smlee729.github.io/python/network%20analysis/2015/04/09/1-networkx-dfs-bfs.html