graph traversal

graph traversal (tsz. graph traversals)

1. (informatika, mesterséges intelligencia) gráfbejárás

A graph traversal (gráf bejárás) az a folyamat, amely során egy gráf csúcsait és éleit módszeresen végigjárjuk, egy vagy több kiindulópontból. A gráfbejárás központi technika a számítástudományban, különösen gráfalgoritmusok, hálózatelemzés, útvonal-keresés, és komponens-felderítés során.

Egy gráf formálisan:

$${\displaystyle G=(V,E)}$$

ahol:

• ${\textstyle V}$: csúcsok (vertices)
• ${\textstyle E}$: élek (edges), lehetnek irányítottak vagy irányítatlanok

A DFS a lehető legmélyebbre halad a gráfban, mielőtt visszalépne.

• Használható veremmel (stack) vagy rekurzívan
• Jó: komponensek keresése, topologikus sorrend, ciklusdetektálás

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

A BFS minden szintet teljesen bejár, mielőtt mélyebbre lépne.

• Használ: sor (queue)
• Jó: legrövidebb út keresése nem súlyozott gráfban

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque()
    while queue:
        node = queue.popleft()
        for neighbor in graph:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

Adjunk meg egy gráfot szótárként:

graph = {
    'A': ,
    'B': ,
    'C': ,
    'D': ,
    'E': ,
    'F': 
}

Mindkét módszer időigénye:

$${\displaystyle O(V+E)}$$

ahol:

• ${\textstyle V}$: csúcsok száma
• ${\textstyle E}$: élek száma

• Útvonal-keresés: BFS → legrövidebb út nem súlyozott gráfban
• Komponens-felbontás: DFS → összefüggő részek keresése
• Ciklusdetektálás: DFS → ha látunk „visszautat”
• Topologikus sorrend: DFS-alapú feldolgozás
• Híd / artikulációs pont keresés: DFS mélység segítségével

Fogalom	Leírás
DFS	Mélységi bejárás, verem/alapú
BFS	Szélességi bejárás, sor/alapú
Irányított	Él irányát figyelembe vesszük
Ciklus	DFS/BFS-sel detektálható
Komplexitás	${\textstyle O(V+E)}$
Alkalmazások	Ütemezés, hálózatok, játékok, mesterséges intelligencia

• graph traversal - Szótár.net (en-hu)
• graph traversal - Sztaki (en-hu)
• graph traversal - Merriam–Webster
• graph traversal - Cambridge
• graph traversal - WordNet
• graph traversal - Яндекс (en-ru)
• graph traversal - Google (en-hu)
• graph traversal - Wikidata
• graph traversal - Wikipédia (angol)