A simple graph is a collection of vertices and edges. The most basic distinction is: directed vs undirected, weighted vs unweighted, both referring to the edges.
Typical representations:
For an unweighted graph, the matrix entries are either 0 or 1, for a weighted graph, they can be any value (the weight of the edge).
Array[List[VertexId]]
.It may be worth considering the way that graphs are a "second order" type of data structure. That is, they are not a fundamental, first class data structure, since they are typically represented in different ways depending on what is most appropriate for the operations to be done on the graph. Graphs are a more abstract entity than the computer has a natural representation for.