Graph Data Structure

Overview

Finally, we arrive at Graphs!

In computer science, Graphs are an abstract concept that helps us represent various objects and the connections between them. There are many famous examples of graph use cases. For instance - social networks. Users are represented by nodes(verticies) and their friendships/connections are represented by edges.
Another use case is maps. Cities are vertices, roads are edges. You get the idea - it's a relatively simple but incredibly powerful concept.

I guess you saw the animation first so you already have an idea what the aforementioned 'vertices' and 'edges' words are. But let's take a more 'theoretical' look at the main components of a graph:

Vertices (or Nodes): Vertices are the fundamental building blocks of a graph. They represent individual objects, entities, or points in the graph. Each vertex holds unique information and can represent various objects depending on the context. As already mentioned in a social network graph, vertices could stand for users, while in maps, they might symbolize cities or intersections.

Edges (or Links): Edges establish connections between vertices in the graph. They represent relationships or interactions between the objects represented by the vertices. Edges can be undirected, indicating a mutual connection between two vertices (like a road), or directed, signifying a one-way relationship from one vertex to another (like a one-way plane ticket).

Adjacent Vertices: Two vertices are considered adjacent if they are connected by an edge. Like two cities closeby, connected by a road.

Adjacent Edges: The adjacent edges of a vertex are the edges directly connected to that vertex. In an undirected graph, these edges are bidirectional, connecting the vertex to its adjacent vertices. In a directed graph, the adjacent edges follow the direction of the edges, leading to or from the vertex (imagine two roads leading to one city).

Path: A path in a graph is a sequence of vertices and edges that connects two or more vertices. It represents a journey or route from one vertex to another. Paths can be simple (no repeated vertices, each vertex can be visited only once) or allow cycles (repeated vertices). The path and its length is determined by the number of edges it contains (in maps for instance, it's literally the path you take when you go on a roadtrip).

Now that we can imagine what a graph is and what its components are, another questions pop up - how to write down a graph?

A graph is generally denoted by G = {V, E}, where:

As expected by the letters - 'G' represents the Grapht itself.
'V' represents the set of vertices in the graph.
'E' represents the set of edges that connect pairs of vertices.
So the graph from the animation with edges A-B, B-C, and C-D, can be represented as follows:

G = {V, E}

V = {A, B, C, D}

E = {(A, B), (B, C), (C, D), (D,A)}

In this representation, V contains the set of vertices {A, B, C, D}, and E contains the set of edges {(A, B), (B, C), (C, D)}, where each edge is represented by an ordered pair of vertices.