Graph

Graph is a collection of vertices and arcs which connects vertices in the graph

Generally, a graph G is represented as G = (V, E), where V is set of vertices and E is set of edges.

---

Types of Graph data structure

Directed or Undirected graph-

Directed graph are connected from on vertices to another through an arrow with direction but undirected graph are simply connected without any direction.

Cyclic or Acyclic graph-

Cyclic graph have a cycle while Acyclic doesn’t have any cycle.

Weighted or unweighted-

If a graph is weighted, if each edge has a distance between two locations, or the cost or time it takes to travel between these locations.

Legal coloring-

A graph coloring is when you assign colors to each node in a graph. A legal coloring means no adjacent nodes have the same color

---

Java program to create a Graph:

Graph is represented by two dimensional array, here vertices are represented by int count and graph matrix will be of size vertices + 1, vertices + 1.

To make an edge we specify the start point and endpoint, which will be position in matrix in x coordinate and y coordinate.

Refer below code snippet-

import java.util.Scanner;

public class Graph {

       private final int vertices;

       private int[][] graph_matrix;

       public Graph(int v) {

              vertices = v;

              graph_matrix = new int[vertices + 1][vertices + 1];

       }

       public void makeEdge(int startPoint, int endPoint, int edge) {

              try {

                     graph_matrix[startPoint][endPoint] = edge;

              } catch (ArrayIndexOutOfBoundsException index) {

                     System.out.println("The vertices does not exists");

              }

       }

       public int getEdge(int startPoint, int endPoint) {

              try {

                     return graph_matrix[startPoint][endPoint];

              } catch (ArrayIndexOutOfBoundsException index) {

                     System.out.println("The vertices does not exists");

              }

              return -1;

       }

       public static void main(String args[]) {

              int v, e, count = 1, startPoint = 0, endPoint = 0;

              Scanner sc = new Scanner(System.in);

              Graph graph;

              try {

                     System.out.println("Enter the number of vertices: ");

                     v = sc.nextInt();

                     System.out.println("Enter the number of edges: ");

                     e = sc.nextInt();

                     graph = new Graph(v);

                     System.out.println("Enter the edges: <startPoint> <endPoint>");

                     while (count <= e) {

                           startPoint = sc.nextInt();

                           endPoint = sc.nextInt();

                           graph.makeEdge(startPoint, endPoint, 1);

                           count++;

                     }

                     System.out.println("The adjacency matrix for the given graph is: ");

                     System.out.print("  ");

                     for (int i = 1; i <= v; i++)

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

                           System.out.println();

                     for (int i = 1; i <= v; i++) {

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

                           for (int j = 1; j <= v; j++)

                             System.out.print(graph.getEdge(i, j) + " ");

                             System.out.println();

                     }

              } catch (Exception E) {

                     System.out.println("Somthing went wrong");

              }

              sc.close();

       }

   }

---

Breadth First Search (BFS)

Breadth First Search is a graph-traversal algorithm, used to finding the shortest path from the starting node to the end node.

BFS travels “layer-by-layer". This means, it first visits all the children of the starting node. These children are treated as the "second layer". Then it will traverse all child of second layer and traverse similarly till the target node found.

It’s kind of left to right traversal.

---

Depth First Search (DFS)

DFS traverse the tree or graph from top to bottom traversal.

DFS doesn't guarantee to find the shortest possible path unlike BFS.

---

A* Search

This algorithm is generally used for most of the shortest path problems. It's often used for real-life searching scenarios as well as video games. Most NPCs and AI players rely on A* to intelligently search for a path, fast and efficient.

A* search algorithm calculate the cost of the route through a function f(x)

Here f(x) is further depends on two other function g(x) and h(x), here g(x) is the cost of movement from starting point to a given square in a grid, while h(x) is the cost of estimated move from the given square in the grid to final destination.

g(x) - The function that represents the cost of moving from the starting node to a given node.

h(x) - The estimated cost from the given node to the goal node.