目录
概述
数据结构分为两类，一类是具有递归结构的数据结构，也就是可以给出一个递归定义的数据结构，一类是非递归结构的数据结构。像链表、数组、广义表、树、FA等都是具有递归结构的数据结构，都可以给出一个递归的定义，比如说树，它的递归定义如下：
basis：空树是一棵树，一个结点的树是一棵树
induction：各个以树的根结点的子结点为根结点的结构是树
关于树的讨论已经进行了很多，这里不再赘述，这篇文章讲一下非递归结构的数据结构：图。
图的定义
图不是一个递归结构的数据结构，也就没法给出一个递归定义，图的定义可以用一个三元组来表示：顶点集、弧/边集、操作集，在图的图形表示里，顶点用一个小圆圈表示，弧用一条有向边来表示，若图中存在一条顶点v到顶点w的弧，由v引一条指向w的弧来表示，v为弧的弧尾，w为弧的弧头。图分为有向图和无向图，无向图是有向图的一种特例，它是一种具有对称性质的有向图，也就是如果从顶点v到顶点w存在一条弧，那么从顶点w到顶点v也必存在一条弧，也就是顶v和顶点w之间存在两条有向边，为了简化表示，用一条连接顶点v、w的无向边表示。图的常见操作有求顶点的所有弧/边，求顶点的度，求图的联通子图，求联通图的最小生成树，对联通图进行遍历，求两个顶点之间的最短路径等。
图的存储结构
1）邻接矩阵
顶点集用一个list表示
弧集用一个临接矩阵表示
matrix[i][j]取0表示顶点i到顶点j不存在一条弧，取1表示顶点i到顶点j存在一条弧
如果是无向图，可以采用上三角/下三角矩阵进行压缩存储，可以节省一半空间
class Vertex:
def __init__(self, data = None):
self.data = data
class Graph:
def __init__(self, vertexs):
self.vertexs = [i for i in vertexs]
self.matrix = [[0] * len(vertexs) for i in range(len(vertexs))]
def set_arc(self, i, j):
self.matrix[i][j] = 1
def unset_arc(self, i, j):
self.matrix[i][j] = 0
def get_in_arcs(self, i):
return [(j, i) for j, k in enumerate(self.matrix) if k[i]]
def get_out_arcs(self, i):
return [(i, j) for j, k in enumerate(self.matrix[i]) if k]
def __str__(self):
graphmatrix = ""
for i in self.matrix:
graphmatrix += " ".join([str(j) for j in i]) + '\n'
return graphmatrix
g1 = Graph([Vertex() for i in range(4)])
g1.set_arc(0, 1)
g1.set_arc(0, 2)
g1.set_arc(2, 3)
g1.set_arc(3, 0)
print(g1)
print(g1.get_in_arcs(0))
print(g1.get_in_arcs(1))
print(g1.get_in_arcs(2))
print(g1.get_in_arcs(3))
print(g1.get_out_arcs(0))
print(g1.get_out_arcs(1))
print(g1.get_out_arcs(2))
print(g1.get_out_arcs(3))
2）邻接表
顶点集存储在一个list中
每个顶点维护一个list，存储它所有的出弧
为了方便求顶点的所有入弧，顶点可以再维护一个list，以存储它所有的入弧
邻接表表示法实际用一个邻接点表示一条弧
临接表的存储密度比临接矩阵大，更节省空间，但要判断任意两个顶点之间是否有弧/边不如临接矩阵效率高
class Vertex:
def __init__(self, data = None):
self.data = data
self.in_arcs = []
self.out_arcs = []
def set_in_arc(self, v):
self.in_arcs.append(v)
def set_out_arc(self, v):
self.out_arcs.append(v)
class Graph:
def __init__(self, vertexs = None):
self.vertexs = [i for i in vertexs] if vertexs else []
def insert_vertex(self, vertex):
self.vertexs.append(vertex)
def set_in_arc(self, i, j):
vertex = self.vertexs[i]
vertex.set_in_arc(j)
def set_out_arc(self, i, j):
vertex = self.vertexs[i]
vertex.set_out_arc(j)
def set_in_arcs(self):
for i, v in enumerate(self.vertexs):
for j in v.out_arcs:
self.vertexs[j].set_in_arc(i)
def get_in_arcs(self, i):
return [(j, i) for j in self.vertexs[i].in_arcs]
def get_out_arcs(self, i):
return [(i, j) for j in self.vertexs[i].out_arcs]
g = Graph(Vertex() for i in range(4))
g.set_out_arc(0, 1)
g.set_out_arc(0, 2)
g.set_out_arc(2, 3)
g.set_out_arc(3, 0)
g.set_in_arcs()
print(g.get_in_arcs(0))
print(g.get_in_arcs(1))
print(g.get_in_arcs(2))
print(g.get_in_arcs(3))
print(g.get_out_arcs(0))
print(g.get_out_arcs(1))
print(g.get_out_arcs(2))
print(g.get_out_arcs(3))
3）十字链表
临接表中给一条弧创建了两个弧结点，因为一条弧，它既作为弧尾顶点的出弧，又作为弧头顶点的入弧，为了避免这种重复，可以给弧结点以更多的信息，指明弧的弧头和弧尾，并把它同时加入弧头的入弧list和弧尾的出弧list中。
class Vertex:
def __init__(self, data = None):
self.data = data
self.in_arcs = []
self.out_arcs = []
def set_in_arc(self, arc):
self.in_arcs.append(arc)
def set_out_arc(self, arc):
self.out_arcs.append(arc)
class Arc:
def __init__(self, tail, head, data = None):
self.tail = tail
self.head = head
self.data = data
class Graph:
def __init__(self, vertexs = None):
self.vertexs = [i for i in vertexs] if vertexs else []
def insert_vertex(self, vertex):
self.vertexs.append(vertex)
def set_arc(self, arc):
self.vertexs[arc.tail].set_out_arc(arc)
self.vertexs[arc.head].set_in_arc(arc)
def get_in_arcs(self, i):
return [(j.tail, i) for j in self.vertexs[i].in_arcs]
def get_out_arcs(self, i):
return [(i, j.head) for j in self.vertexs[i].out_arcs]
g = Graph(Vertex() for i in range(4))
g.set_arc(Arc(0, 1))
g.set_arc(Arc(0, 2))
g.set_arc(Arc(2, 3))
g.set_arc(Arc(3, 0))
print(g.get_in_arcs(0))
print(g.get_in_arcs(1))
print(g.get_in_arcs(2))
print(g.get_in_arcs(3))
print(g.get_out_arcs(0))
print(g.get_out_arcs(1))
print(g.get_out_arcs(2))
print(g.get_out_arcs(3))
4）邻接多重表
上面的各种存储表示都是关于有向图的，当然对他们稍加改造/约束就可以得到一个无向图的表示。邻接多重表是对十字链表表示做了一点修改得来的，用于表示无向图。无向图的边，它没有头、尾的概念，只需指明它连接的两个顶点，并把它加入到两个顶点的边集中即可。
class Vertex:
def __init__(self, data = None):
self.data = data
self.edges = []
def set_edge(self, edge):
self.edges.append(edge)
class Edge:
def __init__(self, one, other, data = None):
self.one = one
self.other = other
self.data = data
class Graph:
def __init__(self, vertexs = None):
self.vertexs = [i for i in vertexs] if vertexs else []
def insert_vertex(self, vertex):
self.vertexs.append(vertex)
def set_edge(self, edge):
self.vertexs[edge.one].set_edge(edge)
if edge.one != edge.other:
self.vertexs[edge.other].set_edge(edge)
def get_edges(self, i):
edges = []
for j in self.vertexs[i].edges:
if j.one == i:
edges.append((i, j.other))
else:
edges.append((i, j.one))
return edges
g = Graph(Vertex() for i in range(4))
g.set_edge(Edge(0, 1))
g.set_edge(Edge(0, 2))
g.set_edge(Edge(2, 3))
g.set_edge(Edge(3, 0))
print(g.get_edges(0))
print(g.get_edges(1))
print(g.get_edges(2))
print(g.get_edges(3))
