What is a Graph data structure?

Graphs consist of 2 ingredients :

• Vertices (V) , also called nodes and can be pictured as dots
• Edges (E) , the line connecting the nodes.

Types of Graphs
Depending on the edges, there two types of graphs:

1. Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the 'Family tree of the Greek gods'
2. Directed Graphs (aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow. Example of such a graph is the 'A finite-state machine of a light switch'

So, consider the following figure below:

So, above graph look similar, but 2nd graph is directed one, as it has arrows attached with some direction.



Graph ADT
Graph is an Abstract Data Type (ADT) which is of a non-linear structure entailing sets of nodes and connectors. Here, the connectors helps to establish relationship between nodes. However, from the graph ADT literature point-of-view the nodes are referred to as Vertices and connectors are referred to as Edges.
>Mathematically, a graph G entails vertices V, which are connected by edges E. Hence, a graph is defined as an ordered pair G=(V,E), where V is a finite set and E is a set consisting of two element subsets of V. We will come to ADT after types of graphs.


Graph ADT in java
So this can be represented as graph:

public class Edge {
    private Node a, b;
    private directionEnum direction;     // AB, BA or both 
    private int weight;
    ...
}

public class Vertex
{
    private List edges;
}

It is looking simple right now, and I agree it may vary depending on your requirement. So, this is just one way of representing the graph. Also, we have to come accross adjacency list and adjacency matrix to make it more clear.

For java, you can refer to following graph library:

• http://jung.sourceforge.net/doc/index.html  
• http://jgrapht.sourceforge.net/
• raphviz  
• Sage

Examples of Graph
Graphs are used ubiquitously.

• An obvious example is a map. The places are the vertices while the roads connecting them are the edges. 
• Web - Individual pages are vertex and linkages among pages are edges
• Social networks - Vertices are individuals and relations are edges
• Graphs can also be used to set precedence. That is, you can show which things are prerequisites for others, such as course prerequisite. 
• Networks - What is network in terms of graph:
  Network refers to a graph in which the edges are bound with weights. Here weights can be numbers assigned to a the edges. Hence, a graph of this nature is referred to as weighted graph or a network.

Number of edges in graph
A graph in one piece with n nodes must have at least n-1 edges. You start out with n distinct pieces and by adding an edge between two edges, you now have n-1 distinct pieces. To get to one piece, you need to do this n-1 times.
This graph will have a maximum number of edges when every vertex is connected to every other vertex. Then there will n(n-1)/2 total edges or nC2, because this is the number of ways of choosing 2 vertices from n of them.

Sparse vs Dense graphs
This distinction is useful as some algorithm are good for sparse graph, and some for dense graph.

Let n( OR |V|) be the # of vertices and m (OR |E|) be the # of edges,
then in most (but not all) applications, we have that m is Ω (n) and O(n²).

A graph is "sparse" if it is closer to the lower bound and "dense" if it is closer to the upper bound.
This is a loose definition.



Resources:
  Source 1, Source 2