This is a 2-part series on graph data structures. In this first part, we are going to learn about the various parts and terminologies used in graphs; we will look at the types, uses and applications of graphs. In part 2 we shall look at graph representation and build a graph in Javascript code.
Definition
A graph is a non-linear data structure made of nodes (vertices) and edges that connect these nodes to simulate a network. Graphs are used to show the relationship between sets of data.
Terminologies
The following are some of the commonly used terms in graph data structures:
Vertex: This refers to a singular node in a graph; a vertex can be any form of data; a name, number, or co-ordinate. [M,A,Q,Z,N] are vertices. The plural for a vertex is vertices.
Edges: An edge is the line connecting 2 nodes; edges have a start vertex and an end vertex. There are 2 main types of edges directed and undirected.
A direct edge is only accessible from the start vertex and is not acknowledged by the end vertex. An undirected edge is accessible and acknowledged by both the start and end vertices.
Weighted Edge: A-weighted edge is an edge that has a value/cost tied to it. They are used to convey the value of the relationship between vertices in a graph.
Degree: A degree refers to the total number of edges (directed or undirected) connected to a vertex. In the above image, we can see that the degree of vertex {Q} is 4.
Indegree: This refers to the number of incoming directed edges of a vertex. In the above image, we can see that the Indegree of vertex {B} is 2.
Outdegree: This refers to the number of out-going directed edges of a vertex. In the above image, we can see that the outdegree of vertex {V} is 3.
Adjacency: Vertices that are connected by an edge are said to be adjacent (next) to one another. In the above image vertex {A} is adjacent to {Q}, and vertex {M} is not adjacent to {Z}.
Types Of Graph Data Structure
Undirected Graph: An undirected graph uses undirected edges to connect its vertices. Connections in undirected graphs are acknowledged by both vertices. An undirected graph can be traversed in any direction, meaning vertex {X} can lead to vertex {T} and vice versa.
Directed Graph: A directed graph uses directed edges to connect its vertices. Connections in directed graphs are one-sided and are only acknowledged by the starting vertex. Directed graphs can be traversed in a forward direction; meaning vertex {Q} can lead to vertex {N} but the reverse is not possible.
Weighted Graph: A weighted graph uses weighted edges to connect its vertices. Connections in a weighted graph are given a value/cost to convey a level of importance. Weighted graphs can be directed or undirected.
Graph Traversal
There are 2 main graph traversal algorithms Breadth-first-traversal and Depth-first-Traversal. These traversal methods are also used in tree data structures ; trees are considered a form of graph data structure. You can read about these traversal methods in my previous article here.
Uses And Real-life Application Of Graph Data Structure
- Undirected Graphs are used to represent networks and are used on social media platforms such as Facebook to represent connections like friendships.
- Webpages operate like a directed graph in which links are the edges/connections between pages. A link leading from one webpage to another is a type of directed edge because the other page will not have a link leading to the origin page.
- Weighted Graphs can be used to represent maps, which is how Google maps works, by using weighted graphs and setting the value of the edges to be the distance between locations.
Conclusion
In my next article we are going to look at graph representation, and implement a graph in Javascript.
