Graph tutorial-directed & undirected graphs ,adjacency list & adjacency matrix
A graph is a collection of nodes and edges.
Nodes can be visualized as circles with data inside them. These can be simple data like numbers, alphabets or even complex objects that hold a lot of data. Nodes are also referred to as vertices (vertex in singular).
Edges are connections between nodes and are shown by lines with arrowheads showing the direction of the connection or lines without arrowheads in case the connection is in both directions.
A bidirectional connection/relation between A and B.
Taking the above illustrations, we can comfortably say that graphs model relationship between things. For instance ,a graph showing connectivity between cities, or routes within a city.
Neighbor node-node or nodes that you can travel to when positioned at a specific node while obeying the directionality of the relationship. In Illustration 2 above B is a neighbor of A but B does not consider A as a neighbor since there is no path to travel from B to A as per the directionality of the edge.
In Illustration 3 B is a neighbor to A and A is a neighbor to B since it is possible to travel to either node when positioned at any of the nodes.
Types of Graphs
We have two main variants of graphs
- Directed graphs
- Undirected graphs
Directed graphs
These are graphs whereby there is direction between the nodes.
This is indicated by arrow heads from the source node to its neighbor.
In above graph we can travel to B from A but not vice versa.
Undirected graph
In this graph, direction is shown by lines without arrowheads and is bidirectional. If A and B are connected B is neighbor to A and A is neighbor to B since we can travel to either node from any of the nodes.
Graph representation
Graphs can be represented in two (2) , major ways.
- Adjacency list
- Adjacency matrix
Adjacency List
Adjacency list holds a list of neighbors for every node in the graph.It is best implemented in a map since a map data structure gives constant time during look up when checking the neighbors of a node.
Let’s explore with the below example.
The above graph is an example of a disjoint graph whereby some nodes have connections to each other but are outside the network of the other nodes in the graph.
The adjacency list will be ;
Explanation
p has neighbor q only hence the entry p:[q],conversely q has p as her only neighbor hence the entry q:[p].
i has 2 neighbors j and k hence the entry i:[j,k].j has only i as her neighbor hence the entry j:[i],k has 3 neighbors i ,m and l hence the entry k:[i,m,l],l has only 1 neighbor k hence the entry l:[k],m has only 1 neighbor k hence the entry m:[k] . n and o are disjoint from the bigger graph, nevertheless n has only 1 neighbor o hence the entry n:[o] and o has only 1 neighbor n hence the entry o:[n].
Adjacency list implementation in Java
We can implement the adjacency list for the above graph in Illustration 4
package graphs;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AdjacencyList {
public static void main(String... args) {
List<List<String>> undirectedGraph = new ArrayList<>();
ArrayList<String> edge0 = new ArrayList<>();
edge0.add("i");
edge0.add("j");
ArrayList<String> edge1 = new ArrayList<>();
edge1.add("k");
edge1.add("i");
ArrayList<String> edge2 = new ArrayList<>();
edge2.add("m");
edge2.add("k");
ArrayList<String> edge3 = new ArrayList<>();
edge3.add("k");
edge3.add("l");
ArrayList<String> edge4 = new ArrayList<>();
edge4.add("o");
edge4.add("n");
ArrayList<String> edge5 = new ArrayList<>();
edge5.add("p");
edge5.add("q");
undirectedGraph.add(edge0);
undirectedGraph.add(edge1);
undirectedGraph.add(edge2);
undirectedGraph.add(edge3);
undirectedGraph.add(edge4);
undirectedGraph.add(edge5);
System.out.println("------Undirected edge list-----");
System.out.println(undirectedGraph);
Map<String, List<String>> adjList = buildAdjacencyList(undirectedGraph);
System.out.println("-----Adjacency list-----");
adjList.keySet().stream().forEach(key -> {
System.out.println(key + ":" + adjList.get(key));
});
}
private static Map<String, List<String>> buildAdjacencyList(List<List<String>> undirectedGraph) {
Map<String, List<String>> adjacencyList = new HashMap<>();
for (List<String> connection : undirectedGraph) {
String a = connection.get(0);
String b = connection.get(1);
if (!adjacencyList.containsKey(a)) {
adjacencyList.put(a, new ArrayList<>());
}
if (!adjacencyList.containsKey(b)) {
adjacencyList.put(b, new ArrayList<>());
}
adjacencyList.get(a).add(b);
adjacencyList.get(b).add(a);
}
return adjacencyList;
}
}
The output of the above program is as below:
Adjacency matrix
In this approach we have a matrix of N*N dimensionality whereby N is the number of nodes in the graph. If an edge exists between Nodes A and B, we have 1 in the matrix intersection NRC and a 0 where there is no edge, R=row, C=column.
Going with the graph in Illustration 4 we have below adjacency matrix.
Explanation
i has 2 neighbors j and k so we have 1 at indices (0,1)=j and (0,2)=k.The rest of the row-column intersections have 0 .In the second row,we keep neighbors for j.j has only 1 neighbor i so at (1,0) we have 1.The rest of the row-column intersections for j have 0.On the 3rd row,we keep neighbors for k.k has 3 neighbors i,l and m.At (2,0)=i we have 1,at (2,3)=l we have 1 and at (2,4)=m we have 1.All the other row-column intersections have 0’s since k has no connection with them.On the 4th row we have data for l’s neighbors.l has only 1 neighbor k so at (3,2)=k,we have 1.However this was already set up when tracking k’s neighbors since l is k’s neighbor at index (2,3) in the previous row.This is because our graph in illustration 4 is a undirected graph.The process repeats for all the remaining nodes.
Lets look at sample code to implement the above adjacency matrix in Java.
Adjacency matrix implementation in Java
package graphs;
import java.util.ArrayList;
import java.util.List;
public class AdjacencyMatrix {
public static void main(String... args) {
List<String> vertices = new ArrayList<>();
vertices.add("i");
vertices.add("j");
vertices.add("k");
vertices.add("l");
vertices.add("m");
vertices.add("n");
vertices.add("o");
vertices.add("p");
vertices.add("q");
List<List<String>> undirectedGraph = new ArrayList<>();
ArrayList<String> edge0 = new ArrayList<>();
edge0.add("i");
edge0.add("j");
ArrayList<String> edge1 = new ArrayList<>();
edge1.add("k");
edge1.add("i");
ArrayList<String> edge2 = new ArrayList<>();
edge2.add("m");
edge2.add("k");
ArrayList<String> edge3 = new ArrayList<>();
edge3.add("k");
edge3.add("l");
ArrayList<String> edge4 = new ArrayList<>();
edge4.add("o");
edge4.add("n");
ArrayList<String> edge5 = new ArrayList<>();
edge5.add("p");
edge5.add("q");
undirectedGraph.add(edge0);
undirectedGraph.add(edge1);
undirectedGraph.add(edge2);
undirectedGraph.add(edge3);
undirectedGraph.add(edge4);
undirectedGraph.add(edge5);
int[][] adjMatrix = buildAdjacencyMatrix(vertices, undirectedGraph);
//print constructed matrix
for (int i = 0; i < adjMatrix.length; i++) {
for (int j = 0; j < adjMatrix.length; j++) {
System.out.print(" " + adjMatrix[i][j]);
}
System.out.println();
}
}
private static int[][] buildAdjacencyMatrix(List<String> vertices, List<List<String>> undirectedGraph) {
int[][] adjMatrix = new int[vertices.size()][vertices.size()];
for (List<String> connection : undirectedGraph) {
String a = connection.get(0);
String b = connection.get(1);
int aindex = vertices.indexOf(a);
int bindex = vertices.indexOf(b);
adjMatrix[aindex][bindex] = 1;
adjMatrix[bindex][aindex] = 1;
}
return adjMatrix;
}
}
Running the above program outputs below which is the same adjacency matrix we have discussed.
