python深度优先遍历代码，python段错误是为什么

深度优先遍历（Depth First Search，DFS）是一种经典的图遍历算法，其主要思想是从图中某个顶点出发，沿着一条路线遍历直到末端，然后回溯到前一个结点，在遍历下一条路径，直到所有路径都被遍历。

在进行深度优先遍历时，需要考虑图的连通性，即要保证每个顶点都能被遍历到。一般情况下，可以通过遍历每个顶点来实现深度优先遍历。

下面是一个简单的深度优先遍历的代码实现：

```

# Python3 program to print DFS traversal from a given vertex

# in a given graph

from collections import defaultdict

# This class represents a directed graph using adjacency

# list representation

class Graph:

# Constructor

def __init__(self):

# default dictionary to store graph

self.graph = defaultdict(list)

# function to add an edge to the graph

def addEdge(self,u,v):

self.graph[u].append(v)

# A function used by DFS

def DFSUtil(self,v,visited):

# Mark the current node as visited and print it

visited.add(v)

print (v)

# Recur for all the vertices adjacent to this vertex

for neighbour in self.graph[v]:

if neighbour not in visited:

self.DFSUtil(neighbour, visited)

# The function to do DFS traversal. It uses recursive DFSUtil()

def DFS(self,v):

# Create a set to store visited vertices

visited = set()

# Call the recursive helper function

# to print DFS traversal

self.DFSUtil(v,visited)

# Driver code

# Create a graph given in the above diagram

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print ("Following is DFS from (starting from vertex 2)")

g.DFS(2)

```

在上述代码中，首先定义了一个Graph类，用来表示一个图。该类使用defaultdict来存储图。

addEdge()函数用来添加一条边，DFSUtil()函数用来进行深度优先遍历的递归调用，DFS()函数则是遍历入口。

在DFSUtil()函数中，首先将当前节点标记为已访问，并打印节点值。然后对于当前节点的所有邻居节点，如果该邻居节点还没有被访问过，就递归调用DFSUtil()对其进行深度优先遍历。

整个深度优先遍历的过程可以看作是一个递归的过程，递归调用栈中存储的就是遍历过程中已经访问过的节点。

深度优先遍历有一些比较重要的特点：

1. 深度优先遍历是一种递归算法，递归实现相对简单。

2. 深度优先遍历会优先遍历最深的节点。

3. 深度优先遍历可以通过栈（自己实现）或递归实现，前者效率高但代码相对复杂，后者代码简单但效率比较低。

那么深度优先遍历的递归调用会有哪些问题呢？

首先，当图很大或者连通性不好时，深度优先遍历可能会导致堆栈溢出（stack overflow）。

此时，可以考虑使用迭代式的实现，即维护一个遍历过程中需要访问的节点队列，每次取出队列中的节点进行遍历，直到所有节点都被遍历过。具体实现可以使用一个栈结构来存储待访问的节点，每次取出栈顶元素来进行遍历，直到栈为空。

下面是一个基于栈实现的深度优先遍历代码：

```

# Python3 program to print DFS traversal from a given vertex

# in a given graph

from collections import defaultdict

# This class represents a directed graph using adjacency

# list representation

class Graph:

# Constructor

def __init__(self):

# default dictionary to store graph

self.graph = defaultdict(list)

# function to add an edge to the graph

def addEdge(self,u,v):

self.graph[u].append(v)

# The function to do DFS traversal using stack

def DFS(self, v):

# Create a set to store visited vertices

visited = set()

# Create a stack for DFS

stack = []

# Push the current source node.

stack.append(v)

while stack:

# Pop a vertex from stack and print it

v = stack.pop()

# If not visited, mark it as visited and

# print it

if v not in visited:

visited.add(v)

print (v)

# Get all adjacent vertices of the popped vertex s

# If a adjacent has not been visited, then push it

# to the stack.

for neighbour in self.graph[v]:

if neighbour not in visited:

stack.append(neighbour)

# Driver code

# Create a graph given in the above diagram

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print ("Following is DFS from (starting from vertex 2)")

g.DFS(2)

```

整个过程中，需要维护两个数据结构：visited和stack。其中，visited用来记录已经访问过的节点，stack用来存储待访问的节点。在遍历过程中，每次取出栈顶元素进行遍历，并将其所有未访问的邻居节点压入栈中等待遍历。当栈为空时，整个遍历过程结束。

最后，需要注意的是，深度优先遍历可能会重复访问某些已经访问过的节点，因此需要使用visited数组或者集合来记录已经访问过的节点，避免重复访问。同时，需要考虑图的连通性，保证每个顶点都能被遍历到。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.ynyuzhu.com/