HelloKoding

Practical coding guides

Graph Data Structure

In this article, you will learn about Graph data structure types, representations, implementations and algorithms

A graph is a data structure used for organizing an interconnected network. It is a non-linear data structure consisting of a collection of vertices (nodes) and edges

  • A vertex represents an entity (object) (for example, student)
  • An edge is a line or arc that connects a pair of vertices in the graph, represents the relationship between entities

Examples

  • A computer network is a graph with computers are vertices and network connections between them are edges
  • The World Wide Web is a graph with web pages are vertices and hyperlinks are edges

Types of Graphs

Undirected vs Directed graph

  • An undirected graph has all edges that don’t have a direction, each edge can be travel in both directions (two-way relationships)
  • A directed graph has all edges that have a direction, each edge can be travel only in a single direction (one-way relationship)
Undirected vs Directed Graph

Cyclic vs Acyclic graph

  • A cyclic graph has at least a cycle (existing a path from at least one node back to itself)
  • An acyclic graph has no cycles
Cyclic vs Acyclic Graph

Connected vs Disconnected graph

  • A connected graph has no unreachable vertices (existing a path between every pair of vertices)
  • A disconnected graph has at least an unreachable vertex
Connected vs Disconnected Graph

Tree vs Forrest

  • A tree is a connected acyclic undirected graph
  • A forest is a graph with each connected component a tree
Tree vs Forest

Weighted vs Unweighted graph

  • A weighted graph has a weight attached to each edge (for example, the distance between two vertices)
  • An unweighted graph has no weight attached to each edge
Weighted vs Unweighted Graph

Vertex and Graph degree

Verex degree, denoted as deg(v), is a number of edges connected to the vertex. Graph degree, denoted as Δ(G), is the highest vertex degree in a graph

Vertex and Graph degree

In the above graph

  • deg(0) = 2, deg(1) = 2, deg(2) = 3, and deg(3) = 1
  • Δ(G) = 3

Vertex Indegree vs Outdegree

In a directed graph, vertex has an indegree and outdegree

  • An indegree, denoted as deg+(v), is a number of edges coming to the vertex
  • An outdegree, denoted as deg-(v), is a number of edges leaving the vertex
Vertex Indegree vs Outdegree

In the above graph

  • deg+(0) = 1, deg-(0) = 1
  • deg+(1) = 2, deg-(1) = 0
  • deg+(2) = 1, deg-(2) = 2
  • deg+(3) = 0, deg-(3) = 1

Graph Representations

There are several ways to represent a graph including the Edge list, Adjacency list, and Adjacency matrix. Let take this graph as an example

Graph Representations
  • An edge list is a list or array of all edges where each edge is represented by an array of two vertices

    In Java, an edge list can be represented by

int[][] graph = {
    {0, 1},
    {0, 2},
    {1, 2},
    {2, 3}
};
  • An adjacency list is a list or array where index represents a vertex and value represents a list of that vertex’s adjacents

    In Java, an adjacency list can be represented by

int[][] graph = {
    {1, 2},
    {0, 2},
    {0, 1, 3},
    {2}
};
  • An adjacency matrix is a matrix of 0s and 1s indicating the connection between two vertices in which the rows represent source vertices and columns represent destination vertices

    In Java, an adjacency matrix can be represented by

int[][] graph = {
    {0, 1, 1, 0},
    {1, 0, 1, 0},
    {1, 1, 0, 1},
    {0, 0, 1, 0}
};

Basic Graph operations

  • Add edge: add an edge between two vertices of the graph
  • Traversal: travel each vertex in the graph by using Depth-Frist and Breath-First Search

Graphs in Java

Java doesn’t have a default Graph implementation. However, you can use other supporting data structures to implement it

Undirected vs Directed Graph implementation example

  • Undirected graph implementation example with an adjacency list

GraphUndirectedByAdjacencyList.java

package com.hellokoding.datastructure.graph;

import java.util.ArrayList;
import java.util.List;

public class GraphUndirectedByAdjacencyList {
    private int V;
    private List<List<Integer>> adjacencyList;

    public GraphUndirectedByAdjacencyList(int V) {
        this.V = V;

        adjacencyList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public Integer getV() {
        return this.V;
    }

    public List<List<Integer>> getAdjacencyList() {
        return this.adjacencyList;
    }

    public void addEdge(int source, int dest) {
        adjacencyList.get(source).add(dest);
        adjacencyList.get(dest).add(source);
    }

    public void printAdjacencyList() {
        for (int i = 0; i < V; i++) {
            System.out.printf("Adjacency list of vertex %d is %s %s", i,
                adjacencyList.get(i), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphUndirectedByAdjacencyList graph = new GraphUndirectedByAdjacencyList(3);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.printAdjacencyList();
    }
}
  • Directed graph implementation example with an adjacency list

GraphDirectedByAdjacencyList.java

package com.hellokoding.datastructure.graph;

import java.util.ArrayList;
import java.util.List;

public class GraphDirectedByAdjacencyList {
    private int V;
    private List<List<Integer>> adjacencyList;

    public GraphDirectedByAdjacencyList(int V) {
        this.V = V;

        adjacencyList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public Integer getV() {
        return this.V;
    }

    public List<List<Integer>> getAdjacencyList() {
        return this.adjacencyList;
    }

    public void addEdge(int source, int dest) {
        adjacencyList.get(source).add(dest);
    }

    public void printAdjacencyList() {
        for (int i = 0; i < V; i++) {
            System.out.printf("Adjacency list of vertex %d is %s %s", i,
                adjacencyList.get(i), System.lineSeparator());
        }
    }

    public static void main(String[] args) {
        GraphDirectedByAdjacencyList graph = new GraphDirectedByAdjacencyList(3);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.printAdjacencyList();
    }
}
  • The only difference between the implementations is the addEdge(source, dest) method. addEdge in an undirected graph adds two-ways direction while in a directed graph adds one-way direction
// addEdge in a directed graph
public void addEdge(int source, int dest) {
    adjacencyList[source].add(dest);
}

// addEdge in an undirected graph
public void addEdge(int source, int dest) {
    adjacencyList[source].add(dest);
    adjacencyList[dest].add(source);
}

Weighted Graph implementation example

  • Weighted graph implementation example with an adjacency list

GraphWeightedByAdjacencyList.java

package com.hellokoding.datastructure.graph;

import java.util.ArrayList;
import java.util.List;

public class GraphWeightedByAdjacencyList {
    private int V;
    private List<List<WeightedVertex>> adjacencyList;

    public GraphWeightedByAdjacencyList(int V) {
        this.V = V;

        adjacencyList = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public Integer getV() {
        return this.V;
    }

    public List<List<WeightedVertex>> getAdjacencyList() {
        return this.adjacencyList;
    }

    public void addEdge(int source, int dest, int weight) {
        adjacencyList.get(source).add(new WeightedVertex(dest, weight));
    }

    public void printAdjacencyList() {
        for (int i = 0; i < V; i++) {
            System.out.printf("Adjacency list of vertex %d is %s %s", i,
                adjacencyList.get(i), System.lineSeparator());
        }
    }

    static class WeightedVertex {
        final Integer vertex, weight;

        public WeightedVertex(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        public int getWeight() {
            return this.weight;
        }

        public String toString() {
            return String.format("%d (weight %d)", vertex, weight);
        }
    }

    public static void main(String[] args) {
        GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
        g.addEdge(0, 1, 19);
        g.addEdge(2, 0, 15);
        g.addEdge(2, 1, 17);
        g.addEdge(3, 2, 12);
        g.printAdjacencyList();
    }
}

Depth-First Search (DFS) and Breadth-First Search (BFS) are algorithms for traversing or searching a graph

  • DFS starts at an arbitrary node and explores as far as possible along each branch before backtracking

    BFS starts at an arbitrary node and explores all of the neighbor nodes at the current level before moving on to the next level

    Thus DFS is better when the target is far from the source while BFS is better when the target is close to the source

  • DFS uses a Stack while BFS uses a Queue data structure to backtrack vertices on the traversal path
  • DFS consumes less memory than BFS as BFS has to store all the children each level
Graph traversal and searching with Depth-First and Breadth-First Search

Learn more about Depth-First Search and Breadth-First Search

Detect Cycle in a Directed Graph

You can use DFS to detect a cycle in a directed graph. When visiting a vertex v and its adjacency vertices, if there is a back edge (w, v) which directs to v then that graph has a cycle

Learn more

Topological Sort with Directed Acyclic Graph

Topological sort is an algorithm which takes a directed acyclic graph and returns a list of vertices in the linear ordering where each vertex has to precede all vertices it directs to

DFS and the above vertex degree theory can be used to implement the topological sort

Learn more

Find shortest paths between vertices

The shortest path is a path between two vertices in a graph such that the total sum of the weights of the constituent edges is minimum

You can implement an algorithm to find the shortest path by using Breadth-First Search (BFS), Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms

Learn more

Follow HelloKoding