Graph — Part 1 — Basics
This is a series of tutorials on Graph data structure used widely in software applications. I will cover basic definition of graph, terminology, various graph representations with implementation in Java with complete code, graph traversal methods and applications of graphs in Computer science. Stay tuned.
What is a Graph?
A graph is a data structure used to represent a collection of objects that are connected in some way.
Graphs are used to model a variety of real-world phenomena, such as social networks, computer networks, transportation networks, and so on.
For example, nodes and edges could represent
- Facebook users and their Friendships,
- Computers and Network cables,
- Cities and Highways
Basic Terminology
Vertices/Nodes
The objects in a graph are called vertices or nodes.
Each node is assigned a unique identifier, called a label, that distinguishes it from other nodes in the graph.
Edge
The connections between nodes are called edges.
An edge can be directed (pointing from one node to another) or undirected (not pointing in any direction).
Directed/Undirected Graphs
In a directed graph, the edges have a direction associated with them, while in an undirected graph, the edges do not have a direction.
Weighted/Unweighted Graphs
A graph can be weighted or unweighted, depending on whether or not the edges have a weight associated with them.
Neighbors
When two vertices are connected to each other, they are called neighbors.
E.g. In the above Weighted Undirected Graph, neighbors of the Vertex 0 are vertices 1, 2 and 3.
Types of Graphs
Tree
A tree is a special type of graph where each node has at most one parent, and there is exactly one root node (a node with no parent).
Acyclic Graph
An acyclic graph is a graph that contains no cycles (i.e., no paths that start and end at the same node).
Complete Graph
A complete graph is a graph where every pair of distinct nodes is connected by an edge.
Bipartite Graph
A bipartite graph is a graph whose nodes can be divided into two disjoint sets such that all edges connect a node in one set to a node in the other set.
Graph Representations
To represent a graph in code, you have to store information about
- The Vertices which are part of the given Graph and,
- The Edges which connect vertices
Vertices can be represented by primitive data type such as Integer or Object such as String or user defined object. Edges can be represented by a value (e.g. 1 for connected, 0 for not connected) in some matrix or each vertex can map to list of other vertices which it is connected to.
There are two commonly used ways to represent a graph: adjacency matrix and adjacency list.
Adjacency Matrix
An adjacency matrix is a 2D array where the rows and columns correspond to the nodes in the graph.
The value at index (i,j) in the matrix represents the connection between nodes i and j (in weighted graph, this value could also represent the weight of the edge between nodes i and j).
Adjacency List
An adjacency list is a data structure that stores the neighbors (connections) of each node in a list or set.
