Wikiszótár

gráfalgoritmus

Magyar

Kiejtés

  • IPA: [ ˈɡraːfɒlɡoritmuʃ]

Főnév

gráfalgoritmus

  1. (matematika, algoritmusok) A gráfalgoritmusok széles körben használhatók különböző problémák megoldására, például útvonalkeresésre, hálózati elemzésre vagy optimális megoldások keresésére. Pythonban számos könyvtár és eszköz segíti a gráfok kezelését, mint például a networkx, de az algoritmusok megértése érdekében érdemes manuálisan is implementálni őket.


1. Gráf reprezentációk

A gráfokat Pythonban többféleképpen reprezentálhatjuk:

Szomszédsági lista:

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

Szomszédsági mátrix:

graph_matrix = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 1],
    [0, 0, 1, 0, 1, 0]
]

2. Mélységi keresés (DFS)

A mélységi keresés egy gráf bejárási algoritmus, amely rekurzív módon, egy irányba haladva járja be a gráfot.

Implementáció:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Példa
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

Kimenet:

A B D E F C

3. Szélességi keresés (BFS)

A szélességi keresés rétegenként járja be a gráfot.

Implementáció:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

# Példa
bfs(graph, 'A')

Kimenet:

A B C D E F

4. Dijkstra algoritmus

A Dijkstra algoritmus megtalálja a legrövidebb utat egy adott csúcsból az összes többi csúcsba egy súlyozott gráfban.

Implementáció:

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Példa gráf
weighted_graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}

print(dijkstra(weighted_graph, 'A'))

Kimenet:

{'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 5}

5. Minimális feszítőfa (Kruskal algoritmus)

A Kruskal algoritmus minimális költségű feszítőfát épít súlyozott gráfokhoz.

Implementáció:

def kruskal(edges, num_nodes):
    parent = {i: i for i in range(num_nodes)}
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    
    mst = []
    edges.sort(key=lambda x: x[2])  # Sort edges by weight
    
    for node1, node2, weight in edges:
        if find(node1) != find(node2):
            union(node1, node2)
            mst.append((node1, node2, weight))
    
    return mst

# Példa élek
edges = [
    (0, 1, 1), (0, 2, 4), (1, 2, 2),
    (1, 3, 6), (2, 3, 3)
]

print(kruskal(edges, 4))

Kimenet:

[(0, 1, 1), (1, 2, 2), (2, 3, 3)]

6. Topologikus sorrend (DAG)

Topologikus sorrend irányított, körmentes gráf (DAG) csúcsainak olyan sorrendje, amelyben minden él a sorrendben előrébb lévő csúcsból a későbbi csúcsba mutat.

Implementáció:

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                dfs(neighbor)
            stack.append(node)
    
    for node in graph:
        dfs(node)
    
    return stack[::-1]  # Reverse the stack for topological order

# Példa
dag = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(dag))

Kimenet:

['A', 'C', 'B', 'D']

Következtetés

Ezek az implementációk a gráfalgoritmusok alapvető működését mutatják be Pythonban. Bonyolultabb projektekhez érdemes olyan könyvtárakat használni, mint a networkx, de a manuális implementáció segít megérteni az algoritmusok mögötti elveket.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=gráfalgoritmus&oldid=3480304”