What is a graph?
A graph is an abstract data type that represents vertices and edges that connect those vertices.
Implementation
A graph can be represented as a matrix with edges connecting each pair of vertices. For example, a graph with vertices 0, 1, 2, 3, 4 and edges between them can be represented as a matrix:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | false | true | false | false | true |
1 | true | false | true | true | true |
2 | false | true | false | true | false |
3 | false | true | true | false | true |
4 | true | true | false | true | false |
In Swift, you can use a list of lists (2D array) to represent the matrix:
[
[false, true, false, false, true],
[true, false, true, true, true],
[false, true, false, true, false],
[false, true, true, false, true],
[true, true, false, true, false]
]
In any cell where true
is found, the corresponding vertices are connected by an edge.
Code Example
final class Graph {
private(set) var graph: [[Bool]]
init(numVertices: Int) {
self.graph = Array(
repeating: Array(
repeating: false,
count: numVertices
),
count: numVertices
)
}
func addEdge(u: Int, v: Int) {
graph[u][v] = true
graph[v][u] = true
}
}
The addEdge
method takes u
and v
vertices and adds an edge between them by setting the corresponding cells to true
. There are two cells in the matrix for each pair of vertices. For example, (0, 1) corresponds to these cells:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
0 | false | true | false | false | false |
1 | true | false | false | false | false |
2 | false | false | false | false | false |
3 | false | false | false | false | false |
4 | false | false | false | false | false |