Types of Graph in Data Structure

Q: What is the difference between a simple graph and a multigraph?

A simple graph has no self-loops and at most one edge between any two vertices. A multigraph allows several edges between the same pair of vertices, such as multiple flights between two cities.

Q: What is a directed acyclic graph (DAG)?

A DAG is a directed graph with no cycles. DAGs model tasks with dependencies, such as build steps, course prerequisites and spreadsheet formulas, and they can be put in a topological order.

Q: Write a Java method for a topological sort of a DAG.

Java example: import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; // Kahn's algorithm: repeatedly take vertices with no incoming edges static List topologicalSort(List > graph) { int[] inDegree = new int[graph.size()]; for (List edges : graph) { for (int v : edges) { inDegree[v]++; } } Queue queue = new ArrayDeque<>(); for (int v = 0; v order = new ArrayList<>(); while (!queue.isEmpty()) { int v = queue.poll(); order.add(v); fo

Q: Write a Java method to check whether a graph is bipartite.

Java example: import java.util.ArrayDeque; import java.util.Arrays; import java.util.List; import java.util.Queue; static boolean isBipartite(List > graph) { int[] color = new int[graph.size()]; Arrays.fill(color, -1); for (int start = 0; start queue = new ArrayDeque<>(); queue.offer(start); while (!queue.isEmpty()) { int v = queue.poll(); for (int next : graph.get(v)) { if (color[next] == -1) { color[next] = 1 - color[v]; // opposite color queue.offer(next); } else if (color[next] == col

Q: What is the difference between a sparse and a dense graph?

A sparse graph has far fewer edges than the maximum, close to V. A dense graph has close to V 2 edges. Use an adjacency list for sparse graphs and consider an adjacency matrix for dense graphs.

Q: Is a tree a type of graph?

Yes. A tree is a connected, acyclic, undirected graph. A tree with n vertices always has exactly n - 1 edges.

Q: What is a cyclic graph versus an acyclic graph?

A cyclic graph contains at least one cycle; an acyclic graph contains none. An undirected acyclic graph is a forest (a set of trees), and a directed acyclic graph is a DAG.

Types of Graph in Data Structure

Finite Graph: If the graph G=(V, E) has a limited number of vertices and edges, it is referred to as a finite graph.
Infinite Graph: The graph G=(V, E) is called a finite graph if the number of vertices and edges in the graph is interminable.
Trivial Graph: If a graph G = (V, E) contains only one vertex and no edges, it is called a trivial graph.
Directed Graph: A graph that has a set of nodes connected by edges, each with a direction, is called a directed graph. A directed graph, also referred to as a digraph.
Undirected Graph: An undirected graph consists of nodes and links that connect them. The order of the two connected vertices is irrelevant and without direction. We can create an undirected graph with a finite number of vertices and edges.
Weighted Graph: In a graph, if each edge has some value or weight, it is called a labeled or weighted graph. The value or weight represents the cost of traversing that edge.
Cyclic Graph: A cyclic graph is a type of graph in which at least one path leads back to the same vertex, creating a cycle. Such a type of graph is called a cyclic graph.
Acyclic Graph: Acyclic graphs are those that do not contain any cycles.
Directed Acyclic Graph: A directed acyclic graph (DAG) is one that contains directed edges but no cycle. It uses an ordered pair of vertices to represent the edges since it directs them and holds certain data.
Simple Graph: A simple graph is one in which each pair of nodes or vertices has only one edge. As a result, only one edge connects two vertices, representing one-on-one interactions between two constituents.
Multi Graph: A graph G= (V, E) is called a multigraph if there are many edges connecting two vertices. A Multigraph does not contain self-loops.
Connected Graph: A graph is said to be linked if there is a path connecting any two of its vertices.
Disconnected Graph: A disconnected graph is a type of graph in which there are at least two vertices that are not connected by a path. This means that the graph can be divided into two or more components, each of which is connected internally but not to the other components.
Complete Graph: A complete graph is another type of graph in data structure; in this graph, every pair of distinct vertices is connected by a unique edge. A complete graph is an undirected graph, and it is also known as a full graph because each vertex's degree must be n-1.
Null Graph: A graph that has multiple vertices but no edges connecting them is known as a null graph. A null graph is a revised version of a simple graph.
Pseudo Graph: If a graph contains a self-loop besides other edges, it is a pseudograph.
Regular Graph: A regular graph is one that has the same degree at each vertex. As a result, the entire graph is a regular graph.
Subgraph: A subgraph is a set of vertices and edges from one graph that are subsets of another graph.

Frequently Asked Questions (FAQ)

Q1. What is the difference between a simple graph and a multigraph?

A simple graph has no self-loops and at most one edge between any two vertices. A multigraph allows several edges between the same pair of vertices, such as multiple flights between two cities.

Q2. What is a complete graph, and how many edges does it have?

In a complete graph, every vertex is connected to every other vertex. An undirected complete graph with n vertices has n(n - 1) / 2 edges; for 5 vertices that is 10 edges.

Q3. What is a connected graph?

An undirected graph is connected if there is a path between every pair of vertices. A directed graph is strongly connected if every vertex can reach every other vertex following the edge directions.

Q4. What is a directed acyclic graph (DAG)?

A DAG is a directed graph with no cycles. DAGs model tasks with dependencies, such as build steps, course prerequisites and spreadsheet formulas, and they can be put in a topological order.

Q5. Write a Java method for a topological sort of a DAG.

TopologicalSort.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

// Kahn's algorithm: repeatedly take vertices with no incoming edges
static List<Integer> topologicalSort(List<List<Integer>> graph) {
    int[] inDegree = new int[graph.size()];
    for (List<Integer> edges : graph) {
        for (int v : edges) {
            inDegree[v]++;
        }
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int v = 0; v < graph.size(); v++) {
        if (inDegree[v] == 0) queue.offer(v);
    }
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int v = queue.poll();
        order.add(v);
        for (int next : graph.get(v)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return order;          // fewer than V vertices means the graph has a cycle
}

Q6. What is a bipartite graph?

A bipartite graph's vertices can be split into two groups so that every edge connects a vertex in one group to a vertex in the other. Job-to-applicant matching is a typical example. A graph is bipartite exactly when it has no odd-length cycle.

Q7. Write a Java method to check whether a graph is bipartite.

IsBipartite.java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

static boolean isBipartite(List<List<Integer>> graph) {
    int[] color = new int[graph.size()];
    Arrays.fill(color, -1);
    for (int start = 0; start < graph.size(); start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int next : graph.get(v)) {
                if (color[next] == -1) {
                    color[next] = 1 - color[v];      // opposite color
                    queue.offer(next);
                } else if (color[next] == color[v]) {
                    return false;                    // same color on both ends
                }
            }
        }
    }
    return true;
}

Q8. What is the difference between a sparse and a dense graph?

A sparse graph has far fewer edges than the maximum, close to V. A dense graph has close to V² edges. Use an adjacency list for sparse graphs and consider an adjacency matrix for dense graphs.

Q9. Is a tree a type of graph?

Yes. A tree is a connected, acyclic, undirected graph. A tree with n vertices always has exactly n - 1 edges.

Q10. What is a cyclic graph versus an acyclic graph?

A cyclic graph contains at least one cycle; an acyclic graph contains none. An undirected acyclic graph is a forest (a set of trees), and a directed acyclic graph is a DAG.

Was this tutorial helpful?

Help Us Improve

Types of Graph in Data Structure

Types of Graph in Data Structure

Frequently Asked Questions (FAQ)