### Ticker

20/recent/ticker-posts

# 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.

### 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.

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.

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();
}

for (int i = 0; i < vertex; i++) {
for (int j = 0; j < vertex; j++) {
System.out.println("Enter the edge between" + " " + +i + " " + "and" + " " + j + ":");
}
}
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<>();
}
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.