- 概念介绍
- 实现方式
- 邻接矩阵
- 邻接列表
- 代码实现
- 邻接列表实现（高效）
- 顶点的抽象
- 图的抽象
- 创建图像实例
- 代码答疑
- 邻接矩阵实现（自编）
本博客在学习北京大学陈斌老师《数据结构与算法》MOOC课程中总结反思形成。
图的概念据我了解是一种比较容易让人看不懂的概念，在之前调研调研神经网络的发展史时，曾经了解过图卷积神经网络，可以说是目前比较先进的网络结构。它要求输入数据转换为图的结构。
但是简单来说，图在我的印象中往往和数学建模中的最短路问题、哥尼斯堡七桥问题等联系在一起。
那么什么是图呢？
- 图Graph是比树更为一般的结构，也是由节点和边构成
- 图可以用来表示现实世界中很多事物，比如道路交通系统、航班线路、互联网连接、或者是大学中课程的先修次序
它的数学抽象概念和术语总结如下图所示：
实现方式 邻接矩阵- 矩阵的每行和每列都代表图中的顶点
- 如果两个顶点之间有边相连，设定行列值
- 邻接矩阵实现法的优点是简单，可以很容易得到顶点是如何相连
- 但如果图中的边数很少则效率低下（而大多数问题所对应的图都是稀疏的，边远远少于 ∣ V ∣ 2 |V|^2 ∣V∣2这个量级）
# 抽象图的实现：顶点Vertex类
class Vertex:
def __init__(self, key):
self.id = key
self.connnectedTo = {}
def addNeighbor(self, nbr, weight=0):
self.connnectedTo[nbr] = weight
def getConnections(self):
return self.connnectedTo.keys() # .keys (因为是一个字典)
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connnectedTo[nbr]
def __str__(self):
return str(self.id) + 'connectedTo:' + str([x.id for x in self.connnectedTo])
图的抽象
# 图保存了包含所有顶点的主表
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0 # vertices 角的顶点
# 新加顶点
def addVertex(self, key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
# 通过key查找顶点
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
# 不存在的顶点先添加
def addEdge(self, f, t, cost=0):
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
# 调用起始顶点的方法添加邻接边
def getVertices(self):
return self.vertList.keys()
def __contains__(self, n):
return n in self.vertList
def __iter__(self):
return iter(self.vertList.values())
创建图像实例
if __name__ == '__main__':
g = Graph()
for i in range(6):
g.addVertex(i)
print(g.vertList)
g.addEdge(0, 1, 5)
g.addEdge(0, 5, 2)
g.addEdge(1, 2, 4)
g.addEdge(2, 3, 9)
g.addEdge(3, 4, 7)
g.addEdge(3, 5, 3)
g.addEdge(4, 0, 1)
g.addEdge(5, 4, 8)
g.addEdge(5, 2, 1)
for v in g:
for w in v.getConnections():
print("%s,%s" % (v.getId(), w.getId()))
代码答疑
-
代码参考自老师的PPT，实现了图数据的抽象表达
Graph()：创建一个空的图；addVertex(vert)：将顶点vert加入图中；
addEdge(fromVert, toVert)：添加有向边
addEdge(fromVert, toVert, weight)：添加带权的有向边
getVertex(vKey)：查找名称为vKey的顶点
getVertices()：返回图中所有顶点列表
in：按照vert in graph的语句形式，返回顶点是否存在图中True/False -
在class里添加contains(self,x)函数,可判断我们输入的数据是否在Class里，参数x就是我们传入的数据。
-
iter()函数的参数是一个可迭代对象，最终返回一个迭代器。
因为图具备稀疏特性，邻接列表的实现比较高效，因此老师给出了邻接列表的参考代码，本着加深理解和强化应用的原则，下面尝试自己完成图的邻接矩阵实现。
在实现前我查阅了CSDN上部分其他同学的实现方式，各有巧思，罗列在此，以供大家比对。
-
python图的创建（邻接矩阵）
-
Python 邻接矩阵实现无向图、有向图的三种方法，并绘图显示
-
networkx中如何获取图的邻接矩阵
思考后发现不需要实现，因为邻接矩阵的实现就是二维矩阵，所以创建二维矩阵就是对于图的一一种描述。
