01. Introduction to Graphs

In the real world, there will be objects that have relationships with one another. For example, you (an object) are in friendships (relation) with peers on Facebook. Can we represent this relation using a data structure? In order to best represent these relationship of objects, we may use the graph data structure.

What are graphs?

Graphs are a particular data structure that define vertices, connected to one another via edges. Mathematically, a graph is represented by G = (V, E). The vertices (V) can be drawn in as nodes, while the edges (E) connect the nodes together.

Examples of graphs in the real world

There are plenty of instances where the use of a graph can be used in the real world.

  • A network of friends in social media.
  • A map - each intersection is a node, and each street/road is an edge.
  • Websites - each website is a node and each external link is an edge to another site.

Example graph

Example graph data structure.
Example digraph graph data-structure. Here, |V| = 7 and |E| = 8.

Vertices and Edges

Vertices are represented by the vector V, and edges are displayed as E. The number of vertices in a graph is |V|, and the number of edges |E|. Edges may or may not have a direction. In the example above, they do. Graphs with edges that have a direction are known as digraphs, and those without are known as undirected.

Graph terms

Here are a list of basic graph terms you may come across.

Self-loop
An edge that starts and ends at the same vertex.
The vertex 1 has a self-loop in our example above.
Neighbor
Vertex A is a neighbor of B if there exists an edge connecting A to B.
The neighbors of 1 include 0,1,2,3,4 and 5.
Connected
A graph is connected is there exists a path from every vertex to every other vertex in the graph.
Our example is not connected since there it is directed and there is no path that visits every point on the graph.
In-degree
The number of edges pointing into a vertex.
The in-degree of vertex 1 is 4.
Out-degree
The number of edges pointing out of a vertex.
The out-degree of vertex 1 is also 4.
Degree Sequence
An ordered sequence of each vertices' degrees (in-degree + out-degree) in decreasing order.
Parallel edges
Two edges that connect to the same pair of vertices.
There are no parallel edges in our graph.
Multigraph
A graph containing parallel edges.
Simple Graph
A graph containing no parallel edges.
Our example graph is a simple graph.
Dense/Sparse
Dense if lots of vertices are connected to one another. The opposite of a dense graph is a sparse one.
Bipartite graph
A graph whose vertices that can be divided into two sets such that all edges connect a vertex in one set with a vertex in the other set.
Path
A sequence of vertices connected by edges. Its length is represented by the number of edges.
Simple path
A path with no repeat visits of vertices.
Cycle
A path in which with at least one edge where the first and last vertices are the same.
Simple Cycle
Cycle with no repeated edges or vertices.

We can specify a graph with V vertices with numbers 0 to V-1.

Types of graphs

There exists four types of graphs:

Undirected
Connections edges are undirected.
Directed
Each edge has a direction.
Edge-weighted
Each connection has a weight.
Edge-weighted digraph
Each connection has a direction and a weight.
Example graph data structure.
Example of a edge-weight graph.

Graph Abstract Class Implementation

Now that we understand what graphs are, let's look at how we would implement them in Java.

There are several ways to represent graphs, so let's start with an abstract base class.

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
 
public abstract class Graph {
    private int numVertices;
    private int numEdges;
 
    public Graph() {
        numVertices = 0;
        numEdges = 0;
    }
 
    public int getNumVertices() {
        return numVertices;
    }
 
    public int getNumEdges() {
        return numEdges;
    }
 
 
    public void setNumVertices(int v) {
        numVertices = v;
    }
 
    public void setNumEdges(int e) {
        numEdges = e;
    }
 
    public abstract boolean inEdgeExists(int v, int w) throws VertexOutOfBoundsException;
    public abstract boolean outEdgeExists(int v, int w) throws VertexOutOfBoundsException;
    public abstract void addVertex();
    public abstract void addEdge(int v, int w) throws VertexOutOfBoundsException;
    public abstract void removeVertex() throws VertexOutOfBoundsException;
    public abstract void removeEdge(int v, int w) throws VertexOutOfBoundsException;
    public abstract int getInDegree(int v) throws VertexOutOfBoundsException;
    public abstract int getOutDegree(int v) throws VertexOutOfBoundsException;
    public abstract List<Integer> getNeighbors(int v) throws VertexOutOfBoundsException;
    public abstract List<Integer> getNeighborsTwoApart(int v) throws VertexOutOfBoundsException;
    
    public List<Integer> getDegreeSeq() throws VertexOutOfBoundsException {
        List<Integer> degreeSeq = new ArrayList<Integer>();
        int degrees = 0;
        for (int i = 0; i < getNumVertices(); i++) {
            degrees = getInDegree(i) + getOutDegree(i);
            degreeSeq.add(degrees);
        }
        Collections.sort(degreeSeq);
        Collections.reverse(degreeSeq);
        return degreeSeq;
    }
 
}

Our implementation of different types of graphs should extend this abstract Graph class. In addition to this class, let's also define our own custo exception:

import java.lang.Exception;
 
public class VertexOutOfBoundsException extends Exception {
  public VertexOutOfBoundsException() {
    super();
  }
  public VertexOutOfBoundsException(String message) {
    super(message);
  }
}

In the next lesson, let's learn how to extend this base class to implement a graph structure with an adjacency matrix.

subgraph - subset of a graph's edges. acyclic graph = graph w no cycles disjoint set of trees = forest spanning tree = subgraph that contains al of the graph's vertices and is a single tree spanning forest = union of spanning trees of its connected components

Trees

A tree is a particular type of graph where the following statements hold:

  1. Trees have V-1 edges and no cycles.
  2. Each edge is connected.
  3. Removing any one edge disconnects the tree.
  4. The graph G is acyclic, but adding any edge creates a cycle.
  5. There exists exactly one simple path that connects each pair of vertices in G.

Want to avoid becoming a code monkey?

The Pragramatic Programmer

Want to avoid becoming a code monkey? Try Good Practice

The Pragmatic Programmer illustrates the best practices and major pitfalls of many different aspects of software development.Whether you're a new coder, an experienced programmer, or a manager responsible for software projects, use these lessons daily, and you'll quickly see improvements in personal productivity, accuracy, and job satisfaction.

$ Check price
49.9949.99Amazon 4.5 logo(338+ reviews)

More Good Practice resources

Learn Enterprise Java Development for a Bright Career

Core Java, Volume II

Learn Enterprise Java Development for a Bright Career Try Java

Designed for serious programmers, this reliable, unbiased, no-nonsense tutorial illuminates advanced Java language and library features with thoroughly tested code examples. As in previous editions, all code is easy to understand and displays modern best-practice solutions to the realworld challenges faced by professional developers.

$ Check price
59.9959.99Amazon 4 logo(34+ reviews)

More Java resources

Ad