Content ：
Yes, yes. n An undirected graph with nodes , Judge whether it can be drawn by one stroke .
requirement ：
For given n An undirected graph with nodes , Determine the Eulerian graph and semi Eulerian graph , If it is an Euler or semi Euler , Then all Euler （ return ） road .
The adopted data structure ： Stack ( adopt python List type of pop To simulate the )
The storage structure used ： Dictionaries ( Store all adjacent nodes of a node )、 aggregate set（ duplicate removal + Check whether you have passed the node ）
function ：
''' The functionality : Complete the initialization of adjacency matrix '''
''' The functionality : Finding reachability matrix '''
''' The functionality : The degree of each node is obtained through the adjacency matrix , On the premise of ensuring connectivity , Euler road can be directly identified by odd degree nodes or Euler circuit '''
''' The functionality : Find a dictionary from adjacency matrix ： Every node mapping Adjacent nodes '''
''' The functionality : adopt dfs The algorithm solves Euler （ return ） road '''
Time complexity ：O（n²）
Experimental thinking ：
import numpy as np
from random import randint
''' The functionality : Complete the initialization of adjacency matrix '''
def init():
n,m=eval(input(" Please enter the number of nodes and edges of the graph ( commas ):"))
matrix = np.zeros((n, n), dtype=int) # The adjacency matrix of a graph
m_list=(input(" Please enter two nodes that are related 1,3( Each pair is separated by a space )： for example 1,5 1,6 Represent nodes in an undirected graph 1 And nodes 5、6 It's accessible to each other \n")).split(' ')
for i in m_list: # According to the user's input , Complete the initialization of adjacency matrix
matrix[eval(i[0])-1,eval(i[-1])-1]=1;
matrix[eval(i[-1])-1, eval(i[0])-1] = 1; # The adjacency matrix of an undirected graph is symmetric subtract 1 To correspond to the subscript of a matrix
return matrix,n
''' The functionality : Finding reachability matrix '''
def GetReachableMatrix(A,n): # Parameters A： Adjacency matrix Parameters n: Number of nodes
temp = np.array(A, dtype=int)
C=np.zeros((n,n),dtype=int) #B Is the reachability matrix
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
''' The functionality : The degree of each node is obtained through the adjacency matrix , On the premise of ensuring connectivity , Euler road can be directly identified by odd degree nodes or Euler circuit '''
def GetOddDegree(matrix,n):
count=0 # Indicates the size of the odd degree
for i in range(n):
sum=0
for j in range(n):
sum+=matrix[i][j]
if sum%2 !=0:# The description is odd
count+=1
return count
''' The functionality : Find a dictionary from adjacency matrix ： Every node mapping Adjacent nodes '''
def GetGraph(matrix,n):
graph=dict() # Generate an empty dictionary
for i in range(n):
graph["v"+str(i+1)]=list()# The mapped object is a list
for j in range(n):
if matrix[i][j]==1:
# Add adjacency nodes to the list
graph["v"+str(i+1)].append("v"+str(j+1))
return graph
def DFS(graph,start): # Parameters graph Is a dictionary of adjacent nodes Parameters start It's the starting point
stack=[] # Used as a stack
seen=set() # Create a collection , Check reuse ( Judge whether this road has been crossed )+ The role of the record path
print(" A stroke path is :",end="")
stack.append(start)
seen.add(start)
while (len(stack)>0):
vertx=stack.pop() # The default is to take it from the top of the stack
node=graph[vertx]
for i in node:
if i not in seen:# Make sure you haven't walked through this node before
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) # Template of reachability matrix of connectivity matrix Is full of 1 For comparison
ReachhableMatrix=GetReachableMatrix(matrix,Node) # Finding reachability matrix
graph=GetGraph(matrix,Node) # Get the dictionary composed of adjacent nodes of each node dict
r=randint(0,Node)
print(" The adjacency matrix is :\n",matrix)
if (templateMatrix==ReachhableMatrix).all():
if GetOddDegree(matrix,Node)==0:# Odd degree nodes are 0 individual , The explanation is eulatus
DFS(graph, "v"+str(Node))
print(" It's eulatu --> One stroke ")
elif GetOddDegree(matrix,Node):
DFS(graph, "v"+str(Node))
print(" It's semi Euler --> One stroke ")
else:
print(" Not eulalu , Nor is it an Euler circuit --> Not a stroke ")
else:
print(" Unconnected graph , It is neither semi Eulerian nor semi Eulerian , Nor is it eulatus --> Not a stroke ")
I haven't learned since I was a freshman dfs
Recommend a b Related resources of the station , Quick start bfs and dfs( use python)
[Python] BFS and DFS Algorithm （ The first 3 speak ）—— from BFS To Dijkstra Algorithm _ Bili, Bili _bilibili from BFS To Dijkstra Algorithm Dijkstra The algorithm is BFS Upgraded version . When each edge in a graph is weighted ,BFS There is no way to find the shortest path from one point to another . Now , Need to use Dijkstra Algorithm . In the most basic principle , hold BFS Change to Dijkstra Algorithm , Only need to “ queue ” Change to “ Priority queue ” That's all right. . This video mainly introduces BFS turn Dijkstra The specific process of , Including the usage of priority queue 、 Code implementation . I hope it will be helpful to you ., Video playback volume 44702、 The amount of bullet screen 633、 Number of likes 1175、 The number of coins dropped 1210、 Number of collectors 1260、 Forwarding number 174, Video author The first month lights lanterns , Author's brief introduction A member of the overseas study party , Currently, I am a doctoral student at the University of New South Wales , You can also think of me as a jobless vagrant . Usually, I like to lecture , Record some teaching videos ., Related video ：[Python] BFS and DFS Algorithm （ The first 1 speak ）,[Python] BFS and DFS Algorithm （ The first 2 speak ）,【neko】DFS And BFS【 Algorithm programming #5】,【 Algorithm 】 Shortest path lookup —Dijkstra Algorithm ,BFS Search widely to solve the maze problem , Figure of the storage （ Adjacency list ） And traversal （BFS）,【 Algorithm 】 Graph traversal —BFS and DFS, chart Graph, Depth-first traversal (DFS), Breadth first traversal (BFS)【 Introduction to data structures and algorithms 9】,【 Peking University, 】 Data structure and algorithm Python edition （ Full version ）,DFS Deep search and BFS Guang Shu C++ Code details 
https://www.bilibili.com/video/BV1ts41157Sy?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click
