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.

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.

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.

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.

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.

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.

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 componentsA tree is a particular type of graph where the following statements hold:

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

This book synthesizes the most effective techniques and must-know principles into clear, pragmatic guidance. No matter what your experience level, development environment, or project size, this book will inform and stimulate your thinking - and help you build the highest quality code.

$ Check price(291+ reviews)

Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming.

$ Check price(418+ reviews)

Ad