Below are some important types of graphs.

• Undirected graph:
  An undirected graph comprised of set of nodes and edges, and the order of edge that connects two nodes has no direction.
  Below is an example of undirected graph.
• Directed graph:
  A directed graph comprised of set of nodes and edges, and the order of edge that connects two nodes will represent a direction.
  Below is an example of directed graph.
• Weighted graph:
  In a weighted graph, an edge that connects nodes will have a value or weight representing the cost of traversing through that path.
  Below is an example of directed graph.
• Finite graph:
  A graph will be called as finite graph if the number of vertices and edges in the graph are limited in number.
  Below is an example of finite graph.
• Ininite graph:
  A graph will be called as infinite graph if the number of vertices and edges in the graph are unknown.
  Below is an example of infinite graph.
• Connected graph:
  If there is a path between every vertex to all other vertices in the graph is called as connected graph.
  Below is an example of connected graph.
• Disconnected graph:
  If there is no path between a vertex and another vertex in the graph that forms disjoint sets in the graph called as disconnected graph.
  Below is an example of disconnected graph. As you can see vertex 2 has no path to any other vertices.

• If a graph contains only one vertex and has no edges is called as Trivial graph.
• If a graph contains multiple vertices, and has no edges is called as Null graph.
• If a graph has relatively few edges than vertices (in general, number of edges are less than |V| log |V|) is called as sparse graph.
• In a graph, if every vertex is connected to other vertex in the graph, is called as Complete graph.
• In a graph, if the number of edges are close the number of edges in a complete graph is called as Dense graph.
• If a graph contains atleast one graph cycle, is called as Cyclic graph.
  In the below example node 1 is connected to 2, 2 is connected to 3, 3 is connected to 4, and 4 is connected back to 1, so it forms a cycle.
• If a graph does not contain any cycles, is called as Acyclic graph.
  In the below example node 1 is connected to 2, 2 is connected to 3, and 3 is connected to 4.

Below are some real world applications of Graphs.

• Geographical map to show how cities connects with roads, flight network and trains network.
• Entitiy relationships in database.
• Social network applications.
• You can model computers network and internet using graphs.

Graph data structure is commonly represented using

• Adjascency matrix.
• Adjascency list.

• Adjascency matrix:
  A graph can be represented as adjascency matrix, for example using a 2D array.
  For example, consider below undirected graph, as you see nodes that are connected are 1-2 , 2-3, 3-4 and 4-1.

  It can be represented as array of arrays, if there is an edge between the nodes, mark that with 1, otherwise 0.

                                            1  2  3  4
                                        1  [0  1  0  1]
                                        2  [1  0  1  0]
                                        3  [0  1  0  1]
                                        4  [1  0  1  0]
          

  char[][] graph = { { 0, 1, 0, 1}, { 1, 0, 1, 0}, { 0, 1, 0, 1} { 1, 0, 1, 0} };
• Adjascency list:
  A graph can be represented as adjascency list, where each node is represented using a singly linked list, with links to its adjascent nodes if there is an edge. public class Node { private int element; private LinkedList<Node> adjascencyList = new LinkedList<>(); public Node(int element) { this.element = element; } public void addAdjascentNode(Node adj) { adjascencyList.add(adj); } public int getElement() { return element; } public LinkedList getAdjascencyList() { return adjascencyList; } }
• Below code snippet shows how you can create graph nodes and their edges. Node element_one = new Node(1); Node element_two = new Node(2); Node element_three = new Node(3); Node element_four = new Node(4); // 1-> 2 and 1-> 4 element_one.addAdjascentNode(element_two); element_one.addAdjascentNode(element_four); // 2-> 1 and 2-> 3 element_two.addAdjascentNode(element_one); element_two.addAdjascentNode(element_three); // 3-> 2 and 3-> 4 element_three.addAdjascentNode(element_two); element_three.addAdjascentNode(element_four); // 4-> 3 and 4-> 1 element_four.addAdjascentNode(element_three); element_four.addAdjascentNode(element_one);