Topoloji sıralama

10.1 Topoloji sıralamanın tərifi

Topoloji sıralama — istiqamətləndirilmiş tsiklsiz qrafın (DAG) zirvələrinin xətti düzülüşüdür ki, hər bir (u, v) qövsü üçün u zirvəsi v zirvəsindən əvvəl gəlir. Bu sıralama yalnız DAG üçün mümkündür və tsiklləri olan qraflarda edilə bilməz.

Necədi bu tərif? Əgər bunu ilk dəfə oxumaqda başa düşdünüzsə, yəqin ki, sizdə alqoritmlərlə işləməkdə böyük təcrübə var.

Sadə dillə belə deyək: sizdə tapşırıqların siyahısı var (qraf zirvələri) və onların arasındakı bağımlılıqlar (qrafdakı oxlar). Tapşırıqları (zirvələri) elə düzün ki, "A tapşırığı"na bağlı olan bütün tapşırıqlar ondan əvvəl yerinə yetirilsin. Və dərhal hər şey aydın olur, yoxsa "istiqamətləndirilmiş tsiklsiz qrafın zirvələrinin xətti düzülüşü"...

Topoloji sıralama praktikada çox vacib bir alqoritmdir, ona görə də ona xüsusi bir ad verilib, sadəcə müəllifin adı ilə kifayətlənməyib. Gəlin görək, harada lazımdır:

Tətbiqlər:

1. Tapşırıqların planlaşdırılması (Task Scheduling):

Bağımlı tapşırıqların elə bir düzülüşü ki, hər tapşırıq öz bağımlılıqlarından sonra icra edilsin.

Nümunə:

Layihələrin idarəetmə sistemində layihələrin planlaşdırılması.

2. Kodun kompilyasiyası:

Bir-birinə bağlı olan modulların və ya kod fayllarının kompilyasiya sırasını müəyyənləşdirmək.

Nümunə:

Proqram təminatının build sistemlərində (məsələn, Makefile) daha səmərəli yığılması.

3. Paket menecerlərində bağımlılıqların həlli:

Paketləri elə bir sıraya düzün ki, onların bağımlılıqları əsas paketdən əvvəl quraşdırılsın.

Nümunə:

Paket menecerlərində proqram təminatının quraşdırılmasını (məsələn, npm, pip, apt) sadələşdirmək.

4. Marşrutların optimallaşdırılması:

Gözləmə nöqtələrinin və ya əməliyyatların ardıcıllığını onların bağımlılıqlarını nəzərə alaraq müəyyən etmək.

Nümunə:

Logistika və məhsulun çatdırılma marşrutlarının planlaşdırılması.

Topoloji sıralamanın vaxt və məkan mürəkkəbliyi:

Vaxt mürəkkəbliyi:

Topoloji sıralamanın iki əsas alqoritmi (DFS və Kahn alqoritmi) üçün vaxt mürəkkəbliyi O(V + E)-dir, burada V qrafın zirvələrinin sayı, E isə qrafın qövslərinin sayıdır.

Məkan mürəkkəbliyi:

Hər iki alqoritm üçün məkan mürəkkəbliyi O(V + E)-dir, çünki qrafın saxlanması, əlavə olaraq ziyarət edilmiş zirvələrin və əvvəlki zirvələrin izlənilməsi üçün massivlər tələb olunur.

10.2 Dərinliyə görə axtarış (DFS) ilə reallaşdırma

Topoloji çeşidləməni müxtəlif yollarla yerinə yetirmək olar, onlardan biri də dərinliyə görə axtarışa — DFS əsaslanır. Topoloji çeşidləmə üçün DFS alqoritmi tamamlanmış qovşaqları izləmək üçün stack istifadə edir.

Nümunə reallaşdırma:

def topological_sort_dfs(graph):
    def dfs(vertex, visited, stack):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor, visited, stack)
        stack.append(vertex)
        
    visited = set()
    stack = []
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex, visited, stack)
            
    return stack[::-1]  # Nəticə tərs ardıcıllıqla
    
# İstifadə nümunəsi:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_dfs(graph)
print("Topoloji çeşidləmə:", result)

Nəticə:

Topoloji çeşidləmə: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']

10.3 Realizasiya: Kahn alqoritmi

Digər bir yanaşma Kahn alqoritmi (Kahn's Algorithm) adlanır. Topoloji sıralama üçün Kahn alqoritmi qrafdakı düyünlərin giriş dərəcələri konsepsiyasından istifadə edir.

Realizasiya nümunəsi:

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
            
    queue = deque([u for u in graph if in_degree[u] == 0])
    top_order = []
            
    while queue:
        u = queue.popleft()
        top_order.append(u)
            
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
            
    if len(top_order) == len(in_degree):
        return top_order
    else:
        raise ValueError("Qrafda dövr var")
            
# İstifadə nümunəsi:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_kahn(graph)
print("Topoloji sıralama:", result)

Nəticə:

Topoloji sıralama: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']

1

Sorğu/viktorina

, səviyyə, dərs

Əlçatan deyil

Enine və dərinliyinə uyğun axtarış

Enine və dərinliyinə uyğun axtarış

Açıq