Graph 정렬, DFS, BFS 시작 노드가 없을 때도 출력

def bidirect_graph(values: list):
    graph = {}
    for val in values:
        k, v = val
        graph[k] = graph.get(k, []) + [v]
        graph[v] = graph.get(v, []) + [k]
        graph[k].sort()
        graph[v].sort()
    return graph

def DFS(graph, root, dfs_list=[]):
    if root not in dfs_list:
        dfs_list.append(root)
        if root in graph:
            for x in graph[root]:
                DFS(graph, x, dfs_list)

    return dfs_list

def BFS(graph, root):
    queue = deque([root])
    res = [root]
    while queue:
        start = queue.pop()
        if start in graph:
            for x in graph[start]:
                if x not in res:
                    queue.appendleft(x)
                    res.append(x)
    return res

graph = bidirect_graph(values)
print(' '.join(list(map(str, DFS(graph, V)))))
print(' '.join(list(map(str, BFS(graph, V)))))

Graph

Python Floyd-Warshall 플로이드 워셜

양방향 그래프 생성 코드

def bidirect_graph(values: list):
    graph = {}
    for val in values:
        k, v = val
        if k not in graph:
            graph[k] = []
        if v not in graph:
            graph[v] = []
            
        if v not in graph[k]:
            graph[k].append(v)
        if k not in graph[v]:
            graph[v].append(k)

# 위와 같음
def bidirect_graph(values: list):
    graph = {}
    for val in values:
        k, v = val
        graph[k] = graph.get(k, []) + [v]
        graph[v] = graph.get(v, []) + [k]
    return graph

if __name__ == "__main__":
    edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
    print(bidirect_graph(edge))
    # {3: [6, 4, 2, 1], 6: [3], 4: [3, 2], 2: [3, 1, 4, 5], 1: [3, 2], 5: [2]}

Deep First Search, Breadth First Search

def dfs_recur(node, graph, dfs_list = []):
    if node not in dfs_list:
        dfs_list.append(node)
        for x in graph[node]:
            dfs_recur(x, graph, dfs_list)

    return dfs_list

# node = [0, 0] # ex)
def bfs_queue(node, graph):
    from collections import deque
    queue = deque([node])
    res = [node]
    while queue:
        for x in graph[queue.pop()]:
            if x not in res:
                queue.appendleft(x)
                res.append(x)
    return res

BFS Level Search

def bfs_level(node, graph):
    from collections import deque
    current_queue = deque([node])
    res = [node]
    next_queue = deque([])
    level = 0
    level_dic = {0 : [node]}
    while current_queue:
        for x in graph[current_queue.pop()]:
            if x not in res:
                next_queue.appendleft(x)
                res.append(x)
        if current_queue == deque([]) and next_queue != deque([]):
            level += 1
            level_dic[level] = list(next_queue)
            current_queue = next_queue
            next_queue = deque([])
            
    return level_dic

# 체크만 하면 되면 빠르게 체크만 하고 넘어가는게 시간이 더 빠름
# 체크 해야 하는 개수가 파악일 될 때 사용 가능
def bfs_level_last(node, graph, n):
    from collections import deque
    current_queue = deque([node])
    check = [0]*n
    next_queue = deque([])
    level = 0
    check[0] = 1
    while current_queue:
        for x in graph[current_queue.pop()]:
            if check[x-1] == 0:
                next_queue.appendleft(x)
                check[x-1] = 1
        
        if current_queue == deque([]) and next_queue != deque([]):
            level += 1
            output = list(next_queue)
            current_queue = next_queue
            next_queue = deque([])
            
    return len(output)

n = 7
graph = {3: [6, 4, 2, 1], 6: [3], 4: [3, 2], 2: [3, 1, 4, 5], 1: [3, 2], 5: [2, 7], 7: [5]}
bfs_level_last(1, graph, n) # 1, 가장 끝 레벨 출력 하게 해놨음 나중에 수정해서 사용하면 될듯.

‣

네트워크

서로 다른 네트워크 구분 / 연결되어 있지 않은 노드끼리 확인

def dfs(node, graph, check, dfs_list = []):
    if node not in dfs_list:
        check[node] = True
        dfs_list.append(node)
        for x in graph[node]:
            dfs(x, graph, check, dfs_list)

    return dfs_list, check

def solution(n, computers):
    dic = {}
    for i, com in enumerate(computers):
        dic[i] = []
        for j, connect in enumerate(com):
            if i != j and connect == 1:
                dic[i].append(j)
                
    check = [False for _ in range(n)]
    networks = []
    for i in dic:
        if check[i] == False:
            d, check = dfs(i, dic, check, dfs_list = [])
            networks.append(d)
    print(networks)

# n = 3, computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# [[0, 1], [2]]

deque BFS, DFS

from collections import deque

def BFS(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += set(graph[n]) - set(visited)
    return visited

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

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += set(graph[n]) - set(visited)
    return visited