5 Grpah Algorithms
Contents
5 Grpah Algorithms¶
5.1 Graph Data Structure¶
num_nodes = 5
edges = [(0,1),(0,4),(1,2),(1,3),(1,4),(2,3),(3,4)]
num_nodes, len(edges)
(5, 7)
5.1.1 Adjacency List 相邻nodes¶
实际上就是将edges以list形式存下来，用于后续的使用
Question: Create a class to represent a graph as an adjacency list in Python
class Graph:
def __init__(self, num_nodes, edges):
self.num_nodes = num_nodes
self.adj_list = [[] for _ in range(self.num_nodes)]
for n1,n2 in edges:
self.adj_list[n1].append(n2)
self.adj_list[n2].append(n1)
def __repr__(self):
return "\n".join(["{}: {}\n".format(n, neighbour) for (n, neighbour) in enumerate(self.adj_list)])
def __str__(self):
return self.__repr__()
graph1 = Graph(num_nodes, edges)
graph1
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]
Question:
Write a function to add an edge to a graph represented as an adjacency list.
Write a function to remove an edge from a graph represented as a adjacency list.
def add_edge(graph, new_edge):
n1,n2 = new_edge[0], new_edge[1]
graph.adj_list[n1].append(n2)
graph.adj_list[n2].append(n1)
return graph
def remove_edge(graph, edge):
n1,n2 = edge[0], edge[1]
graph.adj_list[n1].remove(n2)
graph.adj_list[n2].remove(n1)
return graph
add_edge(graph1, (0,2))
0: [1, 4, 2]
1: [0, 2, 3, 4]
2: [1, 3, 0]
3: [1, 2, 4]
4: [0, 1, 3]
remove_edge(graph1, (0,2))
0: [1, 4]
1: [0, 2, 3, 4]
2: [1, 3]
3: [1, 2, 4]
4: [0, 1, 3]
5.1.2 Adjacency Matrix¶
Question: Represent a graph as an adjacency matrix in Python
class Graph:
def __init__(self, num_nodes, edges):
self.num_nodes = num_nodes
self.adj_list = [[] for _ in range(self.num_nodes)]
for n1,n2 in edges:
self.adj_list[n1].append(n2)
self.adj_list[n2].append(n1)
self.adj_matrix = [[0]*num_nodes for _ in range(self.num_nodes)]
for n1,n2 in edges:
self.adj_matrix[n1][n2] = 1
self.adj_matrix[n2][n1] = 1
def __repr__(self):
return "\n".join(["{}: {}\n".format(n, neighbour) for (n, neighbour) in enumerate(self.adj_list)])
def __str__(self):
return self.__repr__()
graph1 = Graph(num_nodes, edges)
graph1.adj_matrix
[[0, 1, 0, 0, 1],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]]
5.1.3 Weighted/Directed Graph¶
Weighted Graph:
# Graph with weights
num_nodes2 = 9
edges2 = [(0, 1, 3), (0, 3, 2), (0, 8, 4), (1, 7, 4), (2, 7, 2), (2, 3, 6),
(2, 5, 1), (3, 4, 1), (4, 8, 8), (5, 6, 8)]
num_nodes2, len(edges2)
(9, 10)
Directed Graph:
num_nodes3 = 5
edges3 = [(0, 1), (1, 2), (2, 3), (2, 4), (4, 2), (3, 0)]
num_nodes3, len(edges3)
(5, 6)
class Graph:
def __init__(self, num_nodes, edges, weighted = False, directed = False):
self.num_nodes = num_nodes
self.weighted = weighted
self.directed = directed
self.adj_list = [[] for _ in range(self.num_nodes)]
if not self.weighted:
for n1,n2 in edges:
self.adj_list[n1].append(n2)
if not self.directed:
self.adj_list[n2].append(n1)
self.adj_matrix = [[0]*num_nodes for _ in range(self.num_nodes)]
for n1,n2 in edges:
self.adj_matrix[n1][n2] = 1
if not self.directed:
self.adj_matrix[n2][n1] = 1
else:
self.weights = [[] for _ in range(self.num_nodes)]
for n1,n2,weight in edges:
self.adj_list[n1].append(n2)
self.weights[n1].append(weight)
if not self.directed:
self.adj_list[n2].append(n1)
self.weights[n2].append(weight)
def __repr__(self):
result = ""
if self.weighted:
for i, (nodes, weights) in enumerate(zip(self.adj_list, self.weights)):
result += "{}: {}\n".format(i, list(zip(nodes, weights)))
else:
for i, nodes in enumerate(self.adj_list):
result += "{}: {}\n".format(i, nodes)
return result
def __str__(self):
return self.__repr__()
graph2 = Graph(num_nodes2, edges2, weighted = True)
graph2
0: [(1, 3), (3, 2), (8, 4)]
1: [(0, 3), (7, 4)]
2: [(7, 2), (3, 6), (5, 1)]
3: [(0, 2), (2, 6), (4, 1)]
4: [(3, 1), (8, 8)]
5: [(2, 1), (6, 8)]
6: [(5, 8)]
7: [(1, 4), (2, 2)]
8: [(0, 4), (4, 8)]
graph3 = Graph(num_nodes3, edges3, directed = True)
graph3
0: [1]
1: [2]
2: [3, 4]
3: [0]
4: [2]
5.2 Graph Traversal¶
5.2.1 Breadth-first search 广度优先搜索¶
A real-world graph:
Breadth-fist search tree (starting from Frankfurt):
BFS pseudocode (Wikipedia):
1 procedure BFS(G, root) is
2 let Q be a queue
3 label root as discovered
4 Q.enqueue(root)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 Q.enqueue(w)
Question: Implement breadth-first search given a source node in a graph using Python.
def bfs(graph, root):
queue = []
visited = [False] * graph.num_nodes
distance = [None] * graph.num_nodes
parent = [None] * graph.num_nodes
visited[root] = True
distance[root] = 0
queue.append(root)
idx = 0
while idx < len(queue):
current = queue[idx]
for node in graph.adj_list[current]:
if not visited[node]:
queue.append(node)
visited[node] = True
distance[node] = 1+distance[current]
parent[node] = current
idx += 1
return queue, distance, parent
bfs(graph1, 0)
([0, 1, 4, 2, 3], [0, 1, 2, 2, 1], [None, 0, 1, 1, 0])
5.2.2 Depth-first Search 深度优先搜索¶
Depth-first search¶
DFS pseudocode (Wikipedia):
procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Question: Implement depth first search from a given node in a graph using Python.
def dfs(graph, root):
stack = [root]
visited = [False] * graph.num_nodes
result = []
while len(stack) > 0:
current = stack.pop()
if not visited[current]:
visited[current] = True
result.append(current)
for node in graph.adj_list[current]:
if not visited[node]:
stack.append(node)
return result
dfs(graph1,0)
[0, 4, 3, 2, 1]
5.2.3 Comparision and Complexity¶
Time complexity are both \(O(n+e)\), where \(n\) is the number of node and \(e\) is the number of edges.
5.3 Shortest Paths¶
Question: Write a function to find the length of the shortest path between two nodes in a weighted directed graph.
Dijkstra’s algorithm (Wikipedia):
Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.[16]
For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new “current node”, and go back to step 3.
def update_distances(graph, current, distance, visited):
neighbours = graph.adj_list[current]
weights = graph.weights[current]
for i, neighbour in enumerate(neighbours):
if not visited[neighbour]:
distance[neighbour] = min(distance[neighbour],
weights[i] + distance[current])
def pick_next_node(visited, distance):
min_distance = float("inf")
min_node = None
for node,distance in enumerate(distance):
if not visited[node] and distance < min_distance:
min_distance = distance
min_node = node
return min_node
def shortest_path(graph, root, dest):
visited = [False] * graph.num_nodes
distance = [float('infinity')] * graph.num_nodes
distance[root] = 0
queue = [root]
idx = 0
while not visited[dest] and idx < len(graph.adj_list):
current = queue[idx]
update_distances(graph, current, distance, visited)
visited[current] = True
next_node = pick_next_node(visited, distance)
if next_node is not None:
queue.append(next_node)
idx += 1
return distance[dest]
num_nodes = 6
edges = [(0, 1, 4), (0, 2, 2), (1, 2, 5), (1, 3, 10), (2, 4, 3), (4, 3, 4), (3, 5, 11)]
graph = Graph(num_nodes, edges, weighted = True, directed = True)
graph
0: [(1, 4), (2, 2)]
1: [(2, 5), (3, 10)]
2: [(4, 3)]
3: [(5, 11)]
4: [(3, 4)]
5: []
shortest_path(graph,0,5)
20