hello-algo/zh-hant/codes/swift/chapter_graph/graph_dfs.swift
Yudong Jin 870e3e5cb2
Bug fixes and improvements (#1318)
* Sync zh and zh-hant versions

* Update en/README.md

* Add a Q&A for chapter of introduction

* Update the callout headers

* Sync zh ang zh-hant versions

* Bug fixes
2024-04-30 15:52:05 +08:00

54 lines
1.7 KiB
Swift
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: graph_dfs.swift
* Created Time: 2023-02-21
* Author: nuomi1 (nuomi1@qq.com)
*/
import graph_adjacency_list_target
import utils
/* */
func dfs(graph: GraphAdjList, visited: inout Set<Vertex>, res: inout [Vertex], vet: Vertex) {
res.append(vet) //
visited.insert(vet) //
//
for adjVet in graph.adjList[vet] ?? [] {
if visited.contains(adjVet) {
continue //
}
//
dfs(graph: graph, visited: &visited, res: &res, vet: adjVet)
}
}
/* */
// 使便
func graphDFS(graph: GraphAdjList, startVet: Vertex) -> [Vertex] {
//
var res: [Vertex] = []
//
var visited: Set<Vertex> = []
dfs(graph: graph, visited: &visited, res: &res, vet: startVet)
return res
}
@main
enum GraphDFS {
/* Driver Code */
static func main() {
/* */
let v = Vertex.valsToVets(vals: [0, 1, 2, 3, 4, 5, 6])
let edges = [
[v[0], v[1]], [v[0], v[3]], [v[1], v[2]],
[v[2], v[5]], [v[4], v[5]], [v[5], v[6]],
]
let graph = GraphAdjList(edges: edges)
print("\n初始化後,圖為")
graph.print()
/* */
let res = graphDFS(graph: graph, startVet: v[0])
print("\n深度優先走訪DFS頂點序列為")
print(Vertex.vetsToVals(vets: res))
}
}