一、題目要求：

內容：

對具有n個結點的無向圖，判斷其能否被一筆畫。

要求：

對給定n個結點的無向圖，進行歐拉圖和半歐拉圖的判定，若是歐拉圖或半歐拉圖，則輸出所有的歐拉（回）路。

二、實驗原理及內容：

所采用的數據結構：棧(通過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