class adjMatrixGraph: # 构造方法,n个顶点m条边 def __init__(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表,默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #顶点v(编号)出发对图G进行深度优先遍历 def dfs(G,v): #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g #返回无向图g g = createGraph() #创建无向图g v = int(input()) #输入出发顶点的编号 print("DFS from " + g.vertex[v] + " :",end = "") dfs(g,v) #顶点v(编号)出发对图G进行深度优先遍历
时间: 2024-02-14 14:23:21 浏览: 116
这段代码实现了一个无向图的深度优先遍历。其中,使用邻接矩阵来表示图的结构,顶点列表用于存储顶点的值,通过addVertex方法可以添加顶点列表,通过addEdge方法可以添加边。dfs函数实现了深度优先遍历,它首先标记当前顶点为已访问,然后遍历与当前顶点相邻的未访问过的顶点,并递归访问这些顶点。最后,通过createGraph函数可以创建一个无向图,并通过输入指定出发顶点的编号来进行深度优先遍历。
相关问题
class adjMatrixGraph: # 构造方法,n个顶点m条边 def __init__(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表,默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 编写一个深度优先搜索得函数
以下是一个深度优先搜索函数的示例代码:
```python
def DFS(graph, start):
visited = [False] * graph.verNum # 初始化所有顶点为未访问状态
stack = [] # 栈用于存储待访问的顶点
stack.append(start) # 将起始顶点加入栈中
while stack:
# 取出栈顶元素作为当前访问的顶点
cur = stack.pop()
if not visited[cur]:
visited[cur] = True # 将当前顶点标记为已访问
print(graph.vertex[cur], end=' ') # 输出当前顶点的值
# 将当前顶点的未访问过的邻居加入栈中
for i in range(graph.verNum):
if graph.edge[cur][i] == 1 and not visited[i]:
stack.append(i)
```
其中,`graph` 参数是一个 `adjMatrixGraph` 对象,`start` 参数是起始顶点的下标。该函数首先初始化所有顶点为未访问状态,然后将起始顶点加入栈中。接着进入循环,每次取出栈顶元素作为当前访问的顶点,将其标记为已访问,并输出其值。然后将当前顶点的未访问过的邻居加入栈中,继续循环直到栈为空。
class adjMatrixGraph: # 构造方法,n个顶点m条边 def init(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表,默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 根绝上面代码编写一个广度优先搜索得函数
以下是基于邻接矩阵的广度优先搜索算法实现:
```
from queue import Queue
class adjMatrixGraph:
# 构造方法,n个顶点m条边
def __init__(self, n, m):
self.verNum = n # 顶点数
self.edgeNum = m # 边数
self.vertex = [0] * n # 顶点列表
self.edge = [[0 for i in range(self.verNum)] for j in range(self.verNum)] # 邻接矩阵二维列表
self.vis = [False] * n # 顶点的访问列表,默认没访问过
def addVertex(self, ls):
# 添加顶点列表
self.vertex = ls
def addEdge(self, fr, to):
# 添加边(fr,to)
ifr = self.vertex.index(fr) # 起点下标
ito = self.vertex.index(to) # 终点下标
self.edge[ifr][ito] = self.edge[ito][ifr] = 1 # 邻接矩阵
# 广度优先搜索
def BFS(self, start):
if start not in self.vertex:
return None
start_index = self.vertex.index(start)
q = Queue()
q.put(start_index)
self.vis[start_index] = True
while not q.empty():
cur = q.get()
print(self.vertex[cur], end=' ')
for i in range(self.verNum):
if self.edge[cur][i] and not self.vis[i]:
q.put(i)
self.vis[i] = True
```
其中,BFS方法为广度优先搜索算法实现。它首先判断起始顶点是否存在于顶点列表中,然后初始化队列并将起始顶点加入队列,将其标记为已访问。接下来,开始循环处理队列,取出队首元素,输出其对应的顶点,然后遍历该顶点的所有邻接点,将其加入队列,并标记为已访问。直到队列为空,搜索结束。
阅读全文