19. Graph

 

Graph

• A graph is a non-linear data structure consisting of vertices and edges.
• The vertices are some times also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph.
• A graph is composed of a set of vertices (V) and a set of edges (E). The graph is denoted by G(E, V).

Representation of Graph

Following two are the most commonly used representations of a graph.

• Adjacency Matrix
• Adjacency List

There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph representation is situation specific. it totally depends on the type of operations to be performed and ease of use.

Adjacency Matrix

• An adjacency matrix is a way of representing a graph as a matrix of boolean (0's and 1's).
• Let's assume there are n vertices in the graph. So, create a 2D matrix adj[n][n] having dimensions n × n.
• If there is an edge from vertex i to j, mark adj[i][j] as 1.
• If there is no edge from vertex i to j, mark adj[i][j] as 0.

Adjacency List

• An array of lists is used to store edges between two vertices.
• The size of array is equal to the number of vertices.
• The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.

class Edge {

    int src;

    int dest;

    int wgt;

    Edge(int src, int dest) {

        this.src = src;

        this.dest = dest;

        this.wgt = 0;

    }

    Edge(int src, int dest, int wgt) {

        this.src = src;

        this.dest = dest;

        this.wgt = wgt;

    }

}

Graph traversal

We can traverse the graph in two ways:

• BFS (Breadth First Search)
• DFS (Depth First Search)

BFS Graph Traversal

• This traversal algorithm selects a node and visits all nearby nodes in order. After checking all nearby vertices, examine another set of vertices, then recheck adjacent vertices.
• This algorithm uses a queue as a data structure as an additional data structure to store nodes for further processing.

void breadthFirstTraversal(ArrayList<Edge> graph[], int root) {

        Queue<Integer> queue = new LinkedList<>();

        boolean visited[] = new boolean[graph.length];

        queue.add(root);

        while (!queue.isEmpty()) {

            int curr = queue.remove();

            if (!visited[curr]) {

                System.out.print(curr + " ");

                visited[curr] = true;

                for (Edge edge : graph[curr])

                    queue.add(edge.dest);

            }

        }

    }

DFS Graph Traversal

• This algorithm explores the graph in depth-first order, starting with a given source node and then recursively visiting all of its surrounding vertices before backtracking.
• DFS will analyze the deepest vertices in a branch of the graph before moving on to other branches.
• To implement DFS, either recursion or an explicit stack might be utilized.

void depthFirstTraversal(ArrayList<Edge> graph[], int root, boolean visited[]) {

        if (!visited[root]) {

            System.out.print(root + " ");

            visited[root] = true;

            for (Edge edge : graph[root])

                depthFirstTraversal(graph, edge.dest, visited);

        }

    }