Implement the Graph Data Structure in Java

Exercise:

Write a Java Program to to implement the graph data structure.

Click Here to View the Solution!
public class Graph {

    // inner class
    class Edge {
        int src, dest;
    }

    // number of vertices and edges
    int vertices, edges;

    // array to store all edges
    Edge[] edge;
    Graph(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;

        // initialize the edge array
        edge = new Edge[edges];
        for(int i = 0; i < edges; i++) {

            // each element of the edge array
            // is an object of Edge type
            edge[i] = new Edge();
        }
    }

    public static void main(String[] args) {

        // create an object of Graph class
        int noVertices = 5;
        int noEdges = 8;
        Graph g = new Graph(noVertices, noEdges);

        // create graph
        g.edge[0].src = 1;   // edge 1---2
        g.edge[0].dest = 2;

        g.edge[1].src = 1;   // edge 1---3
        g.edge[1].dest = 3;

        g.edge[2].src = 1;   // edge 1---4
        g.edge[2].dest = 4;

        g.edge[3].src = 2;   // edge 2---4
        g.edge[3].dest = 4;

        g.edge[4].src = 2;   // edge 2---5
        g.edge[4].dest = 5;

        g.edge[5].src = 3;   // edge 3---4
        g.edge[5].dest = 4;

        g.edge[6].src = 3;   // edge 3---5
        g.edge[6].dest = 5;

        g.edge[7].src = 4;   // edge 4---5
        g.edge[7].dest = 5;

        // print graph
        for(int i = 0; i < noEdges; i++) {
            System.out.println(g.edge[i].src + " - " + g.edge[i].dest);
        }

    }
}
Click Here to View the Output!
1 - 2
1 - 3
1 - 4
2 - 4
2 - 5
3 - 4
3 - 5
4 - 5
Click Here to View the Explanation!
  • This program shows how to create a graph data structure.
  • Here we have created a class Graph, which contains an inner class Edge to keep track of edges in the graph.
  • Here src and dest keep track of source and destination vertices of all edges; also we create an array of Edge type to store the edges.
  • The constructor of Graph initializes the values of vertices and edges.
  • The values of edges are assigned to edge array, where each element of edge array is an Edge type object.
  • After initializing the edge array, we move on to main method where we declare 5 vertices and 8 edges and initialize a Graph object.
  • Then we connect vertices by creating edges between them.
  • Finally we print all the edges that exist between graph vertices.
  • Notice that no vertex is connected to itself, thus avoiding any loop.

%d bloggers like this: