羅德興老師的教學歷程檔案 - 中華科技大學數位化學習歷程

# 以陣列儲存圖形，做深度優先搜尋法(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()

Unit 8 圖形 (Graph)