What is a graph?

A graph is an abstract data type that represents vertices and edges that connect those vertices.

Source

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

Thank you for reading! 😊