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