算法是编码面试中最常见的主题之一。为了在面试中获得优势，非常熟悉顶级算法及其实现非常重要。
在次此篇文章中，我们将探索图算法。我们将从图论和图算法的介绍开始。接下来，我们将学习如何实现图。
今天，我们将学习：
算法是使用明确定义或最佳步骤数解决问题的数学过程。它只是用于完成特定工作的基本技术。
图是一种抽象符号，用于表示所有对象对之间的连接。图是广泛使用的数学结构，由两个基本组成部分可视化：节点和边。
图算法用于解决将图表示为网络的问题，例如航空公司航班、互联网如何连接或微信、QQ、微博上的社交网络连接。它们在NLP和机器学习中也很流行，用于形成网络。
一些顶级的图形算法包括：
虽然图是离散数学不可或缺的一部分，但它们在计算机科学和编程中也有实际用途，包括以下内容：
由 G 表示的图由一组顶点 (V)或在边 (E)处链接的节点表示。边的数量取决于顶点。边缘可以是有向的或无向的。
在有向图中，节点沿一个方向链接。这里的边显示了一种单向关系。
在无向图中，边是双向的，显示出双向关系。
示例：无向图的一个很好的用例是微信好友建议算法。用户（节点）有一个边缘运行到朋友 A（另一个节点），而朋友 A 又连接（或有一个边缘运行）到朋友 B。然后将朋友 B 推荐给用户。
还有许多其他复杂类型的图属于不同的子集。例如，当每个顶点都可以从其他每个顶点到达时，有向图就具有强连通分量。
顶点是多条线相交的点。它也称为节点。
边是一个数学术语，用于表示连接两个顶点的线。许多边可以由单个顶点形成。然而，没有顶点，就无法形成边。每条边必须有一个起始和结束顶点。
图中的路径G=( V ,E ）是顶点 v1, v2, …, vk 的序列，其属性是之间有边 vi 和 vi +1。我们说路径从v1到vk 。
序列 6,4,5,1,26,4,5,1,2 定义从节点 6 到节点 2 的路径。
类似地，可以通过遍历图的边来创建其他路径。如果路径的顶点全部不同，则路径很简单。
行走是路径，但它们不需要一系列不同的顶点。
如果对于每对顶点，则图是连通的v和v，有一条路径从v到v。
循环是一条路径 v1, v2, …, vk，满足以下条件：
树是不包含环的连通图。
在图中，如果从顶点到自身绘制一条边，则称为环。在图中，V 是一个顶点，其边 (V, V) 形成一个环。
在我们继续使用图算法解决问题之前，首先了解如何在代码中表示图非常重要。图可以表示为邻接矩阵或邻接列表。
邻接矩阵是由图顶点标记的方阵，用于表示有限图。矩阵的条目指示顶点对在图中是否相邻。
在邻接矩阵表示中，需要迭代所有节点来识别节点的邻居。
a b c d ea 1 1 - - -b - - 1 - -c - - - 1 -d - 1 1 - -邻接表用于表示有限图。邻接列表表示允许轻松地遍历节点的邻居。列表中的每个索引代表顶点，与该索引链接的每个节点代表其相邻顶点。
1 a -> { a b }2 b -> { c }3 c -> { d }4 d -> { b c }对于下面的基图类，我们将使用邻接列表实现，因为它对于本文后面的算法解决方案执行得更快。
我们的图实现的要求相当简单。我们需要两个数据成员：图中顶点的总数和存储相邻顶点的列表。我们还需要一种添加边或一组边的方法。
class AdjNode: """ 表示节点邻接表的 类 """ def __init__(self, data): """ 构造函数 :参数数据 : 顶点 """ self.vertex = data self.next = Noneclass Graph: """ 图类 ADT """ def __init__(self, vertices): """ 构造函数 :param vertices : 图中的总顶点数 """ self.V = vertices self.graph = [None] * self.V # 在无向图中添加边的函数 def add_edge(self, source, destination): """ 添加边缘 :param source: 源顶点 :param destination: 目标顶点 """ # 将节点添加到源节点 node = AdjNode(destination) node.next = self.graph[source] self.graph[source] = node # 如果无向图，将源节点添加到目标节点 # 故意注释这一行，方便理解 #node = AdjNode(source) #node.next = self.graph[destination] #self.graph[destination] = node def print_graph(self): """ 打印图标的函数 """ for i in range(self.V): print("Adjacency list of vertex {}/n head".format(i), end="") temp = self.graph[i] while temp: print(" -> {}".format(temp.vertex), end="") temp = temp.next print(" /n")# 主程序if __name__ == "__main__": V = 5 # 顶点总数 g = Graph(V) g.add_edge(0, 1) g.add_edge(0, 4) g.add_edge(1, 2) g.add_edge(1, 3) g.add_edge(1, 4) g.add_edge(2, 3) g.add_edge(3, 4) g.print_graph()在上面的示例中，我们看到了Python graph class。我们已经奠定了图形类的基础。变量 V 包含一个整数，指定顶点总数。下面示例的代码都会用到这个类。
给定一个表示为邻接列表和起始顶点的图，代码应该输出一个字符串，其中包含以正确的遍历顺序列出的图的顶点。当从起始顶点遍历图形时，将首先打印每个节点的右子节点，然后是左子节点。
为了解决这个问题，前面已经实现了 Graph 类。
输入：表示为邻接列表和起始顶点的图。
输出：一个字符串，其中包含以正确的遍历顺序列出的图的顶点。
示例输出：
result = "02143" orresult = "01234"在开始实施之前，先看一下并设计一个分步算法。首先尝试自己解决。如果遇到困难，可以随时参考解决方案部分提供的解决方案。
bfs：
def bfs(graph, source): """ 打印图的 BFS 的函数 :param graph: 图表 :param source: 起始顶点 :return: """ # 写你的代码 passbfs：
def bfs(my_graph, source): """ 打印图的 BFS 函数 :param graph: 图表 :param source: 起始顶点 :return: """ # 将所有的顶点标识为未访问过 visited = [False] * (len(my_graph.graph)) # 创建 BFS 队列 queue = [] # 结果字符串 result = "" # 将源节点表示为 访问过并将其排入队列 queue.append(source) visited[source] = True while queue: # 经一个顶点重队列中取出 # 排队并打印 source = queue.pop(0) result += str(source) # 取出相邻的顶点 # 出对的顶点源， #如果一个相邻的还没有访问过，那么标记一下 # 访问过并将其排入队列 while my_graph.graph[source] is not None: data = my_graph.graph[source].vertex if not visited[data]: queue.append(data) visited[data] = True my_graph.graph[source] = my_graph.graph[source].next return result# 主要测试上面的程序if __name__ == "__main__": V = 5 g = Graph(V) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 3) g.add_edge(1, 4) print(bfs(g, 0))我们从选定的节点开始，逐层遍历图。探索所有邻居节点。然后，我们进入下一个级别。我们水平遍历图表，也就是每一层。
图表可能包含循环。为了避免再次处理同一节点，我们可以使用布尔数组来标记访问过的数组。可以使用队列来存储节点并将其标记为已访问。队列应遵循先进先出（FIFO）排队方法。
在这个问题中，你必须实现深度优先遍历。为了解决这个问题，之前实现的图类已经提供了。
输入：表示为邻接列表和起始顶点的图。
输出：一个字符串，其中包含以正确的遍历顺序列出的图的顶点。
示例输出：
result = "01342" orresult = "02143"在开始实施之前，先看一下并设计一个分步算法。首先尝试自己解决。如果遇到困难，可以随时参考解决方案部分提供的解决方案。
dfs：
def dfs(graph, source): """ 打印图的 DFS 的函数 :param graph: 图表 :param source: 起始顶点 :return: """ # 在这里写下你的代码! passdfs：
def dfs(my_graph, source): """ 打印图的DFS的函数 :param graph: 图表 :param source: 起始顶点 :return: 以字符串形式返回遍历结果 """ # 将所有顶点标记为未访问过 visited = [False] * (len(my_graph.graph)) # 创建 DFS 堆栈 stack = [] # 结果字符串 result = "" # 拼接字符 stack.append(source) while stack: # 从堆栈中弹出一个顶点 source = stack.pop() if not visited[source]: result += str(source) visited[source] = True # 获取弹出顶点源的所有相邻顶点 # 如果相邻的未必访问过，则将其压入 while my_graph.graph[source] is not None: data = my_graph.graph[source].vertex if not visited[data]: stack.append(data) my_graph.graph[source] = my_graph.graph[source].next return result# 主程序运行if __name__ == "__main__": V = 5 g = Graph(V) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 3) g.add_edge(1, 4) print(dfs(g, 0))深度优先图算法利用了回溯的思想。这里的“回溯”是指只要当前路径上没有更多的节点，就向前移动，然后在同一条路径上向后移动，寻找要遍历的节点。
在此问题中，必须实现remove_edge以源和目标作为参数的函数。如果两者之间存在边，则应将其删除。
输入：图形、源（整数）和目标（整数）。
输出：对图进行 BFS 遍历，并删除源和目标之间的边。
首先，在开始实施之前仔细研究这个问题并设计一个分步算法。
remove_edge：
def remove_edge(graph, source, destination): """ 删除边缘函数 :param graph: 图表 :param source: 源顶点 :param destination: 目标顶点 """ # 写代码 pass如果熟悉的话，这个解决方案与链表中的删除非常相似。
我们的顶点存储在一个链接列表中。首先，我们访问source链表。如果源链表的头节点持有要删除的键，我们将头向前移动一步并返回图。
如果要删除的键位于链表的中间，我们会跟踪前一个节点，并在目的地遇到时将前一个节点与下一个节点连接起来。
图算法是用于解决图（Graph）数据结构中的各种问题的算法，对广度优先和深度优先做了一些示例，还有注释，我们可以私下练习一下。
图算法能够帮助我们理解和处理复杂的关系型数据，并在实际应用中提供解决方案。
本文链接：http://www.28at.com/showinfo-26-17169-0.html如何使用图算法，帮助我们理解和处理复杂的关系型数据
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： RabbitMQ的四种交换机详解
下一篇： 一次单据图片处理的优化实践
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
