Ticker

20/recent/ticker-posts

Advertisement

Graphs data structure

 Graph

The graph is a non-linear data structure, which contains sets of nodes and edges. These nodes are also referred to as vertices and the connection between any two nodes is an edge.

Graph example:


In the above figure, A, B, C, D are vertices of the graph and the connection between two vertices such as A and B is referred to as an edge.

Different types of graph:

Directed Graph

The term directed graph means that the edges in the graph are directed as for instance there is a direct edge from A to C, particularly in one direction.

Undirected Graph

The term undirected graph means that the edges in the graph are undirected as for instance if there is an edge from A to C in terms of the undirected graph there is also an edge from C to A.

Weighted Graph

The term weighted graph means, that there is an edge cost between any two vertices. Edge values represent cost, weight, or length.

Unweighted Graph

The term unweighted graph means, that there is no edge cost between any two vertices. For instance, the above figure is an unweighted graph.

Ways for representing a graph:

There are two ways to represent a graph data structure, they are Adjacency matrix and the adjacency list representation.

Adjacency Matrix Representation

In this representation, a matrix is made of size vertex * vertex that is the number of vertices of a graph.






In the above figure is a directed graph with vertices 1, 2, 3, 4, 5 and edges between them. The adjacency matrix representation shows an active edge by 1 and no edge by 0. If the graph is undirected an edge from 1 to 2 is marked as 1 along with 2 to 1.

Adjacency List Representation



In this above representation, an active edge is represented by creating a node adjacent to it.

Program of adjacency matrix representation:


class App {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertex = 0;
        System.out.println("Enter the number of vertices");
        if (sc.hasNextInt()) {
            vertex = sc.nextInt();
        }

        int[][] adj_matrix = new int[vertex][vertex];

        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                System.out.println("Enter the edge between" + " " + +i + " " + "and" + " " + j + ":");
                adj_matrix[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                System.out.println(
                        "The edge between" + " " + +i + " " + "and" + " " + j + " " + "is :" + adj_matrix[i][j]);

            }
        }
        sc.close();

    }
}

Program of adjacency list representation:


class App {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertex = 0;
        System.out.println("Enter the number of vertices");
        if (sc.hasNextInt()) {
            vertex = sc.nextInt();
        }
        List<ArrayList<Integer>> list = new ArrayList<>(vertex);
        for (int i = 0; i < vertex; i++) {
            ArrayList<Integer> l = new ArrayList<>();
            list.add(l);
        }
        list.get(1).add(2);
        list.get(1).add(3);
        list.get(2).add(4);
        list.get(4).add(5);
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                System.out.println(
                        "The edge between" + " " + i + " " + "and " + j + " " + "is" + " " + list.get(i).get(j));
            }
        }
        sc.close();

    }
}

Moreover, adjacency list representation is way more preferred as it does not represent unactive edges.
We can traverse the graph using various methods these following methods are popular graph traversals.
  • Breadth-First Search
  • Depth-First Search.
I hope you guys liked this article and here are some articles you may like:

Post a Comment

0 Comments