A graph is a mathematical structure that models pairwise relations between objects. The objects are represented as vertices and relations between two objects are represented with edges. For example, a road network could be described with a graph, where the cities are vertices and the roads between them are edges.
Definition
A graph is a pair $G = (V,E)$ where $V$ is a set of elements that are called vertices and $E$ is a set of pairs $(u,v)$ with $u,v \in V$ that are called edges between the vertices $u$ and $v$.
If we change this definition so that $E$ contains ordered pairs $(u,v)$ then we have a directed graph, where each pair represents a directed edge from $u$ to $v$, often written as $u \to v$. If not the graph is known as an undirected graph and edges don't have a direction.
The fact that $E$ is a set also means that there can only be one edge between two vertices. For that reason this is sometimes called a simple graph to distinguish it from multigraphs which can have duplicate edges.
In an undirected graph, a vertex $u$ is called a neighbour of $v$ if there exists an edge $(u,v) \in E$ and we say that $u$ is adjacent to $v$. The degree of a vertex $u$ is it's number of neighbours.
Definition
A graph $G' = (E', V')$ is a subgraph of a graph $G = (E,V)$ if $E' \subseteq E$ and $V' \subseteq V$. If $G' \not=G$ then $G'$ is a proper subgraph of $G$.
A walk is a sequence of vertices where each vertex is adjacent to the next one. A walk is called a path if each vertex is visited at most once. We say that a vertex $u$ is reachable from $v$ if there exists a walk between them. A graph is connected if any vertex is reachable from all the other vertices. A component of a graph is a maximal connected subgraph. Every graph consists of one or more components and two vertices are in the same component if there exists a walk between them.
Here are a few commonly used graph types in addition to the ones we have already described.
A weighted graph is a graph where each edge has been assigned a numerical value. The values might for example be costs, distances or bandwidth. Such graphs often arise in problems such as finding shortest paths or the travelling salesman problem.
A bipartite graph is a simple graph in which the vertices can be partitioned into two sets such that each vertex in one set is only neighbours with a vertex from the other set i.e. there are no edges between vertices in the same set. Such graphs are useful when modeling relations between two classes of objects.
A tree is a connected acyclic graph.
The most common data structure for storing graphs is the adjacency list. An adjacency list is an array $A$ such that the value $A[i]$ is an array of indexes of the adjacent vertices to vertex number $i$. The standard (and simplest) implementation of an adjacency list uses singly linked list.
Adjacency lists can be implemented using hash tables in which each vertex is mapped to an array of it's adjacent vertices. A vertex can thus be represented by any hashable object.
The main alternative to adjacency lists is the adjacency matrix.