8000 added BFS and DFS traversals · TheAlgorithms/Swift@c459742 · GitHub
[go: up one dir, main page]
Skip to content

Commit c459742

Browse files
dogra25130dogra25130
committed
added BFS and DFS traversals
1 parent 2ce2905 commit c459742

File tree

2 files changed

+139
-0
lines changed

2 files changed

+139
-0
lines changed

‎graph/BFS/BFS.swift

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
// MARK: - Basic requirement
2+
struct Edge {
3+
let from: Int
4+
let to: Int
5+
}
6+
7+
public class Node {
8+
var val: Int
9+
var neighbors: [Int]
10+
public init(_ val: Int) {
11+
self.val = val
12+
self.neighbors = []
13+
}
14+
}
15+
16+
// MARK: - BFS implementation
17+
func testBFS(edges: [Edge]) {
18+
19+
var graph = [Int: Node]()
20+
for edge in edges {
21+
graph[edge.from] = Node(edge.from)
22+
graph[edge.to] = Node(edge.to)
23+
}
24+
for edge in edges {
25+
graph[edge.from]?.neighbors.append(edge.to)
26+
graph[edge.to]?.neighbors.append(edge.from)
27+
}
28+
var visited: [Bool] = Array(repeating: false, count: graph.count + 1)
29+
var nodesOfCurrentLevel: [Int] = []
30+
31+
for node in 1...graph.count {
32+
if visited[node] == false {
33+
nodesOfCurrentLevel.append(node)
34+
while(nodesOfCurrentLevel.isEmpty == false) {
35+
var nodesOfNextLevel: [Int] = []
36+
let sizeOfQueue = nodesOfCurrentLevel.count
37+
for index in 0..<sizeOfQueue {
38+
let currNode = nodesOfCurrentLevel[index]
39+
if(visited[currNode] == true){
40+
continue
41+
}
42+
print("\(currNode) ")
43+
visited[currNode] = true
44+
guard let neighbors = graph[currNode]?.neighbors else { continue }
45+
for neigh in neighbors {
46+
if visited[neigh] == false {
47+
nodesOfNextLevel.append(neigh)
48+
}
49+
}
50+
}
51+
nodesOfCurrentLevel = nodesOfNextLevel
52+
}
53+
}
54+
}
55+
}
56+
57+
// MARK: - Input Graph
58+
func setup() {
59+
let edges = [
60+
Edge(from: 1, to: 2),
61+
Edge(from: 1, to: 4),
62+
Edge(from: 2, to: 3),
63+
Edge(from: 2, to: 4),
64+
Edge(from: 2, to: 5),
65+
Edge(from: 3, to: 5),
66+
Edge(from: 4, to: 5),
67+
Edge(from: 4, to: 6),
68+
Edge(from: 5, to: 6),
69+
Edge(from: 5, to: 6),
70+
Edge(from: 6, to: 7),
71+
]
72+
testBFS(edges: edges)
73+
}
74+
75+
setup()

‎graph/DFS/DFS.swift

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
// MARK: - Basic requirement
2+
struct Edge {
3+
let from: Int
4+
let to: Int
5+
}
6+
7+
public class Node {
8+
var val: Int
9+
var neighbors: [Int]
10+
public init(_ val: Int) {
11+
self.val = val
12+
self.neighbors = []
13+
}
14+
}
15+
16+
// MARK: - DFS Recursion
17+
func dfs(vertex: Int, visited: inout [Bool], graph: [Int: Node]) {
18+
if visited[vertex] == true {
19+
return
20+
}
21+
visited[vertex] = true
22+
print("\(vertex) ")
23+
guard let neighbors = graph[vertex] else { return }
24+
for neighbor in neighbors.neighbors {
25+
dfs(vertex: neighbor, visited: &visited, graph: graph)
26+
}
27+
}
28+
29+
func testDFS(edges: [Edge]) {
30+
var graph = [Int: Node]()
31+
for edge in edges {
32+
graph[edge.from] = Node(edge.from)
33+
graph[edge.to] = Node(edge.to)
34+
}
35+
for edge in edges {
36+
graph[edge.from]?.neighbors.append(edge.to)
37+
graph[edge.to]?.neighbors.append(edge.from)
38+
}
39+
var visited: [Bool] = Array(repeating: false, count: graph.count + 1)
40+
for node in 1...graph.count {
41+
if visited[node] == false {
42+
dfs(vertex: node, visited: &visited, graph: graph)
43+
}
44+
}
45+
}
46+
47+
48+
// MARK: - setup
49+
func setup() {
50+
let edges = [
51+
Edge(from: 1, to: 2),
52+
Edge(from: 1, to: 4),
53+
Edge(from: 2, to: 3),
54+
Edge(from: 2, to: 4),
55+
Edge(from: 2, to: 5),
56+
Edge(from: 3, to: 5),
57+
Edge(from: 4, to: 5),
58+
Edge(from: 4, to: 6),
59+
Edge(from: 5, to: 6),
60+
Edge(from: 5, to: 6),
61+
Edge(from: 6, to: 7),
62+
]
63+
testDFS(edges: edges)
64+
}

0 commit comments

Comments
 (0)
0