数据结构与算法——图形结构（七）
数据结构——图
1、图的基本概念
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。2、图的数据表示法
2.1 邻接矩阵表示法
假设一个图A有n个顶点，我们以n*n的二维矩阵列来表示它，这个二维矩阵就是该图的邻接矩阵，此矩阵的定义如下：对于一个图G=(V,E)，假设有n个顶点，n>=1，则可以将n个顶点的图使用一个n*n的二维矩阵来表示，其中A(i,j)=1，则表示图中有一条边(Vi,Vj)存在，反之，A(i,j)=0，则不存在(Vi,Vj)。
相关特性说明如下：
（1）对无向图而言，邻接矩阵一定是对称的，而对角线一定为0。有向图则不一定如此。
（2）在无向图中，任意结点 i 的度数就是第 i 行所有元素的和。在有向图中，结点 i 的出度就是第 i 行所有元素之和；结点 j 的入度就是第 j 列所有元素之和。
（3）用邻接矩阵法表示图共需要 n^2 个单位空间，由于无向图的邻接矩阵具有对称关系的，扣除对角线全部为 0 外，仅需要存储上三角形数据即可，因此仅需要n(n-1)/2。
接下来，我们看一个实际的例子，以邻接矩阵来表示无向图，无向图如下图所示：
该无向图的邻接矩阵表示为：
我们接下来使用程序来创建邻接矩阵表示这个无向图，该程序使用Python2实现：
1 import numpy as np 2 3 #返回某个顶点在顶点列表中的位置索引 4 def find_index(node, node_list): 5 for i in range(len(node_list)): 6 if node == node_list[i]: 7 return i 8 return -1 9 10 #无向图的输入，采用二维数组 11 data = [[1, 2], [1, 5], [2, 3], [2, 4], [3, 4], [3, 5],[4, 5]] 12 #顶点列表 13 vertex_list = [1, 2, 3, 4, 5] 14 #创建一个邻接矩阵 15 Adj_matrix = np.zeros((5, 5), dtype=int) 16 #开始遍历图数据，生成邻接矩阵。 17 for i in range(len(data)): 18 temp1 = find_index(data[i][0], vertex_list) #找到顶点在顶点列表中的索引 19 temp2 = find_index(data[i][1], vertex_list) 20 Adj_matrix[temp1][temp2] = 1 #将有边的点出填入1 21 Adj_matrix[temp2][temp1] = 1 # 将有边的点出填入1 22 #输出邻接矩阵 23 for i in range(len(Adj_matrix)): 24 for j in range(len(Adj_matrix[0])): 25 print Adj_matrix[i][j], #python2的用法，在后面加“，”表示不换行。 26 print ""
运行的结果如下：
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
下面我们再看一个有向图的例子，以邻接矩阵来表示有向图，有向图如下图所示：
该有向图的邻接矩阵表示为：
我们接下来使用程序来创建邻接矩阵表示这个有向图，该程序使用Python2实现：
1 import numpy as np 2 3 #返回某个顶点在顶点列表中的位置索引 4 def find_index(node, node_list): 5 for i in range(len(node_list)): 6 if node == node_list[i]: 7 return i 8 return -1 9 10 #有向图的输入，采用二维数组 11 data = [[1, 2], [2, 1], [2, 3], [2, 4], [4, 3], [4, 1]] 12 #顶点列表 13 vertex_list = [1, 2, 3, 4] 14 #创建一个邻接矩阵 15 Adj_matrix = np.zeros((5, 5), dtype=int) 16 #开始遍历数据，生成邻接矩阵。 17 for i in range(len(data)): 18 temp1 = find_index(data[i][0], vertex_list) #找到顶点在顶点列表中的索引 19 temp2 = find_index(data[i][1], vertex_list) 20 Adj_matrix[temp1][temp2] = 1 #将有边的点出填入1 21 #输出邻接矩阵 22 for i in range(len(Adj_matrix)): 23 for j in range(len(Adj_matrix[0])): 24 print Adj_matrix[i][j], #python2的用法，在后面加“，”表示不换行。 25 print ""
运行的结果如下：
0 1 0 0 0
1 0 1 1 0
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0
2.2 邻接表法
前面所介绍的邻接矩阵法，优点是凭借着矩阵的运算又许多特别的应用。要在图中加入新边时，这个表示法的插入和删除相当简易。不过还要考虑到稀疏矩阵空间的浪费问题，另外，如果要计算所有顶点的度，其时间复杂度为O(n^2)。
因此可以考虑更有效的方法，就是邻接表法（Adjacency List）。这种表示法就是将一个n行的邻接矩阵表示成n个链表，这种做法和邻接矩阵相比较节省空间，如计算所有顶点的度时，其时间复杂度为O(n+e)，缺点是：例如有新边加入图中或者从图中删除边时，就要修改相关的链接，较为麻烦费时。
首先，将图的n个顶点作为n个链表头，每个链表中的结点表示它们和链表头结点之间有边相连。每个结点的数据结构如下：
1 class list_node(object): #定义一个结点类 2 def __init__(self): #构造函数 3 self.data = 0 #结点的数据域 4 self.next = None #结点的指针域
在无向图中，因为对称关系，若有n个顶点、m个边，则形成n个链表头，2m个结点。若在有向图中，则有n个链表头以及m个结点，因此在邻接表中，求所有顶点的度所需的时间复杂度为O(n+m)。
3、图的遍历
4、生成树
5、最短路径问题
