Graph Basics

Graphs consist of vertices (nodes) that store data and edges that connect vertices. Edges may be unidirectional or bi-directional. Edges may also have weights associated with them. Two vertices are said to be adjacent if they are connected by only one edge. If the two vertices are connected by a sequence of more than one edges, then the sequence of edges between 2 vertices is called a Path. Two vertices are said to be connected if at least one path (single or multi-edge) exists between them. Paths is a graph can be cyclic, that is, they may start and end at the same node.

The diagram below shows a Graph:

Types of Graphs:

•	Undirected graphs: In this type of graph, the edges connect vertices in both directions.
•	Directional graph: In this type of graph the edges are uni-directional.
•	Simple graph: In this type of graph, two vertices are connected only by at most one edge.
•	Multi graph: In this type of graph, two vertices may be connected by more than one edge.
•	Complete graph: In this type of graph, all vertices are connected by a single edge with all other vertices of the graph.

Use cases for Graphs

In Social networks to model connections between multiple users.

In GPS systems to model paths between two or multiple end points.

For network modelling and analysis.

In image processing algorithms.

In project management to depict tasks and dependencies.

Used in machine learning neural networks.

Time Complexity of Heap data Structure

Graph using adjacency list:

Following table shows time complexity metrics for an String with n characters:

Operation	Complexity
Add vertex.	O(1)
Add edge	O(1)
Remove vertex.	O(V+E)
Remove edge.	O(E)
Search vertex	O(V)

Graph using adjacency matrix:

Following table shows time complexity metrics for an Graph operations using adjacency matrix:

Operation	Complexity
Add vertex.	O(V^2)
Add Edge	O(1)
Remove vertex.	O(V^2)
Remove vertex.	O(1)
Search vertex	O(1)

Graph in Java JDK API.

Java does not provide a standard graph implementation as part of its API. We need to code custom graph implementations as per requirements of the software.