邻接矩阵表示法，用两个数组表示，一个一维数组和一个二维数组。
一维数组存储节点信息，二维数组存储节点之间的关系。
#图的邻接矩阵实现
class Graph:
def __init__(self, vertex):
self.vertex = vertex
self.graph = [[0]*vertex for i in range(vertex)]
def insert(self, u, v):
self.graph[u - 1][v - 1] = 1 #对存在连接关系的两个点，在矩阵里置1代表存在连接关系，没有连接关系则置0
self.graph[v - 1][u - 1] = 1
def show(self): #展示图
for i in self.graph:
for j in i:
print(j, end=\' \')
print(\' \')
if __name__ == "__main__":
graph = Graph(5)
graph.insert(1, 4)
graph.insert(4, 2)
graph.insert(4, 5)
graph.insert(2, 5)
graph.insert(5, 3)
graph.show()
#输出
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1
1 1 0 0 1
0 1 1 1 0
图的遍历问题
通常图的遍历有两种：深度优先搜索和广度优先搜索。
深度优先搜索
深度优先搜索(DFS) 是树的先根遍历的推广，它的基本思想是：
从图 G 的某个顶点 v0 出发，访问 v0，然后选择一个与 v0 相邻且没被访问过的顶点 vi 访问，再从 vi 出发选择一个与 vi 相邻且未被访问的顶点 vj 进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点 w，从 w 出发按同样的方法向前遍历，直到图中所有顶点都被访问。
#深度优先遍历
def dfs(graph, start):
explored, stack = [], [start] #explored：已经遍历的节点列表，stack:寻找待遍历的节点栈
explored.append(start)
while stack:
v = stack.pop()
for w in graph[v]:
if w not in explored:
explored.append(w)
stack.append(w)
return explored
G = {\'0\':[\'1\'],
\'1\':[\'3\'],
\'2\':[\'1\'],
\'3\':[\'2\',\'4\'],
\'4\':[\'5\'],
\'5\':[\'7\'],
\'6\':[\'4\'],
\'7\':[\'6\']
}
print(dfs(G, \'0\'))
#输出
[\'0\', \'1\', \'3\', \'2\', \'4\', \'5\', \'7\', \'6\']
图的最短路径问题
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。给定一个图，和一个源顶点 src，找到从 src 到其它所有所有顶点的最短路径，图中可能含有负权值的边。在这里我们介绍两种常见的求解最短路径问题的算法。
Dijkstra 的算法是一个贪婪算法，时间复杂度是 O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用，Bellman-Ford 适合这样的图。在网络路由中，该算法会被用作距离向量路由算法。
Bellman-Ford 也比迪杰斯特拉算法更简单和同时也适用于分布式系统。但 Bellman-Ford 的时间复杂度是 O(VE)，这要比迪杰斯特拉算法慢。（V 为顶点的个数，E 为边的个数）。
Dijkstra 算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块，Dijkstra 算法不能处理包含负边的图！
#Dijkstra 算法
import heapq
def dijkstra(graph, start, end):
heap = [(0, start)] #cost from start node, end node
visited = []
while heap:
(cost, u) = heapq.heappop(heap)
if u in visited:
continue
visited.append(u)
if u == end:
return cost
for v, c in G[u]:
if v in visited:
continue
next = cost +c
heapq.heappush(heap, (next, v))
return (-1, -1)
G = {\'0\':[[\'1\', 2], [\'2\', 5]],
\'1\':[[\'0\', 2], [\'3\', 3], [\'4\', 1]],
\'2\':[[\'0\', 5], [\'5\', 3]],
\'3\':[[\'1\', 3]],
\'4\':[[\'1\', 1], [\'5\', 3]],
\'5\':[[\'2\', 3], [\'4\', 3]]
}
shortDistance = dijkstra(G, \'4\', \'2\')
print(shortDistance)
并查集
并查集是一种数据结构，用于处理对 N 个元素的集合划分和判断是否属于同集合的问题。让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
注：定义来自百度百科。并查集的主要性质
用集合中的某个元素来代表这个集合，该元素称为集合的代表元。一个集合内的所有元素组织成以代表元为根的树形结构。对于每一个元素 parent[x]指向 x 在树形结构上的父亲节点。如果 x 是根节点，则令 parent[x] = x。对于查找操作，假设需要确定 x 所在的的集合，也就是确定集合的代表元。可以沿着 parent[x]不断在树形结构中向上移动，直到到达根节点。判断两个元素是否属于同一集合，只需要看他们的代表元是否相同即可。
并查集的应用
1、维护无向图的连通性。支持判断两个点是否在同一连通块内，和判断增加一条边是否会产生环。
2、用在求解最小生成树的 Kruskal 算法里。
并查集的功能实现
#创建一个 union_find 的类,并初始化。初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小。初始化的时候，将节点的父节点设为自身，size 设为 1
class union_find(object):
def __init__(self, data_list):
self.father_dict = {}
self.size_dict = {}
for node in data_list:
self.father_dict[node] = node
self.size_dict[node] = 1
#用递归的方式查找父节点
def find(self, node):
father = self.father_dict[node]
if(node != father): #递归查找父节点
father = self.find(father)
self.father_dict[node] = father #在查找父节点的时候，顺便把当前节点移动到父节点上面这个操作算是一个优化
return father
#查看两个节点是不是在一个集合里面。通过调用 find 函数，判断两个节点是否是同一个父节点，如果是则判断两个节点属于一个集合。
def is_same_set(self, node_a, node_b):
return self.find(node_a) == self.find(node_b)
#将两个集合合并在一起
def union(self, node_a, node_b):
if node_a is None or node_b is None: #对合并的两个节点做初步判断，判断是否为空
return
a_head = self.find(node_a) #分别查找两个节点的父节点
b_head = self.find(node_b)
if(a_head != b_head): #当两个节点的父节点不一样时，才能做合并操作
a_set_size = self.size_dict[a_head]
b_set_size = self.size_dict[b_head]
if(a_set_size >= b_set_size):
self.father_dict[b_head] = a_head
self.size_dict[a_head] = a_set_size +b_set_size
else:
self.father_dict[a_head] = b_head
self.size_dict[b_head] = a_set_size +b_set_size
if __name__ == "__main__":
a = [1,2,3,4,5]
union_find = union_find(a)
union_find.union(1,2)
union_find.union(3,5)
union_find.union(3,1)
print(union_find.is_same_set(2,5))
#输出
True
