グラフ＃グラフ＃

17703 ワード
アルゴリズムインタビュー アルゴリズム#アルゴリズム# algorithm Graph テキストリンク
グラフがよくわからないまま、いつ勉強すべきか考えて整理しています.
グラフは大きく二つに分かれている.
  • DFS(深度優先ナビゲーション):スタックによって実現され、再帰によってより簡単に実現される.
  • 広さ優先ブラウズ(BFS):キューの重複構造を採用しています.(推奨インデックス)
    • DFSはBFSより出題頻度が高い.
    画像の説明:https://velog.io/@yusokk/algorithm-graph

    📌 DFS


    👉 再帰的に実現する

    graph = {
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3],
}

def recursive_dfs(v,discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if not w in discovered:
            discovered = recursive_dfs(w , discovered)
    return discovered
print(recursive_dfs(1)) # [1, 2, 5, 6, 7, 3, 4]
  • 1->2->5->6に進み、戻ります.
  • 7->3、それからルートに遡ります.
  • 4
    ==> 1->2->5->6->7->3->4

    • https://leetcode.com/problems/permutations/ 
    from typing import List
import numpy as np

nums = [1,2,3]

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result        = []
        prev_elements = []

        def dfs(elements):
            if len(elements)==0:
                result.append(prev_elements[:])
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()
        dfs(nums)
        return result

solution = Solution()
print('result : ',solution.permute(nums))
    しかし、iteratoolsを使えば簡単に解けます.

    👉 itertoolsによる解析

    import itertools
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))
    このように簡単に解くことができますが、基本概念を熟知しなければならないので、前に書いたコードを理解してください.

    👉 スタックを使用した重複構造の実装

    graph = {
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3],
}

def iterative_dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

print(iterative_dfs(1)) # [1, 4, 3, 5, 7, 6, 2]
    スタックされているので、最後に挿入したノードから取り出して繰り返します.
    この場合、隣接ノードに最近含まれているノード、すなわち最後からアクセスするためである.

    📌 BFS


    👉 キューを使用した重複構造の実行

    graph = {
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3],
}

def iterative_bfs(start_v):
    discovered = [start_v]
    queue      = [start_v]

    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

print(iterative_bfs(1)) # [1, 2, 3, 4, 5, 6, 7]
    さらに最適化するためには、Deckなどの資料型を推奨します.
    数値順に実行します.
    1から各隣接ノードのBFSに優先的にアクセスする.

    📌 さかのぼる

  • テクノロジーは、すべての場合(完全ナビゲーションなど)にナビゲーションを行い、条件に合致しないケースを中間的に剪断することで、ナビゲーション時間を短縮する
  • ナビゲーションでは、条件に合致しない場合は前のプロシージャを返す必要があるため、再帰
    • がしばしば使用される.
  • どのように条件を設定して、いつエラーの時点
    • を返すかを設計します.
    AssemblyのInstructionのByte and Word
    アクセス制御者