According to Wikipedia:
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.
A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
A graph is a pictorial representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by points termed as vertices, and links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.
Take a look at the following graph:-
In the above graph,
There are different ways of representing a graph, each of them with its own advantages and disadvantages. Here are the two main ones:
- Adjacency list: For every vertex a list of adjacent vertices is stored. This can be viewed as storing the list of edges. This data structure allows the storage of additional data on the vertices and edges.
- Adjacency matrix: Data are stored in a two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. The data on the edges and vertices must be stored externally.
If a tree is free to have more than one parent, it becomes a Graph. Edges that connect vertices together in a graph can be directed or undirected, weighted or unweighted. Edges that have both direction and weight are analogous to vectors.
Multiple inheritances in the form of Mixins and data objects that have many-to-many relationships produce graph structures. A social network and the Internet itself are also graphs. The most complicated graph in nature is our human brain, which neural networks attempt to replicate to give machines superintelligence.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Storage |  |
 |
| Add Vertex |  |
|
| Add Edge | |
|
| Query |  |
|
Simple representation of a Graph (Our sample graph)
