Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Naive Graphs Practice using Adjacency Matrix instead of normal linked lists
import Cocoa
class Graph {
let size: Int
private var nodes: [[Int]]
init(size: Int) {
self.size = size
nodes = Array<[Int]>(repeating: [] , count: size)
}
func walkBFS(from target: Int) {
var nodesToVisit = [Int]()
var visitedNodes = Set<Int>()
nodesToVisit += nodes[target]
visitedNodes.insert(target)
print("Starting at: \(target)")
while let next = nodesToVisit.first {
print("Visiting Node: \(next)")
visitedNodes.insert(next)
nodesToVisit = Array(nodesToVisit.dropFirst())
for item in nodes[next] where !visitedNodes.contains(item) {
if nodesToVisit.contains(item) {
continue
}
nodesToVisit.append(item)
}
}
}
func walkDFS(from target: Int) {
var nodesToVisit = [Int]()
var visitedNodes = Set<Int>()
nodesToVisit += nodes[target]
visitedNodes.insert(target)
print("Starting at: \(target)")
while let next = nodesToVisit.last {
print("Visiting Node: \(next)")
visitedNodes.insert(next)
nodesToVisit = Array(nodesToVisit.dropLast())
for item in nodes[next] where !visitedNodes.contains(item) {
if nodesToVisit.contains(item) {
continue
}
nodesToVisit.append(item)
}
}
}
func attach(nodeA: Int, nodeB: Int) {
nodes[nodeA].append(nodeB)
nodes[nodeB].append(nodeA)
}
func show() {
for (index, item) in nodes.enumerated() {
print("Row: \(index) || \(item)")
}
}
}
let m = Graph(size: 8)
m.attach(nodeA: 0, nodeB: 3)
m.attach(nodeA: 3, nodeB: 1)
m.attach(nodeA: 3, nodeB: 2)
m.attach(nodeA: 1, nodeB: 0)
m.attach(nodeA: 1, nodeB: 5)
m.show()
print("------------------- BFS -----------------")
m.walkBFS(from: 0)
print("------------------- DFS -----------------")
m.walkDFS(from: 0)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment