Introduction
Get ready, because we're about to dive headfirst into the wild and wacky world of Graphs! Forget your boring old spreadsheets; here, we'll untangle their mysterious properties, get cozy with their vertices (the VIPs of the graph), navigate their edges (the scenic routes), master the art of traversal, and even learn how to draw them in a way that doesn't look like your cat walked across the keyboard (their representation). I'm hoping this post is more valuable than finding a twenty in your old jeans, but if you have any brilliant ideas, don't be shy – drop a comment below!
Graph
Picture a bunch of islands floating in the sea. Each island is a vertex. Now, imagine some beavers build bridges between certain islands. Those bridges? They're the edges. A graph is just the whole map showing where all the islands are and which ones are connected by a convenient bridge. It's a network of "who's connected to whom".
Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges.
Basic terms of a graph
-
Directed edges in graphs are like one-way streets. If you have an edge
(u, v)that's directed fromutov, it means you can travel fromutov, but you cannot go fromvback touusing that same edge. The arrow (from the above figure) tells you which way the traffic flows. Now, for undirected edges, it's more like a two-way street or a friendly handshake. If there's an undirected edge betweenuandv, it means the connection goes both ways. You can absolutely travel fromutov, and just as easily fromvtou. The lack of an arrow (from the above figure) implies this mutual connection. - The two vertices joined by an edge are called the end vertices (or endpoints) of the edge. For the undirected graph in the above figure, Vertex
AandBare the endpoints for edge2. If an edge is directed, its first endpoint is its origin (e.g.,A) and the other is its destination (e.g.,B), as seen with edge3in the above figure. - Two vertices
uandvare said to be adjacent if there is an edge whose end vertices areuandv. In the above figure,AandBare adjacent because there is an edge between them for example, edge2in the undirected graph, or edge3even if directed fromAtoB. - An edge is said to be incident to a vertex if the vertex is one of the edge’s endpoints. In the above figure, edge
3is incident to vertexB, and edge4is also incident to vertexBassuming vertexBis an endpoint of both edge3and edge4. A vertex is incident with an edge if the vertex is one of the endpoints of that edge. - The outgoing edges of a vertex are the directed edges whose origin is that vertex. The incoming edges of a vertex are the directed edges whose destination is that vertex. In the above figure the vertex
Bhas two outgoing edges (2and4) and one incoming edge (3) in the directed graph. - The degree of a vertex
vis the number of incident edges ofv. The in-degree and out-degree of a vertexvare the number of the incoming and outgoing edges ofv, respectively.
We've navigated the dictionary of graph terms, and now it's time to get our hands dirty with some actual code to bring these concepts to life.
So, go ahead and fire up your favorite text editor and let's start sketching out the blueprint for our Graph.
The Vertex ADT
Before our graph can establish any type of connections, we must first define its fundamental building block: the vertex. Please create a Vertex.java file and add the following code.
public interface Vertex<V> {
V getElement();
void setIsVisited(boolean isVisited);
boolean getIsVisited();
}
From the above code getElement() which is obvious return the element stored at the vertex, the other like getIsVisited() and setIsVisited() are used for indicating if the vertex is visited or not we will be using them in graph graph traversal section.
The Graph ADT
We've given our humble vertices a soul. Now, for the grand reveal: it's time to give the entire Graph some personality and give it the essential tricks 'expected functions' – we're training our magnificent Graph to perform.
numVertices(): Returns the number of vertices of the graph.
vertices(): Returns an iteration of all the vertices of the graph.
numEdges(): Returns the number of edges of the graph
insertVertex(x): Creates and returns a new Vertex storing element x.
insertEdge(u, v): Creates and an Edge from vertex u to vertex v, an error occurs if there already exists an edge from u to v.
outgoingVertices(v): returns the outgoing vertex connected to v.
incomingVertices(v): returns the incoming vertex connected to v.
outDegree(v): Returns the number of outgoing edges from vertex v.
inDegree(v): Returns the number of incoming edges to vertex v. For an undirected graph, this returns the same value as does outDegree(v).
Alright, It's time to get our abstract Graph concept into the harsh reality of Java ☕ code. We're not just defining it anymore; we're giving it a proper blueprint (a.k.a., an interface). So, buckle up, create that Graph.java file, and let's give it a life into with the code below.
public interface Graph<V> {
int numVertices();
int numEdges();
Iterable<Vertex<V>> vertices();
Vertex<V> insertVertex(V element);
void insertEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;
V removeVertex(Vertex<V> v) throws IllegalArgumentException;
Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException;
Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException;
int outDegree(Vertex<V> v) throws IllegalArgumentException;
int inDegree(Vertex<V> v) throws IllegalArgumentException;
}
Graph representation
Think of graph representation as the art of organizing a very, very busy brain. How do we store all those relationships – who knows whom, what leads where – inside a computer's limited gray matter so it can actually find things later without a complete meltdown? It's all about picking the right mental filing system.
We have to forget the other graph representations for now – we're going with the Adjacency List for totally obvious reasons.
We use an array as our main directory, where each spot is reserved for a vertex. But here's the clever bit: each array spot doesn't just hold the vertex; it points to a list of all that vertex's immediate pals or 'neighbors.' We call this its adjacency list.
So, if A is our array, A[i] leads you to 'Node i's' list. If 'Node i' is socially awkward and has no connections? A[i] will just point to null. look at the figure below for more understanding.
Adjacency List Implementation
We've done the theoretical hand-waving, now... it's time to get down to the nuts and bolts, the secret sauce, the absolute juicy core of our graph adventure: implementing the adjacency list with true grace.
This is where the real magic happens. So, create a new file called AdjacencyMapGraph.java, and let's start weaving some code spells.
Our master plan for this elegant implementation involves:
- Using an
ArrayList<Vertex<V>>to keep our vertices neatly organized (like a very tidy collection of digital action figures). - And, of course, the ever-important
isDirectedboolean will be our guiding star, letting us know if we're dealing with one-way streets (directed graph) or a free-for-all (undirected graph) network.
Let's make some magic happen in AdjacencyMapGraph.java with the code below.
import java.util.ArrayList;
import java.util.HashSet;
import dsa.graph.Graph;
import dsa.graph.Vertex;
public class AdjacencyMapGraph<V> implements Graph<V> {
private boolean isDirected;
private int numEdges;
private ArrayList<Vertex<V>> vertices = new ArrayList<>();
public AdjacencyMapGraph(boolean isDirected) {
this.isDirected = isDirected;
}
}
Now we need to dive into the nitty-gritty of what makes each individual vertex. Think of it like giving each of our graph citizens their own little private diary and address book.
So, let's conjure up a special internal class, which we'll call InnerVertex. This little powerhouse will quietly implement our Vertex interface.
Inside this InnerVertex's digital brain, we're going to give it two super-speedy rolodexes: outgoing and incoming. These will be HashSet<Vertex<V>> because, let's be honest, we're obsessed with that glorious O(1) time complexity. outgoing and incoming variables will be the same if the graph is undirected. This way, our InnerVertex can instantly know who it's sending signals to and who's sending signals its way.
And just to keep things super organized, each InnerVertex will also remember its own 'seat number' – an index member that tells us exactly where it's chilling in our main vertices array.
Alright, enough with the briefing! It's time to get down to business. Head back to your AdjacencyMapGraph.java file and let's embed this clever little helper with the code below. Get ready to sprinkle some more magic!
public AdjacencyMapGraph(boolean isDirected) {
this.isDirected = isDirected;
}
protected static class InnerVertex<V> implements Vertex<V> {
private V element;
private int index;
private boolean isVisited;
private HashSet<Vertex<V>> outgoing, incoming;
public InnerVertex(V element, boolean isDirected) {
this.element = element;
outgoing = new HashSet<>();
if (isDirected) {
incoming = new HashSet<>();
} else {
incoming = outgoing;
}
}
@Override
public void setIsVisited(boolean isVisited) {
this.isVisited = isVisited;
}
@Override
public boolean getIsVisited() {
return isVisited;
}
public V getElement() {
return element;
}
public HashSet<Vertex<V>> getOutgoing() throws IllegalArgumentException {
return outgoing;
}
public HashSet<Vertex<V>> getIncoming() throws IllegalArgumentException {
return incoming;
}
public int getIndex() {
return this.index;
}
public void setIndex(int index) {
this.index = index;
}
}
Alright, we've designed our fancy InnerVertex with all its clever internal workings. Now, it's time to equip our AdjacencyMapGraph with its fundamental housekeeping rules and, most importantly, a very strict validator validate(Vertex<V> v), Think of it as our graph's quality control department, making sure only our kind of vertices (the InnerVertex kind) are allowed to play in our exclusive graph club.
public void setIndex(int index) {
this.index = index;
}
}
private InnerVertex<V> validate(Vertex<V> v) {
if (!(v instanceof InnerVertex))
throw new IllegalArgumentException("Invalid vertex");
InnerVertex<V> vertex = (InnerVertex<V>) v;
return vertex;
}
@Override
public int numVertices() {
return vertices.size();
}
@Override
public int numEdges() {
return numEdges;
}
@Override
public Iterable<Vertex<V>> vertices() {
return vertices;
}
@Override
public Vertex<V> insertVertex(V element) {
InnerVertex<V> vertex = new InnerVertex<>(element, isDirected);
vertices.add(vertex);
vertex.setIndex(vertices.size() - 1);
return vertex;
}
@Override
public int outDegree(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> origin = validate(v);
return origin.getOutgoing().size();
}
@Override
public int inDegree(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> destination = validate(v);
return destination.getIncoming().size();
}
@Override
public Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> outgoing = validate(v);
return outgoing.getOutgoing();
}
@Override
public Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> incoming = validate(v);
return incoming.getIncoming();
}
Alright, next we've to add our meticulous validators and our keen-eyed "are-they-even-here-or-already-friends?" checkers (our isValidVertex and hasEdge methods). Head back to AdjacencyMapGraph.java add the code below.
public void setIndex(int index) {
this.index = index;
}
}
private boolean hasEdge(Vertex<V> u, Vertex<V> v) {
InnerVertex<V> origin = validate(u);
InnerVertex<V> destination = validate(v);
return origin.getOutgoing().contains(destination);
}
private boolean isValidVertex(Vertex<V> v) {
if (v == null) {
return false;
}
InnerVertex<V> vertex = validate(v);
int index = vertex.getIndex();
if (index < vertices.size() && vertices.get(index) == vertex) {
return true;
}
return false;
}
Now that all the pre-flight checks are in place, we can finally and happily, write the big one: our insertEdge(Vertex<V> u, Vertex<V> v) method. Let's give our AdjacencyMapGraph.java the power to make relationships! Go ahead and add the following code.
InnerVertex<V> vertex = validate(v);
int index = vertex.getIndex();
if (index < vertices.size() && vertices.get(index) == vertex) {
return true;
}
return false;
}
@Override
public void insertEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException {
if (!isValidVertex(u) || !isValidVertex(v)) {
throw new IllegalArgumentException("Invalid vertex");
}
if (!hasEdge(u, v)) {
InnerVertex<V> origin = validate(u);
InnerVertex<V> destination = validate(v);
origin.getOutgoing().add(destination);
destination.getIncoming().add(origin);
numEdges++;
} else
throw new IllegalArgumentException("Edge from u to v exists");
}
Alright, we've brought vertices into existence, we've played matchmaker with edges, and now... it's time for the less glamorous but equally essential task: ejecting a vertex.
Sometimes, a vertex just needs to go. But before we send it packing, we have to be polite and disconnect all its social ties first using our removeEdge() method. Can't have any dangling digital friendships, after all.
And here's where we get really clever to avoid a massive performance headache. Normally, if you yank a vertex out of the middle of an array, everything after it has to awkwardly shuffle forward, which is a slow O(N) dance. But we're too smart for that.
Instead, we're going to pull a fast one: when we remove a vertex, we'll grab the very last vertex in our vertices array and plop it right into the empty spot using the index inside the vertex. Then, we simply snip off the now-redundant last element. It's like a quick game of musical chairs to fill the gap instantly, making our removal almost ridiculously fast (a glorious O(1)). No tedious shifting required.
So, get ready to implement this elegantly brutal "eviction" strategy. Head back to AdjacencyMapGraph.java and let's add the code to gracefully removed vertex.
destination.getIncoming().add(origin);
numEdges++;
} else
throw new IllegalArgumentException("Edge from u to v exists");
}
private void removeEdge(HashSet<Vertex<V>> edges, Vertex<V> vertex, boolean isOutgoing) {
for (Vertex<V> ve : edges) {
InnerVertex<V> vert = validate(ve);
if (isOutgoing) {
vert.getIncoming().remove(vertex);
} else {
vert.getOutgoing().remove(vertex);
}
numEdges--;
}
edges.clear();
}
@Override
public V removeVertex(Vertex<V> v) throws IllegalArgumentException {
V temp = v.getElement();
InnerVertex<V> vertex = validate(v);
HashSet<Vertex<V>> outgoing = vertex.getOutgoing();
removeEdge(outgoing, vertex, true);
HashSet<Vertex<V>> incoming = vertex.getIncoming();
removeEdge(incoming, vertex, false);
int index = vertex.getIndex();
int size = vertices.size();
if (index != size - 1) {
InnerVertex<V> lastVertex = validate(vertices.get(size - 1));
lastVertex.setIndex(index);
vertices.set(index, lastVertex);
}
vertices.remove(size - 1);
vertex = null;
v = null;
return temp;
}
Graph traversal algorithms
Alright, our dandy graph has been built, it's got its charming vertices, and it knows how to make (and break) connections. But what's a magnificent map if you can't actually explore it?
Now, it's time for our graph to embark on some grand adventures! We're talking about traversal algorithms, which are essentially fancy ways for our graph to go on a tour, visiting each of those cute little vertices and intriguing edges.
On this particular post, we're going back to basics, visiting the wise elders of the traversal world: the good old Depth-First Search (DFS) and Breadth-First Search (BFS). Think of them as two very different, but equally effective, tour guides for navigating the twists and turns of our graph. One's a deep diver, the other's a wide explorer.
Depth-First Search (DFS)
Depth-First Search (DFS) is basically that friend who, when faced with a multi-story building, immediately bursts into the first room they see and then just keeps going. "Oh, a door! What's behind that door? Another door! Let's see where that one leads!"
It's like DFS gets tunnel vision. It'll plunge down into the deepest, darkest corner of the basement, exploring every nook and cranny of that one path before it even considers glancing at another room on the first floor. It carries a trusty stack to remember where it was before it got distracted by the shiny new path, like a pile of "oops, gotta backtrack eventually" notes. It's not about levels, it's about seeing how deep the rabbit hole goes.
Alright, we've got the lowdown on what DFS is all about! Now it's time to roll up our sleeves and get our hands dirty by implementing it on our trusty, dandy Graph. We're gonna let it explore all its precious vertices. So go on, create GraphAlgorithms.java file and write the following code right inside.
public class GraphAlgorithms {
public static <V> void depthFirstSearch(Graph<V> graph, Vertex<V> start, ArrayList<Vertex<V>> visited) {
start.setIsVisited(true);
visited.add(start);
for (Vertex<V> vertex : graph.outgoingVertices(start)) {
if (!vertex.getIsVisited()) {
depthFirstSearch(graph, vertex, visited);
}
}
}
public static <V> ArrayList<Vertex<V>> depthFirstSearchComplete(Graph<V> graph) {
ArrayList<Vertex<V>> snapshot = new ArrayList<>();
for (Vertex<V> vertex : graph.vertices()) {
if (!vertex.getIsVisited()) {
depthFirstSearch(graph, vertex, snapshot);
}
}
return snapshot;
}
}
Our depthFirstSearch() method starts exploring your graph from a chosen vertex, then recursively visits all connected vertices it hasn't seen yet. To make sure every single vertex in the graph gets explored, even if it's disconnected, our depthFirstSearchComplete() method loops through all vertices and calls depthFirstSearch() for any that haven't been visited yet.
Breadth-First Search (BFS)
Unlike its chaotic cousin (DFS), Breadth-First Search is the sensible, highly organized explorer. When faced with a multi-story building, it doesn't just plunge into the basement. Oh no! It meticulously clears out every room on the first floor, then every room on the second, and so on. It's all about exploring "level by level," methodically making its way through the structure. It carries a trusty queue to remember which rooms it still needs to check on the current floor.
Alright, We've got a good understanding of what BFS is all about. It's time to get our hands dirty by implementing it on our Graph. We're gonna let it explore all its precious vertices. So go on and add the following code inside GraphAlgorithms class.
for (Vertex<V> vertex : graph.vertices()) {
if (!vertex.getIsVisited()) {
depthFirstSearch(graph, vertex, snapshot);
}
}
return snapshot;
}
public static <V> void breadthFirstSearch(Graph<V> graph, Vertex<V> start, ArrayList<Vertex<V>> visited) {
Queue<Vertex<V>> queue = new LinkedList<>();
queue.add(start);
start.setIsVisited(true);
visited.add(start);
while (!queue.isEmpty()) {
Vertex<V> current = queue.remove();
if (!current.getIsVisited()) {
current.setIsVisited(true);
visited.add(current);
}
for (Vertex<V> vertex : graph.outgoingVertices(current)) {
if (!vertex.getIsVisited()) {
queue.add(vertex);
}
}
}
}
public static <V> ArrayList<Vertex<V>> breadthFirstSearchComplete(Graph<V> graph) {
ArrayList<Vertex<V>> snapshot = new ArrayList<>();
for (Vertex<V> vertex : graph.vertices()) {
if (!vertex.getIsVisited()) {
breadthFirstSearch(graph, vertex, snapshot);
}
}
return snapshot;
}
public static <V> void resetVisitedVertices(ArrayList<Vertex<V>> visited) {
for (Vertex<V> vertex : visited) {
vertex.setIsVisited(false);
}
}
resetVisitedVertice() method is used for un-visiting the visited vertices.
Alright, it seems our initial dive into the world of Graphs has reached its surface. While we've only skimmed the top of this fascinating subject, covering the essential basics like vertices, edges, traversal, and representation, there's a whole ocean of advanced topics awaiting us.
We deliberately kept this post concise to ensure you grasped the fundamental concepts without getting lost. In upcoming posts, we'll dive and explore much deeper.
Now that we've finished writing the post, we need to test what we've written so far. So, go to your main() method and add the following code.
public static void main(String[] args) throws Exception {
AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(true);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> five = graph.insertVertex(5);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> seven = graph.insertVertex(7);
Vertex<Integer> eight = graph.insertVertex(8);
// Insering an edge
graph.insertEdge(one, three);
graph.insertEdge(one, five);
graph.insertEdge(five, four);
graph.insertEdge(five, two);
graph.insertEdge(three, eight);
graph.insertEdge(three, seven);
var visited = GraphAlgorithms.depthFirstSearchComplete(graph); // [1, 5, 2, 4, 3, 8, 7]
for (Vertex<Integer> vertex : visited) {
System.out.print(vertex.getElement() + ", ");
}
GraphAlgorithms.resetVisitedVertices(visited);
System.out.println("\n-- BFS Visited ---");
var bfsVisited = GraphAlgorithms.breadthFirstSearchComplete(graph); // [1, 5, 3, 2, 4, 8, 7]
for (Vertex<Integer> vertex : bfsVisited) {
System.out.print(vertex.getElement() + ", ");
}
}
The graph we create on the code is the same as the graph in the figure below.
Top comments (0)