Adjacency List and Matrix Representations

Introduction to Graphs and its Representations

What is a Graph?

A Graph is a data structure consisting of a finite set of vertices, called nodes, and a set of edges that are links between the vertices.

The edges of a graph are represented in ordered or unordered pairs depending on whether the graph is directed or undirected.

These are non-linear structures. The fundamental characteristic a graph has is that the data does not follow any order (at least not something as ordered as we see in arrays or linked lists).

Graphs have two distinct parts which are used to define them: vertices and edges.

Some graphs have many edges as compared to nodes, and are defined as dense graphs, whereas graphs with a smaller edge-to-node ratio are called a sparse graph.

Similarly, if the edges of a graph have a directional flow, the graph is defined as directed, while a graph with edges with no directional flow is undirected.

We will cover more on directed and undirected graphs in lesson 2 of this chapter.

Being able to identify these characteristics is very important since this directly affects how we go about representing a graph. But wait — how do ...