Graphs

Graphs are a collection of nodes that may or may not be connected to one another.

The nodes are called vertices, and the connections are called edges.

Important Properties of Graphs

Connectivity

A graph is considered connected when, for any two possible vertices, there always exists some path connecting them. In other words, no vertex is unreachable. A real-world example of a connected graph would be a network of tight-knit friends (the friendships being the edges).

Note: By default, we call these connections weakly connected because the connections have at least one direction. A graph is only strongly connected when the paths that connect any two vertices are always bi-directional: you can get from vertex 1 to vertex 2 just as easily as you can get from vertex 2 to vertex 1.

On the other hand, if there are unreachable vertices, a graph is considered disconnected. A real-world example would be a group that includes one person that has no friends (so their vertex has no edges).

Direction

A graph is considered directed when its edges point from one vertex to another, i.e., its edges can be represented as arrows. A real-world example of a directed graph would be a network of airports and their flight paths. Pearson Airport can have a flight path to Heathrow Airport, and that direction matters.

Otherwise, a graph is considered undirected when direction doesn't make sense for the edges, often because the relationship is always bi-directional. A real-world example of an undirected graph would be a network of friends because friendship always goes both ways.

Cycles

As a decent heuristic, a graph is considered cyclic when you have 3 or more vertices with edges that form a circle, allowing you to traverse around the same vertices infinitely. A real-world example of a cyclic graph would be a Wikipedia article that links to other articles that eventually link back to the original article.

Otherwise, a graph is considered acyclic.

Pro tip: When traversing through cyclic graphs, be aware that it's possible to get locked into an infinite loop. To avoid this problem, you have techniques available like marking vertices as visited and skipping the visited ones.

Representing a Graph in Code

Graphs are represented in code via adjacency lists. Adjacency lists are defined by 2 features:

• Store vertices/nodes with their values in a list or hash table

• In each vertex/node, keep a list of the vertices that it's connected to, i.e., the edges leading to the adjacent vertices

Space Complexity of Graphs

Generally, when storing a graph, there are V vertices and E edges. So, we say the space complexity of a graph is O(V + E).

Traversal operations

Traversal is the most common operation you're likely to perform for graphs, so it's valuable to dedicate a section to it.

Depth-first search

The fundamental idea of depth-first search is that you prioritize depth when traversing through a vertex's children. This means going deep before wide: going as deep as possible for one vertex before moving onto the next vertex.

For example, suppose vertex 1 has children 2, 3, and 4. By prioritizing depth, you focus on vertex 2 first, traversing down a straight line until you hit the last vertex in that line. Only when you're done do you move onto the next child vertex 3.

Breadth-first search

In contrast, the fundamental idea of breadth-first search is that you prioritize width when traversing through a vertex's children. This means going wide before deep: going as wide as possible between child vertices before diving deeper into any one particular vertex.

For example, suppose vertex 1 has children 2, 3, and 4. By prioritizing breadth, you move through vertices 2, 3, and 4 in sequence. Only when you're done do you start diving deeper into any particular vertex.

Time complexity of traversal

Without going into it too much yet, traversal ends up being O(V + E) just like space complexity because you can imagine having to traverse through every single vertex and every single edge.