时间戳

首页 > 解决方案 > 从用户那里获取图形输入，用于 dfs 算法

python - 从用户那里获取图形输入，用于 dfs 算法

问题描述

我想编写一个 DFS 算法，它可以为我在输入询问时给出的任何图形提供 DFS 结果。

但我找不到解决方案。我唯一发现的是代码中特定图形的算法。

# Using a Python dictionary to act as an adjacency list
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

标签： pythonalgorithminputuser-inputdepth-first-search

解决方案

这是工作代码，您可以更改图表或输入自己的代码。此 DFS 适用于加权路径。图形表示如下：

adjacency_list = {
    'A': [('B', 1)],
    'B': [('A', 1), ('C', 1)],
    'C': [('A', 1)]
}

输入图形输入结，然后在数组中输入元组作为邻居（使用一些字符或数字停止输入该结）这是DFS

class Graph:
    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list
        
    def __str__(self):
        return str(self.adjacency_list)
        
    def get_neighbors(self, v):
        return self.adjacency_list[v]
        
    def dfs(self, start, stop):
        visited = set([])
        
        visited.add(start)
        path = [start]
        
        while len(path) > 0:
            
            n = path[-1]
            
            if n == stop:
                print('Path found: {}'.format(path))
                return path
            
            has_unvisited = False
            
            for (m, weight) in self.get_neighbors(n):
                if m not in visited:
                    path.append(m)
                    visited.add(m)
                    has_unvisited = True
                    break

            if (not has_unvisited):
                path.pop()

        print('Path doesnt exist')
        return None

你用这个来调用 DFS：

g = Graph(adjacency_list)
g.dfs('A','C')

推荐阅读