图是一种 多对多 的存储结构，即一个节点可能会有多个连接的节点, 为了展现多对多关系, 产生了一种 顺序存储 与链式存储结合的方式, 由 顺序存储 来存放每个节点, 使用 链式存储 来体现每个 节点 之间的关系, 这两个方式就是 顶点表(数组)和邻接表(单链表). 图的结构中有若干个节点 也叫做 顶点, 因此叫 顶点表
顶点表
用途: 存放所有顶点. 使用 数组 存放, 将所有顶点，依次存入数组中 (也可直接从下标1开始存)
-
顶点的数据结构
- 顶点数据(option): 这个可以不需要, 也可以直接用顶点在
数组中下标来代替 - 顶点域(visited): 整型，初始值为0，当节点被访问过后，标记修改为1
- 邻接表节点(first_adj): 指向第一个邻接表节点，若无邻接节点，则值为空
- 顶点数据(option): 这个可以不需要, 也可以直接用顶点在
邻接表
在顶点表 中, 每个顶点 中, 都有一个 邻接表节点 (first_adj), 这就是一条单链表, 其中每个节点中存储着与 顶点 相连 顶点 的信息, 因此, 通过顶点中的单链表 可以访问到与之相连的顶点,单链表 中有 几个节点, 就代表着 顶点 有 几个连接顶点, 即相邻顶点
-
单链表中节点的数据结构
邻接顶点位置(vex): 整型，记录邻接顶点在在顶点表中的位置, 即数组索引值单链表下一个(next):下一个节点
示例邻接表建立
- 概况
数组 = [
# 顶点0 有2个 邻接顶点, 分别是 顶点1, 顶点2
顶点0(visited=0, 邻接表节点(1, next=邻接表节点(2))),
顶点1(visited=0, 邻接表节点(0),
顶点2(visited=0, 邻接表节点(1)),
]
- 建立
class AdjNode():
def __init__(self, vex: int, next=None):
self.vex = vex
self.next = next
class VexNode():
def __init__(self, first_adj=None):
self.visited = 0
self.first_adj = first_adj
adjlist2 = [
0,
VexNode(first_adj=AdjNode(3, AdjNode(2))),
VexNode(first_adj=AdjNode(5, AdjNode(4, AdjNode(1)))),
VexNode(first_adj=AdjNode(7, AdjNode(6, AdjNode(1)))),
VexNode(first_adj=AdjNode(2)),
VexNode(first_adj=AdjNode(2)),
VexNode(first_adj=AdjNode(7, AdjNode(3))),
VexNode(first_adj=AdjNode(6, AdjNode(3))),
VexNode()
]
图遍历
深度优先搜索(Depth-First Search)
树的先根遍历的推广
(1) 深度优先搜索基本思想：
1、从图中某个顶点Vi出发, 首先访问 Vi。
2、选择并访问与Vi相邻且“未访问过”(通过visited判断)的顶点Vj, 然后以该顶点为新的顶点，重复此步骤，直到当前顶点
没有未访问过的顶点为止。
3、返回前一个仍有未访问的邻接点的顶点，找出(可通过栈或递归实现)并访问该顶点的下一个未访问的邻接点，
然后执行步骤 2
(2) 若是非连通图：
在遍历完一个连通子图后，若图中仍然有未访问的顶点，则选出一个作为起始点，进行(1)操作,
直至图中所有顶点都访问过为止。
算法实现：
递归：
def dfs_recursion2(adjlis: List[VexNode], v: int):
def dfs(i):
print(i, end="")
adjlis[i].visited = 1
node = adjlis[i].first_adj
while node:
if not adjlis[node.vex].visited:
dfs(node.vex)
node = node.next
dfs(v)
for i in range(1, len(adjlis)):
if not adjlis[i].visited:
dfs(i)
非递归:
def dfs_not_recursion2(adjlis: List[VexNode], v: int):
def _dfs(i):
print(i, end="")
adjlis[i].visited = 1
op_stack.append(adjlis[i].first_adj)
while op_stack:
node = op_stack.pop(-1)
while node:
if not adjlis[node.vex].visited:
print(node.vex, end="")
adjlis[node.vex].visited = 1
op_stack.append(node.next)
op_stack.append(adjlis[node.vex].first_adj)
break
node = node.next
op_stack = []
_dfs(v)
for i in range(1, len(adjlis)):
if not adjlis[i].visited:
_dfs(i)
广度优先搜索(Breadth-First Search)
树的层次遍历的推广
这个就和树的层次遍历一样，图中的所谓的层次，也就是访问第一个指定顶点后，依次先访问它的邻接结点们，
访问顺序遵从单链邻接表的顺序，并在访问过程中依次记录下每个邻接顶点它们各自的邻接结点，作为之后
的访问顺序
def bfs_not_recursion2(adjlis: List[VexNode], v: int):
def _bfs(i):
op_queue.append(i)
while op_queue:
i = op_queue.pop(0)
if adjlis[i].visited: # 因为每次都会把某个结点的所有出度都放到队列中，所以队列中可能会存在相同的结点
continue
print(i, end="")
adjlis[i].visited = 1
node = adjlis[i].first_adj
while node:
if not adjlis[node.vex].visited:
op_queue.append(node.vex)
node = node.next
op_queue = []
_bfs(v)
for i in range(1, len(adjlis)):
if not adjlis[i].visited:
_bfs(i)