Графтағы алгоритм түрлері

Графтағы іздеу — белгілі бір шартқа сай төбені табу үшін графтың барлық төбесін жүйелі қарап шығу. Ең кең тараған екі әдіс бар — оларды лабиринтте жүру мысалымен түсінуге болады.

n = 10
adj_list = [[2, 4, 6], [9], [0, 3], [2, 4], [0, 3], [], [0, 7, 8], [6], [6], [1]]
s = 0
visited = [False] * n

def dfs(v):
    visited[v] = True
    for w in adj_list[v]:
        if visited[w] == False:
            dfs(w)

dfs(s)
print(visited.count(True))

DFS рекурсия (немесе стек) қолданса, BFS уақытша ақпаратты сақтау үшін кезек (жаңа элемент соңына қосылып, ескісі басынан алынатын тізім) қолданады.

adj = [[1, 3], [0, 3, 4, 5], [4, 5], [0, 1, 5], [1, 2], [1, 2, 3]]
level = [-1] * len(adj)

def bfs(s):
    global level
    level[s] = 0
    stack = [s]
    while stack:
        v = stack.pop(0)
        for w in adj[v]:
            if level[w] == -1:
                level[w] = level[v] + 1
                stack.append(w)

bfs(0)
print(level)

Ең ҚЫСҚА жолды табу үшін ең қарапайым идея — әр қадамда ЕҢ ЖАҚЫН қалаға өту. Бірақ бұл ӘРДАЙЫМ дұрыс жауап бере ме?

Информатикада ең қысқа жол іздеудің бірнеше атақты алгоритмі бар — олардың айырмашылығы, НЕ ІЗДЕЙТІНІНДЕ:

Прима-Крускал — тойымсыз алгоритм, БІРАҚ бұл жерде ол әрқашан дұрыс жұмыс істейді: әр қадамда ағашқа қосылмаған ЕҢ АРЗАН қабырға таңдалады, циклдің құрылмауын бақылау үшін әр төбе «түспен» белгіленеді.

col = [i for i in range(N)]
ostov = []
for k in range(N - 1):
    minDist = 1e10
    for i in range(N):
        for j in range(N):
            if col[i] != col[j] and W[i][j] < minDist:
                iMin, jMin, minDist = i, j, W[i][j]
    ostov.append((iMin, jMin))
    c = col[jMin]
    for i in range(N):
        if col[i] == c:
            col[i] = col[iMin]

Флойд алгоритмі ерекше ықшам — небәрі үш кірістірілген цикл арқылы БАРЛЫҚ жұптың ең қысқа жолын табады, әр аралық k төбе арқылы өту қысқарақ бола ма деп тексереді:

for k in range(N):
    for i in range(N):
        for j in range(N):
            if a[i][k] + a[k][j] < a[i][j]:
                a[i][j] = a[i][k] + a[k][j]

Дейкстра алгоритмі бір бастапқы төбеден бастап, әр қадамда ТЕКСЕРІЛМЕГЕН, ЕҢ ЖАҚЫН төбені таңдап, оның арқылы басқа қашықтықтарды «қысқартады»:

D[K] = 0  # бастапқы төбе қашықтығы 0
for i in range(N):
    M = -1
    for j in range(N):
        if not Use[j] and (M == -1 or D[j] < D[M]):
            M = j
    Use[M] = True
    for j in range(N):
        if D[j] > A[M][j] + D[M]:
            D[j] = A[M][j] + D[M]