计算未加权图中节点之间的距离

作者

图遍历算法有多种应用。应用之一是找到图的两个节点之间的最小距离。在本文中，我们将使用广度优先图遍历算法实现一种算法，在 python 中找到未加权的全连接图中的最小距离。

对图使用 BFS 算法

广度优先搜索是一种图遍历算法，其中我们从任意单个顶点开始，对图的每个顶点恰好遍历一次。对于每个选定的顶点，我们首先打印该顶点，然后打印其所有邻居。这个过程一直持续到遍历完所有的顶点为止。当使用广度优先搜索遍历图时，看起来我们正在从选定的顶点开始分层移动。

图的 BFS 算法的实现如下。在此算法中，我们假设图是无权、无向且全连接的。

def bfs(graph, source):
    Q = Queue()
    visited_vertices = set()
    Q.put(source)
    visited_vertices.update({0})
    while not Q.empty():
        vertex = Q.get()
        print(vertex, end="-->")
        for u in graph[vertex]:
            if u not in visited_vertices:
                Q.put(u)
                visited_vertices.update({u})

确定未加权图的两个节点之间的最小距离

我们可以使用广度优先搜索算法，通过对算法进行一定的修改来找到从源到所有节点的最小距离。

给定图的源和邻接列表表示，我们将声明一个包含所有访问过的顶点的列表，我们还将创建一个字典，其中字典的键确定顶点，值确定当前顶点和顶点之间的距离。来源。

这里对 BFS 算法的修改是，每当我们处理一个顶点 v 时，我们都会更新它的邻居的距离。v 的邻居到源的距离将等于 v 到源的距离加一。

确定最小距离的算法

由于我们对如何确定从源到每个顶点的最小距离有了大致的了解，因此我们将为其制定算法。

Algorithm Least Distance:
Input: Graph(Adjacency list) and Source vertex
Output: A list with distance of each vertex from source
Start:
    1.Create an empty queue Q.
    2.Create an empty set to keep record of visited vertices.
    3. Create a dictionary in which keys of the dictionary determine the vertex and values determine the distance between current vertex and source.
    4.Insert source vertex into the Q and Mark the source as visited.
    5.If Q is empty, return. Else goto 6.
    6.Take out a vertex v from Q.
    7.Insert all the vertices in the adjacency list of v which are not in the visited list into Q and mark them visited after updating their distance from source.
    8.Goto 5.
Stop.

实现图遍历计算最小距离

由于我们已经制定了用于确定顶点与源的最小距离的算法，因此我们将实现该算法并针对下图中给出的图执行该算法。

Python 中的图实现 – Askpython

该算法在python中的实现如下。

from queue import Queue
 
myGraph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
 
 
def leastDistance(graph, source):
    Q = Queue()
    # create a dictionary with large distance(infinity) of each vertex from source
    distance = {k: 9999999 for k in myGraph.keys()}
    visited_vertices = set()
    Q.put(source)
    visited_vertices.update({0})
    while not Q.empty():
        vertex = Q.get()
        if vertex == source:
            distance[vertex] = 0
        for u in graph[vertex]:
            if u not in visited_vertices:
                # update the distance
                if distance[u] > distance[vertex] + 1:
                    distance[u] = distance[vertex] + 1
                Q.put(u)
                visited_vertices.update({u})
    return distance
 
 
print("Least distance of vertices from vertex 0 is:")
print(leastDistance(myGraph, 0))

输出：

Least distance of vertices from vertex 0 is:
{0: 0, 1: 1, 2: 2, 3: 1, 4: 2, 5: 3}

结论

在本文中，我们实现了一种算法，使用深度优先搜索遍历算法来查找源与图的其他顶点之间的最小距离。请继续关注更多信息丰富的文章。