gráfalgoritmus
networkx, de az algoritmusok megértése érdekében érdemes manuálisan is implementálni őket.
A gráfokat Pythonban többféleképpen reprezentálhatjuk:
graph = {
'A': ,
'B': ,
'C': ,
'D': ,
'E': ,
'F':
}
graph_matrix = [
,
,
,
,
,
]
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.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Példa
graph = {
'A': ,
'B': ,
'C': ,
'D': ,
'E': ,
'F':
}
dfs(graph, 'A')
A B D E F C
A szélességi keresés rétegenként járja be a gráfot.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque()
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(neighbor for neighbor in graph if neighbor not in visited)
# Példa
bfs(graph, 'A')
A B C D E F
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.
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances = 0
priority_queue =
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances:
continue
for neighbor, weight in graph.items():
distance = current_distance + weight
if distance < distances:
distances = 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'))
{'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 5}
A Kruskal algoritmus minimális költségű feszítőfát épít súlyozott gráfokhoz.
def kruskal(edges, num_nodes):
parent = {i: i for i in range(num_nodes)}
def find(node):
if parent != node:
parent = find(parent)
return parent
def union(node1, node2):
root1 = find(node1)
root2 = find(node2)
if root1 != root2:
parent = root1
mst =
edges.sort(key=lambda x: x) # 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))
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.
def topological_sort(graph):
visited = set()
stack =
def dfs(node):
if node not in visited:
visited.add(node)
for neighbor in graph:
dfs(neighbor)
stack.append(node)
for node in graph:
dfs(node)
return stack # Reverse the stack for topological order
# Példa
dag = {
'A': ,
'B': ,
'C': ,
'D':
}
print(topological_sort(dag))
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.