算法是编码面试中最常见的主题之一。为了在面试中获得优势，非常熟悉顶级算法及其实现非常重要。

在次此篇文章中，我们将探索图算法。我们将从图论和图算法的介绍开始。接下来，我们将学习如何实现图。

今天，我们将学习：

什么是图算法？图的属性如何在代码中表示图形如何实现广度优先遍历如何实现深度优先遍历如何去除边缘什么是图算法？

算法是使用明确定义或最佳步骤数解决问题的数学过程。它只是用于完成特定工作的基本技术。

图是一种抽象符号，用于表示所有对象对之间的连接。图是广泛使用的数学结构，由两个基本组成部分可视化：节点和边。

图算法用于解决将图表示为网络的问题，例如航空公司航班、互联网如何连接或微信、QQ、微博上的社交网络连接。它们在NLP和机器学习中也很流行，用于形成网络。

一些顶级的图形算法包括：

实现广度优先遍历实现深度优先遍历计算图级别中的节点数查找两个节点之间的所有路径查找图的所有连通分量Dijkstra 算法在图数据中查找最短路径移除边缘

虽然图是离散数学不可或缺的一部分，但它们在计算机科学和编程中也有实际用途，包括以下内容：

计算机程序中以图形表示的调用者-被调用者关系网站的链接结构可以用有向图来表示神经网络

图的属性

由 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，满足以下条件：

k>2k>2k>2k _>2首先k-1顶点都不同v1=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 }

对于下面的基图类，我们将使用邻接列表实现，因为它对于本文后面的算法解决方案执行得更快。

图类（Graph Class）

我们的图实现的要求相当简单。我们需要两个数据成员：图中顶点的总数和存储相邻顶点的列表。我们还需要一种添加边或一组边的方法。

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:    """    # 写你的代码    pass

解决方案

bfs:

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:    """        # 在这里写下你的代码!    pass

解决方案

dfs：

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）数据结构中的各种问题的算法，对广度优先和深度优先做了一些示例，还有注释，我们可以私下练习一下。

图算法能够帮助我们理解和处理复杂的关系型数据，并在实际应用中提供解决方案。