# Graphs

A graph is a data structure that shows a relationship (e.g., connection) between two or more objects. Because of their flexibility, graphs are one of the most widely used structures in modern computing. Popular tools and services like online maps, social networks, and even the Internet as a whole are based on how objects relate to one another. In this chapter, we’ll highlight the key features of graphs and will demonstrate how to create a basic `graph`

with Swift.

### THE BASICS

As discussed, a graph is a model that shows how objects relate to one another. Graph objects are usually referred to as `nodes`

or `vertices`

. While it would be possible to build a graph with a single node, models that contain multiple `vertices`

better represent real-world applications.

Graph objects relate to one another through connections called `edges`

. Depending on your requirements, a `vertex`

could be linked to one or more objects through a series of `edges`

. It’s also possible to create a `vertex`

without `edges`

. Here are some basic `graph`

configurations:

*An undirected graph with two vertices and one edge.*

*An undirected graph with three vertices and three edges.*

*An undirected graph with four vertices and three edges.*

### DIRECTED VS. UNDIRECTED

As shown, there are many ways to configure a `graph`

. An additional option is to set the model to be either *directed* or *undirected*. The examples above represent undirected graphs. In other words, the connection between vertices `A`

and `B`

is equivalent to the connection between vertices `B`

and `A`

. Social networks are a great example of undirected graphs. Once a request is accepted, both parties (e.g. the sender and recipient) share a mutual connection.

A service like Google Maps is a great example of a directed graph. Unlike an undirected graph, *directed* graphs only support a one-way connection between source `vertices`

and their destinations. So, for example, vertex `A`

could be connected to `B`

, but `A`

wouldn’t necessarily be reachable through `B`

. To show the varying relationship between `vertices`

, directed graphs are drawn with lines and arrows.

### EDGES & WEIGHTS

Regardless of graph type, it’s common to represent the level of connectedness between vertices. Normally associated with an `edge`

, the `weight`

is a numerical value tracked for this purpose. As we’ll see, modeling of graphs with `edge`

weights can be used to solve a variety of problems.

*A directed graph with three vertices and three weighted edges.*

### THE VERTEX

With our understanding of graphs in place, let’s build a basic directed graph with `edge`

weights. To start, here’s a data structure that represents a `vertex`

:

//a basic vertex data structure public class`Vertex`

{ var key: String? var neighbors: Array<`Edge`

> init() { self.neighbors = Array<`Edge`

>() } }

As we’ve seen with other structures, the `key`

represents the data to be associated with a `class`

instance. To keep things straightforward, our `key`

is declared as a `string`

. In a production app, the key type would be replaced with a generic placeholder, `<T>`

. This would allow the `key`

to store any object like an `integer`

, account or profile.

### ADJACENCY LISTS

The `neighbors`

property is an `array`

that represents connections a `vertex`

may have with other vertices. As discussed, a `vertex`

can be associated with one or more items. This list of neighboring items is sometimes called an adjacency list and can be used to solve a variety of problems. Here’s a basic data structure that represents an `edge`

:

//a basic edge data structure public class`Edge`

{ var neighbor:`Vertex`

var weight:`Int`

init() { weight = 0 self.neighbor =`Vertex`

() } }

### BUILDING THE GRAPH

With our `vertex`

and `edge`

objects built, we can use these structures to construct a `graph`

. To keep things straightforward, we’ll focus on the essential operations of adding and configuring `vertices`

.

//a default directed graph canvas public class`SwiftGraph`

{ private var canvas: Array<`Vertex`

> public var isDirected:`Bool`

init() { canvas = Array<`Vertex`

>() isDirected = true } //create a new vertex func addVertex(key:`String`

) ->`Vertex`

{ //set the key var childVertex:`Vertex`

=`Vertex`

() childVertex.key = key //add the vertex to the graph canvas canvas.append(childVertex)`return`

childVertex } }

The function `addVertex`

accepts a `string`

which is used to create a new `vertex`

. The `SwiftGraph`

class also has a private property named `canvas`

which is used to manage all `vertices`

. While not required, the `canvas`

can be used to track and manage vertices with or without `edges`

.

### MAKING CONNECTIONS

Once a `vertex`

is added, it can be connected to other vertices. Here’s the process of establishing an `edge`

:

//add an edge to source vertex func addEdge(source:`Vertex`

, neighbor:`Vertex`

, weight:`Int`

) { //create a new edge var newEdge =`Edge`

() //default properties newEdge.neighbor = neighbor newEdge.weight = weight source.neighbors.append(newEdge) //check for undirected graph if (isDirected == false) { //create a new reversed edge var reverseEdge =`Edge`

() //establish the reversed properties reverseEdge.neighbor = source reverseEdge.weight = weight neighbor.neighbors.append(reverseEdge) } }

The function `addEdge`

receives two vertices, identifying them as `source`

and `neighbor`

. Since our model defaults to a directed graph, a new `edge`

is created and is added to the *adjacency list* of the `source`

vertex. For an undirected graph, an additional `edge`

is created and added to the `neighbor`

vertex.

As we’ve seen, there are many components to graph theory. In the next section, we’ll examine a popular problem (and solution) with graphs known as shortest paths.