【生物信息学算法】图算法1：概念和算法

本文主要是介绍【生物信息学算法】图算法1：概念和算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 图的定义、分类、表达方式

图的定义

图G可以由两个集合来定义，即G=(V,E)。其中，V是对象的集合，称为图的顶点或节点; E是V中(u,v)顶点对的集合，称为边或弧，表示u和v之间的关系存在。

图的分类

1. 有向图：E有方向性，即顶点对是有序的。
2. 无向图：E无方向性，即顶点对是无序的。
3. 加权图：对E中的边赋予数值权重。

表达方式

图形，邻接矩阵，邻接列表

·邻接矩阵：行列表示图的节点；矩阵中的具体数值，在无权图中主要表示是否存在该边（以及该边的方向），在加权图中则会包含权重的信息
·当图是稀疏时，使用基于邻接列表的实现存储更有效

Python实现

class MyGraph:# 定义图的类def __init__(self, g={}):'''构造函数，接受一个字典作为输入来填充图的结构；默认为一个空字典。:param g: 图的初始结构，默认为空字典'''self.graph = g# 获取图的基本信息def get_nodes(self):'''获取图中的所有节点（顶点）。:return: 节点列表'''return list(self.graph.keys())def get_edges(self):'''获取图中的所有边。:return: 边的列表，列表中的每个元素是一个元组，表示两个相连的节点'''edges = []# 遍历所有节点for v in self.graph.keys():# 遍历每个节点的邻接列表for d in self.graph[v]:# 将每条边（节点对）添加到边列表中edges.append((v, d))return edgesdef size(self):'''返回图的节点数和边数。:return: 一个元组，包含节点数和边数'''return len(self.get_nodes()), len(self.get_edges())def print_graph(self):'''打印图的邻接列表表示法。每个节点及其相邻节点列表都会输出。'''for v in self.graph.keys():print(v, " -> ", self.graph[v])def add_vertex(self, v):'''向图中添加一个新的节点（顶点）。如果节点已存在，则不添加。:param v: 要添加的节点'''if v not in self.graph.keys():self.graph[v] = []def add_edge(self, o, d):'''向图中添加一条新的边。如果边的两个节点（顶点）不存在，则会自动添加这些节点。:param o: 边的起始节点:param d: 边的目标节点'''# 如果起始节点不存在，则添加该节点if o not in self.graph.keys():self.add_vertex(o)# 如果目标节点不存在，则添加该节点if d not in self.graph.keys():self.add_vertex(d)# 如果目标节点不在起始节点的邻接列表中，则添加该边if d not in self.graph[o]:self.graph[o].append(d)

2.相邻节点和度

概念定义

在有向图G=(V,E)中，若边的集合E中存在有序对(s,v)，则顶点v是顶点s的后继(successor)，s称为v的前身；两个顶点s和v被命名为邻接，即如果一个顶点是另一个顶点的后继，则两个顶点是邻接的。

节点度为给定节点的相邻节点数，在有向图中：入度为计算一个节点的前置数，出度为一个节点的后继数。

python实现

接上

    def get_successors(self, v):'''获取节点v的所有后继节点（邻接节点）。返回v的邻接列表的副本，避免列表被覆盖。:param v: 节点:return: 节点v的所有后继节点的列表'''return list(self.graph[v])  # 返回节点v的邻接列表的副本，避免原列表被修改def get_predecessors(self, v):'''获取图中所有指向节点v的前驱节点。:param v: 节点:return: 节点v的所有前驱节点的列表'''res = []  # 用于存储前驱节点的列表# 遍历所有节点，检查它们的邻接列表for k in self.graph.keys():if v in self.graph[k]:  # 如果节点v在节点k的邻接列表中，说明k是v的前驱节点res.append(k)return resdef get_adjacents(self, v):'''获取与节点v相连的所有相邻节点，包括前驱和后继。:param v: 节点:return: 节点v的所有相邻节点的列表'''suc = self.get_successors(v)  # 获取v的后继节点pred = self.get_predecessors(v)  # 获取v的前驱节点res = pred  # 将前驱节点列表赋值给res# 检查所有后继节点，如果它们不在前驱节点列表中，则添加到结果列表中for p in suc:if p not in res:res.append(p)return resdef out_degree(self, v):'''计算节点v的出度（从该节点出发的边的数量）。:param v: 节点:return: 节点v的出度'''return len(self.graph[v])  # 节点v的邻接列表的长度即为出度def in_degree(self, v):'''计算节点v的入度（指向该节点的边的数量）。:param v: 节点:return: 节点v的入度'''return len(self.get_predecessors(v))  # 前驱节点的数量即为入度def degree(self, v):'''计算节点v的度数（与该节点相连的边的数量，包括入度和出度）。:param v: 节点:return: 节点v的度数'''return len(self.get_adjacents(v))  # 相邻节点的数量即为度数def all_degrees(self, deg_type="inout"):'''计算所有节点的度数（入度、出度或总度数）。:param deg_type: 度数类型，可以是 "in"（入度）、"out"（出度）或 "inout"（总度数）:return: 一个字典，键是节点，值是对应的度数'''degs = {}  # 创建一个空字典用于存储每个节点的度数# 遍历所有节点，计算出度或总度数for v in self.graph.keys():# 如果度数类型是出度("out")或总度数("inout")if deg_type == "out" or deg_type == "inout":degs[v] = len(self.graph[v])  # 节点v的出度是其邻接列表的长度else:degs[v] = 0  # 如果不是计算出度，初始化为0# 遍历所有节点，计算入度或总度数if deg_type == "in" or deg_type == "inout":for v in self.graph.keys():# 遍历节点v的邻接节点for d in self.graph[v]:# 如果度数类型是入度("in")或者v不在d的邻接列表中（避免重复计算）if deg_type == "in" or v not in self.graph[d]:degs[d] = degs[d] + 1  # 对应节点的度数加1return degs  # 返回包含所有节点度数的字典

3.路径、距离和搜索

路径和距离

路径(path)：在有向图中，定义为节点的有序列表，其中列表中的连续节点需要通过边连接。即这个过程中的每一步都是从一个节点沿着图中的一条“边”走到另一个节点。所以路径就是这些节点的有序排列。

在图 G=(V, E) 中：

• 有向图中，节点 x 和任意节点 y 之间的路径 P 是列表$P=p_1,p_2,\dots ,p_n$，其中 $p_1=x$, $p_n=y$，以及 $P$ 上的所有连续节点对 $(p_i,p_{i+1})\in E$ 。即路径上的每一对相邻节点 $p_i,p_{i+1}$ 都必须是有向边集合 $E$ 中的一条边。
• 无向图中，则 $(p_i,p_{i+1})\in E$ 或 $(p_{i+1},p_i)\in E$
  最短路径：两个节点之间边数最少的路径，最短路径的长度称为两点间的距离。
  代码实现：

    def distance(self, s, d):'''计算从节点s到节点d的最短路径的距离（使用广度优先搜索算法）。:param s: 起始节点:param d: 目标节点:return: 从s到d的最短距离，如果没有路径返回None'''if s == d:  # 如果起始节点等于目标节点，距离为0return 0l = [(s, 0)]  # 初始化队列l，包含起始节点和初始距离0visited = [s]  # 初始化已访问列表，包含起始节点# 当队列不为空时，继续搜索while len(l) > 0:node, dist = l.pop(0)  # 弹出队列的第一个元素，获取当前节点和当前距离# 遍历当前节点的邻接节点for elem in self.graph[node]:if elem == d:  # 如果找到目标节点，返回距离加1return dist + 1elif elem not in visited:  # 如果邻接节点未访问过l.append((elem, dist + 1))  # 将邻接节点加入队列，距离加1visited.append(elem)  # 标记邻接节点为已访问return None  # 如果没有找到路径，返回Nonedef shortest_path(self, s, d):'''查找从节点s到节点d的最短路径（使用广度优先搜索算法）。:param s: 起始节点:param d: 目标节点:return: 从s到d的最短路径（节点列表），如果没有路径返回None'''if s == d:  # 如果起始节点等于目标节点，返回空路径return 0l = [(s, [])]  # 初始化队列l，包含起始节点和初始路径（空列表）visited = [s]  # 初始化已访问列表，包含起始节点# 当队列不为空时，继续搜索while len(l) > 0:node, preds = l.pop(0)  # 弹出队列的第一个元素，获取当前节点和路径# 遍历当前节点的邻接节点for elem in self.graph[node]:if elem == d:  # 如果找到目标节点，返回完整路径return preds + [node, elem]elif elem not in visited:  # 如果邻接节点未访问过l.append((elem, preds + [node]))  # 将邻接节点加入队列，更新路径visited.append(elem)  # 标记邻接节点为已访问return None  # 如果没有找到路径，返回None

搜索

广度优先搜索(BFS):从源节点开始，然后访问其所有后续节点，然后访问这些后续节点的后续节点，直到访问所有可能的节点；
深度优先搜索(DFS):从源节点开始，先搜索第一个后继节点，然后再搜索其第一个后继节点，直到无法进行进一步的搜索，然后回溯以探索其他替代方案。

代码实现：

    def reachable_bfs(self, v):'''使用广度优先搜索（BFS）算法找到从节点v可以到达的所有节点。:param v: 起始节点:return: 从v可以到达的所有节点的列表'''l = [v]  # 初始化列表l，包含起始节点v，作为搜索队列res = []  # 初始化结果列表，用于存储已访问的节点# 当搜索队列不为空时，继续搜索while len(l) > 0:node = l.pop(0)  # 取出队列的第一个节点# 如果节点不是起始节点，添加到结果列表if node != v:res.append(node)# 遍历当前节点的所有邻接节点for elem in self.graph[node]:# 如果邻接节点不在结果列表和搜索队列中，加入队列if elem not in res and elem not in l:l.append(elem)return res  # 返回所有从节点v可以到达的节点def reachable_dfs(self, v):'''使用深度优先搜索（DFS）算法找到从节点v可以到达的所有节点。:param v: 起始节点:return: 从v可以到达的所有节点的列表'''l = [v]  # 初始化列表l，包含起始节点v，作为搜索堆栈res = []  # 初始化结果列表，用于存储已访问的节点# 当搜索堆栈不为空时，继续搜索while len(l) > 0:node = l.pop(0)  # 取出堆栈的第一个节点# 如果节点不是起始节点，添加到结果列表if node != v:res.append(node)s = 0  # 位置变量，用于控制新元素插入的位置（保持DFS的堆栈顺序）# 遍历当前节点的所有邻接节点for elem in self.graph[node]:# 如果邻接节点不在结果列表和搜索堆栈中，插入堆栈顶部if elem not in res and elem not in l:l.insert(s, elem)  # 在索引s的位置插入元素s += 1  # 更新位置变量return res  # 返回所有从节点v可以到达的节点

环

·如果一条路径在同一个顶点上开始和结束，则该路径被定义为闭合的。
·如果在闭合路径中没有重复的节点或边，则该路径称为环。(主要为了排除两个节点间的一来一回)
代码实现：

def node_has_cycle(self, v):'''检查从给定节点v开始的图中是否存在环（使用广度优先搜索算法）。:param v: 起始节点:return: 如果存在环，返回True；否则返回False'''l = [v]  # 初始化队列l，包含起始节点vres = False  # 初始化结果为False，表示暂未发现环visited = [v]  # 初始化已访问列表，包含起始节点v# 当队列不为空时，继续搜索while len(l) > 0:node = l.pop(0)  # 弹出队列的第一个元素，获取当前节点# 遍历当前节点的所有邻接节点for elem in self.graph[node]:if elem == v:  # 如果邻接节点等于起始节点，说明存在环return Trueelif elem not in visited:  # 如果邻接节点未访问过l.append(elem)  # 将邻接节点加入队列visited.append(elem)  # 标记邻接节点为已访问return res  # 如果没有发现环，返回Falsedef has_cycle(self):'''测试图中是否存在环（从任意节点开始）。:return: 如果存在环，返回True；否则返回False'''res = False  # 初始化结果为False，表示暂未发现环# 遍历所有节点，测试每个节点是否是环的起点for v in self.graph.keys():if self.node_has_cycle(v):  # 如果从节点v开始存在环return Truereturn res  # 如果没有发现环，返回False

4.图论中的欧拉定理

欧拉迹（欧拉路径）：在图论中，欧拉迹是指一条经过图中所有边且恰好一次的路径。这条路径可以重复访问顶点，但不能重复访问边。
欧拉回路：在图论中，欧拉回路指的是一种通过图中所有边恰好一次，并且最终回到起点的闭合路径。
连通图：如果图中的任意两个顶点之间都有路径相连，那么这个图被称为连通图。换句话说，连通图是一个没有孤立部分的图，图中的所有顶点都是相互可达的。
欧拉定理：连通图存在欧拉迹当且仅当图中奇度数的点的个数至多为 2

这篇关于【生物信息学算法】图算法1：概念和算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---