Skip to content

Instantly share code, notes, and snippets.

@bachiri
Created September 5, 2019 21:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bachiri/1e25d7ff721047a44833db4df0ed0b84 to your computer and use it in GitHub Desktop.
Save bachiri/1e25d7ff721047a44833db4df0ed0b84 to your computer and use it in GitHub Desktop.
Graph Adjacency list Representation
import java.util.LinkedList;
public class GraphAdjacencyListRepresentation {
public static void main(String[] args) throws GraphRep.GraphException {
GraphRep graphRep = new GraphRep(6);
graphRep.addVertexTo(new GraphNode(4), new GraphNode(5));
graphRep.addVertexTo(new GraphNode(4), new GraphNode(1));
graphRep.addVertexTo(new GraphNode(4), new GraphNode(6));
graphRep.addVertexTo(new GraphNode(5), new GraphNode(1));
graphRep.addVertexTo(new GraphNode(5), new GraphNode(7));
graphRep.addVertexTo(new GraphNode(6), new GraphNode(1));
graphRep.addVertexTo(new GraphNode(6), new GraphNode(2));
graphRep.addVertexTo(new GraphNode(1), new GraphNode(2));
graphRep.printGraph();
// 4------------5--------7
// |\ |
// | \ |
// | \ |
// | \ |
// | \ |
// | \ |
// 6------------1
// \ /
// \ /
// \ /
// \ /
// \ /
// 2
}
static class GraphNode {
int data;
public GraphNode(int data) {
this.data = data;
}
}
static class GraphRep {
LinkedList<GraphNode>[] adjList;
int count = 0;
public GraphRep(int nodesNumber) {
adjList = new LinkedList[nodesNumber];
}
public void addVertexTo(GraphNode source, GraphNode destination) throws GraphException {
insert(source, destination);
insert(destination, source);
}
private void insert(GraphNode source, GraphNode destination) throws GraphException {
if (count >= adjList.length) {
throw new GraphException("Out of bound check The right number of your vertices ");
}
int index = vertexExist(source);
if (index != -1) {
LinkedList<GraphNode> graphNodes = adjList[index];
graphNodes.addLast(destination);
} else {
adjList[count] = new LinkedList<>();
adjList[count].addFirst(source);
adjList[count].addLast(destination);
count++;
}
}
private int vertexExist(GraphNode source) {
for (int i = 0; i < adjList.length; i++) {
LinkedList<GraphNode> graphNodes = adjList[i];
if (graphNodes != null && graphNodes.getFirst().data == source.data) {
return i;
}
}
return -1;
}
public void printGraph() {
for (LinkedList<GraphNode> graphNodes : adjList) {
System.out.println("Nodes For " + graphNodes.poll().data);
while (!graphNodes.isEmpty()) {
System.out.print(" " + graphNodes.poll().data);
}
System.out.println("");
System.out.println("----------");
}
}
class GraphException extends Exception {
public GraphException(String message) {
super(message);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment