一、题目要求：

二、实验原理及内容：

所采用的数据结构：栈(通过python的列表类型pop来模拟)

所采用的的存储结构：字典(存放某一个结点的所有相邻的结点)、集合set（去重+检测是否走过该节点）

函数：

• def init():

'''函数功能:完成邻接矩阵的初始化'''

• def GetReachableMatrix(A,n):  #参数A：邻接矩阵  参数n:结点个数

'''函数功能:求可达性矩阵'''

• def GetOddDegree(matrix,n):

'''函数功能:通过邻接矩阵获取到每一个节点的度数，在保证连通性的前提下，通过奇数度节点直接判别出欧拉路or欧拉回路'''

• def GetGraph(matrix,n):

''' 函数功能:由邻接矩阵求出一个字典：每一个节点 映射 相邻节点 '''

• def DFS(graph,start):  #参数 graph是邻接节点的一个字典   参数start是起始点

''' 函数功能:通过dfs算法求出欧拉（回）路 '''

时间复杂度：O（n²）

实验思路：

• 欧拉（回）路前提：可达性矩阵元素均为1
• 若不满足1直接结束。若满足：求出奇数度节点的个数，等于2->欧拉路 等于0->欧拉回路
• 在②的前提下，深度优先搜索，找出一笔画的路径并输出

三、源代码

import numpy as np
from random import randint
'''函数功能:完成邻接矩阵的初始化'''
def init():
     n,m=eval(input("请输入图的结点数和边数(逗号隔开):"))
     matrix = np.zeros((n, n), dtype=int)  #图的邻接矩阵
     m_list=(input("请输入有关联关系的两个结点1,3(每一对中间用空格隔开)：例如  1,5 1,6 在无向图中表示结点1和节点5、6是相互可达的\n")).split(' ')
     for i in m_list:    #根据用户的输入，完成邻接矩阵的初始化
          matrix[eval(i[0])-1,eval(i[-1])-1]=1;
          matrix[eval(i[-1])-1, eval(i[0])-1] = 1; #无向图的邻接矩阵是对称的    减去1是为了与矩阵的下标对应
     return matrix,n
 
'''函数功能:求可达性矩阵'''
def GetReachableMatrix(A,n):  #参数A：邻接矩阵  参数n:结点个数
     temp = np.array(A, dtype=int)
     C=np.zeros((n,n),dtype=int)  #B是可达性矩阵
     for i in range(n):
          C+=temp
          temp=np.dot(temp,A)
     t=np.array(C,dtype=bool)
     B=np.array(t,dtype=int)
     return B
 
'''函数功能:通过邻接矩阵获取到每一个节点的度数，在保证连通性的前提下，通过奇数度节点直接判别出欧拉路or欧拉回路'''
def GetOddDegree(matrix,n):
     count=0 #表示奇数度的大小
     for i in range(n):
          sum=0
          for j in range(n):
               sum+=matrix[i][j]
          if sum%2 !=0:# 说明是奇数
               count+=1
     return count
 
''' 函数功能:由邻接矩阵求出一个字典：每一个节点 映射 相邻节点 '''
def GetGraph(matrix,n):
     graph=dict()  #生成一个空字典
     for i in range(n):
          graph["v"+str(i+1)]=list()#映射的对象是一个列表
          for j in range(n):
               if matrix[i][j]==1:
                    #向列表中添加邻接节点
                    graph["v"+str(i+1)].append("v"+str(j+1))
     return graph
 
def DFS(graph,start):  #参数 graph是邻接节点的一个字典   参数start是起始点
     stack=[]  #当栈用
     seen=set() #创建一个集合，查重用(判断这条路是否已经走过)+记录路径的作用
     print("一笔画路径为:",end="")
     stack.append(start)
     seen.add(start)
     while (len(stack)>0):
          vertx=stack.pop()  #默认是从栈顶取出
          node=graph[vertx]
          for i in node:
               if i not in seen:#确保之前没有走过该节点
                    stack.append(i)
                    seen.add(i)
          print(vertx+"->",end="")
     print("\b\b")
 
if __name__=='__main__':
     matrix,Node=init()  #initial info
     templateMatrix=np.ones((Node,Node),dtype=int)  #连通性阵的可达性矩阵的模板 全是1 用于比较
     ReachhableMatrix=GetReachableMatrix(matrix,Node)  #求可达性矩阵
     graph=GetGraph(matrix,Node)    #得到每一个节点的邻接节点构成的字典dict
     r=randint(0,Node)
     print("邻接矩矩阵为:\n",matrix)
 
     if (templateMatrix==ReachhableMatrix).all():
          if GetOddDegree(matrix,Node)==0:#奇数度节点为0个，说明是欧拉图
               DFS(graph, "v"+str(Node))
               print("是欧拉图-->可以一笔画")
          elif GetOddDegree(matrix,Node):
               DFS(graph, "v"+str(Node))
               print("是半欧拉图-->可以一笔画")
          else:
               print("既不是欧拉路，也不是欧拉回路-->不能一笔画")
     else:
          print("非连通图，既不是半欧拉图，也不是欧拉图-->不能一笔画")

四、写在最后

大一下还没有学dfs

        推荐一个b站的相关资源，快速上手bfs和dfs(用python)

[Python] BFS和DFS算法（第3讲）—— 从BFS到Dijkstra算法_哔哩哔哩_bilibili从BFS到Dijkstra算法Dijkstra算法是BFS的升级版。当一个图中的每条边都加上权值后，BFS就没办法求一个点到另一个点的最短路径了。这时候，需要用到Dijkstra算法。从最基本原理上讲，把BFS改成Dijkstra算法，只需要把“队列”改成“优先队列”就可以了。这段视频主要给大家介绍BFS转Dijkstra的具体过程，包括优先队列的用法、代码实现。希望对大家有一定帮助。, 视频播放量 44702、弹幕量 633、点赞数 1175、投硬币枚数 1210、收藏人数 1260、转发人数 174, 视频作者 正月点灯笼, 作者简介 海外留学党一名，目前在新南威尔士大学读博，大家也可以认为我是无业游民。平时爱好讲讲课，录点教学视频。，相关视频：[Python] BFS和DFS算法（第1讲），[Python] BFS和DFS算法（第2讲），【neko】DFS与BFS【算法编程#5】，【算法】最短路径查找—Dijkstra算法，BFS广搜解决迷宫问题，图的存储（邻接表）与遍历（BFS），【算法】图的遍历—BFS和DFS，图Graph, 深度优先遍历(DFS), 广度优先遍历(BFS)【数据结构和算法入门9】，【北京大学】数据结构与算法Python版（完整版），DFS深搜与BFS广搜 C++代码详解https://www.bilibili.com/video/BV1ts41157Sy?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click