Sunday, 26 February 2023
Algoritma Graf, like a Depth-First Search, Breadth-First Search, Dijkstra
- Depth-First Search (DFS)
Here's an example implementation of DFS in Python:
def DFS(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
DFS(graph, next, visited)
return visited
2. Breadth-First Search (BFS)
BFS is another graph traversal algorithm that explores all the vertices at the present depth before moving on to the vertices at the next depth level. BFS can be used to solve problems such as finding the shortest path between two nodes in an unweighted graph and testing if a graph is bipartite.
Here's an example implementation of BFS in Python:
def BFS(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
3. Dijkstra's Algorithm
Dijkstra's Algorithm is used to find the shortest path between nodes in a weighted graph. It does this by assigning a tentative distance to every node, then iteratively choosing the node with the shortest tentative distance and updating its neighbors' tentative distances. Dijkstra's Algorithm can be used to solve problems such as finding the shortest path in a road network or a flight network.
Here's an example implementation of Dijkstra's Algorithm in Python:
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
(cost, current) = heapq.heappop(queue)
if cost > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = cost + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
4. Kruskal's Algorithm
Kruskal's Algorithm is used to find the minimum spanning tree (MST) of a weighted graph. The minimum spanning tree is a subset of edges that connect all vertices in the graph while minimizing the total weight of the edges. Kruskal's Algorithm starts with the edges with the lowest weights and adds them to the MST as long as they don't form a cycle.
Here's an example implementation of Kruskal's Algorithm in Python:
def kruskal(graph):
parent = {}
rank = {}
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:
return
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
for node in graph:
parent[node] = node
rank[node] = 0
mst = set()
edges = list(graph.edges)
edges.sort()
for edge in edges:
weight, node1, node2 = edge
if find(node1) != find(node2):
union(node1, node2)
mst.add(edge)
return mst
5. Bellman-Ford Algorithm
The Bellman-Ford Algorithm is used to find the shortest path between nodes in a weighted graph with negative edge weights. It does this by relaxing the edges repeatedly, meaning it looks for a shorter path between two nodes by using an intermediate node. The algorithm repeats this process for all nodes in the graph.
Here's an example implementation of the Bellman-Ford Algorithm in Python:
def bellman_ford(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
raise ValueError("Negative weight cycle detected")
return distances