Data Structures: Graphs I

Data Structures: Graphs I

An introductory article on graph data structures.

·

4 min read

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.

Let's do this

 

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:

Graph Vertices And Vertex

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.

 

Graph with edge

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.

 

Directed and Undirected Edges

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 Graph Weighted Edges

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.

 

Graph Degree Vertex Degree

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 Graph Outdegree Graph

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.

 

Graph data structure

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, Bi-directional graph, diagram

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, Digraph, Diagram

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 Diagram, Bi-graph

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

  Social Media Graph, Undirected Friendship Graph

  • Undirected Graphs are used to represent networks and are used on social media platforms such as Facebook to represent connections like friendships.

 

directed Webpage Graph, Webpage graph diagram

  • 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.

Map Graph, Map Weighted Graph

  • 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.

See you soon