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

## 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 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);
}
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.

#### Programming Interviews: Exposed In today's tight job market, competition for programming jobs is hotter than ever. This third edition of a popular guide to programming interviews includes new code examples, information on the latest languages, new chapters on sorting and design patterns, tips on using LinkedIn, and a downloadable app to help prepare applicants for the interview.

\$ Check price (94+ reviews)

### Aching back from coding all day?

#### Prism Glasses Ever feel achy from sitting crunched up on your computer table? Try lying down with these optical glasses that allow you to work on your laptop while lying flat on your back. This is the perfect solution with those with limited mobility or those who wish to prevent neck cramps and back strains.

\$ Check price (128+ reviews)