|
羅德興老師的教學歷程檔案 - 112-2 資料結構 (2024年) - Unit 8 圖形 (Graph) |
|
|
|
|
Unit 8 圖形 (Graph)1. 範例與作業一 # 以陣列儲存圖形，做 深度優先搜尋法(DFS) by L.D.S. on 2023/05/29 # Ex 8-1 以 廣度優先搜尋法(BFS)拜訪各頂點 print("===============程式描述========================") print("= 程式名稱：ch7-5-1.py =") print("= 程式目的：深度優先搜尋法(DFS) =") print("==============================================") N=8 #定義頂點總數 Edge=10 #定義邊的總數 G=[[0 for i in range(8)] for j in range(8)] Gnode =[[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 8], [5, 8], [6, 8], [7, 8]]; Visited=[0 for i in range(8)] #記錄已被拜訪過的節點 row, column, i=0,0,0 #設定節點都尚未被拜訪 for i in range(0,N): Visited[i] = 0 #將二維陣列的內容轉換成相鄰陣列 R_node=0 #相鄰陣列預設為0 for row in range(0,N): for column in range(0,N): G[row][column]=0 #設定頂點的起點 for row in range(0,Edge): R_node = Gnode[row][0] - 1 for column in range(0,2): G[R_node][Gnode[row][column] - 1] = 1 #設定頂點的終點 for row in range(0,Edge): R_node = Gnode[row][1] - 1 for column in range(0,2): G[R_node][Gnode[row][column] - 1] = 1 #對角線設定為0 for row in range(0,N): for column in range(0,N): if(row == column): G[row][column]=0 def Create_Graph(): #建立圖形 print("圖形的相鄰 矩陣 內容如下:\n"); for row in range(0,N): for column in range(0,N): print("%3d" % G[row][column],end="") print() def DFS(i): #深度優先搜尋法(DFS) j=0 Visited[i] = 1 print("v%d " % (i + 1),end="") for j in range(0,N): if(G[i][j] == 1): if (Visited[j]!=1): #判斷是否已經被拜訪過 DFS(j) Create_Graph() #建立圖形 print("=================輸出==================\n") print("深度優先搜尋法(DFS)拜訪頂點的順序為：\n") #印出走訪過程 DFS(0) #呼叫深度優先搜尋法(DFS) 2. 範例與作業二 # 使用字典(dict)將節點名稱轉成節點編號，將圖形資料結構以字典(dict)表示，最後使用深度優先搜尋，找出最長邊的個數。 # Using a Python dictionary to act as an adjacency list # https://favtutor.com/blogs/depth-first-search-python # Ex. 8-2.1 繪出該圖 # Ex. 8-2.2 使用 廣度優先搜尋 實作程式 graph = { '5' : ['3','7'], '3' : ['2', '4'], '7' : ['8'], '2' : [], '4' : ['8'], '8' : [] } visited = set() # Set to keep track of visited nodes of graph. def dfs(visited, graph, node): #function for dfs if node not in visited: print (node) visited.add(node) for neighbour in graph[node]: dfs(visited, graph, neighbour) # Driver Code print("Following is the Depth-First Search") dfs(visited, graph, '5') 3. 範例與作業 三 # # 以 Linked List 儲存圖形，做 深度優先搜尋法(DFS traversal) by L.D.S. on 2023/05/29 # Ex. 8-4.1 繪出該圖 (Hint: 為有向圖且有迴圈) # Ex. 8-4.2 再任意加上 5 個節點和邊 # Ex. 8-4.3 以 廣度優先搜尋法(BFS)拜訪各頂點 # https://www.geeksforgeeks.org/python-program-for-depth-first-search-or-dfs-for-a-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 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[v]= True print(v) # Recur for all the vertices adjacent to # this vertex for i in self.graph[v]: if visited[i] == False: self.DFSUtil(i, visited) # The function to do DFS traversal. It uses # recursive DFSUtil() def DFS(self): V = len(self.graph) #total vertices # Mark all the vertices as not visited visited =[False]*(V) # Call the recursive helper function to print # DFS traversal starting from all vertices one # by one for i in range(V): if visited[i] == False: self.DFSUtil(i, visited) # Driver code # Create a graph given in the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 4) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(2, 4) g.addEdge(3, 3) g.addEdge(4, 5) g.addEdge(5, 6) g.addEdge(6, 0) print ("以下是 深度優先搜尋法 Depth First Traversal") g.DFS()
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| 中華科技大學數位化學習歷程 - 意見反應 |  |
