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.
0 Comments