Alternative graph data structures
Here are some examples of slightly different approaches:

Hash-table

Key into hash-table is a vertex, value is a list of vertices it is connected to, the edge is thus a relation between the key and the element of the value in the hash-table.  This is not so different from adjacency list except that testing for presence of the vertex will be faster, but it will take more spece to store the graph.

This, obviously, describes a directed graph.  You could include the reversed edges to make it work as undirected graph.

Example (JavaScript):

function graph() {
    var vertices = {}, g = { vertices: vertices };
    g.getVertex = function (vertex) {
        return vertices[vertex];
    };
    g.getEdge = function (from, to) {
        var adjacent = vertices[from], result;
        if (adjacent.indexOf(to) &gt; -1) result = [from, to];
        return result;
    };
    g.addEdge = function (from, to) {
        var edges = vertices[from] || [];
        edges.push(to);
        vertices[from] = edges;
    };
    [].slice.call(arguments).forEach(function (edge) {
        g.addEdge.apply(g, edge);
    });
    return g;
}
graph([1, 2], [1, 3], [2, 1], [2, 3], [3, 5], [3, 6], [3, 4],
      [4, 7], [5, 2], [5, 6], [6, 3], [6, 7]);
// { vertices: 
//    { '1': [ 2, 3 ],
//      '2': [ 1, 3 ],
//      '3': [ 5, 6, 4 ],
//      '4': [ 7 ],
//      '5': [ 2, 6 ],
//      '6': [ 3, 7 ] },
//   getVertex: [Function],
//   getEdge: [Function],
//   addEdge: [Function] }


Graph-proper data structure

We define vertex as a tuple of the value and a list of edges from this vertex to other vertices it is directly connected to.  This is a little bit more compact than the hash-table, but testing whether vertex is in a graph becomes linear (just as in adjacency list / matrix).  Same as before we can add edges in the opposite direction to make this graph undirected.  This is different from adjacency list in that retrieving all adjacent vertices to a given vertex is a constant time operation, while in the list it is linear in time.  Adjacency matrix would also give constant time for this, but will use more space, especially if a graph is sparse.

Example (Prolog):

:- use_module(library(record)).

:- record vertex(value, arcs=[_ | _]).

lookup(X, [X | _]).
lookup(X, [Y | Xs]) :- X \== Y, lookup(X, Xs).

instantiated(Goal, [X | _], []) :- \+ call(Goal, X).
instantiated(Goal, [X | Xs], [X | Ys]) :- call(Goal, X), instantiated(Goal, Xs, Ys).

vertex_instantiated(Vertex) :-
    make_vertex([], Vertex),
    vertex_value(Vertex, Value),
    ground(Value).

find_vertex_helper(Value, _, Vertex) :- vertex_value(Vertex, Value).
find_vertex_helper(V1, Cache, V2) :-
    vertex_arcs(V2, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    subtract(InstArcs, Cache, FilteredArcs),
    union(Cache, InstArcs, NewCache),
    findnsols(1, V, (member(V, FilteredArcs),
                     find_vertex_helper(V1, NewCache, V)),
              [V2]).

find_vertex(_, [], _) :- !, fail.
find_vertex(Value, [V | Graph], Vertex) :-
    vertex_value(V, Value), Vertex = V
    ;
    vertex_arcs(V, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    include(find_vertex_helper(Value, []), InstArcs, [Vertex])
    ;
    find_vertex(Value, Graph, Vertex).

find_or_create_vertex(Value, Vertex, Graph, Graph) :-
    find_vertex(Value, Graph, Vertex), !.
find_or_create_vertex(Value, Vertex, OldGraph, [Vertex | OldGraph]) :-
    make_vertex([value(Value)], Vertex).

add_arc(From, To, OldGraph, NewGraph) :-
    find_or_create_vertex(From, VertexFrom, OldGraph, Graph1),
    find_or_create_vertex(To, VertexTo, Graph1, NewGraph),
    vertex_arcs(VertexFrom, Arcs),
    lookup(VertexTo, Arcs).

make_graph_helper([], Graph, Graph).
make_graph_helper([From-To | Vs], GraphIn, GraphOut) :-
    add_arc(From, To, GraphIn, NewGraph),
    make_graph_helper(Vs, NewGraph, GraphOut).

make_graph(Vs, Graph) :- make_graph_helper(Vs, [], Graph).

make_graph([x1-x2, x1-x3, x2-x1, x2-x3, x3-x5, x3-x6, x3-x4,
            x4-x7, x5-x2, x5-x6, x6-x3, x6-x7], G).
/*    G = [vertex(x7, [_G3910|_G3911]),
           vertex(x4, [vertex(x7, [_G3910|_G3911])|_G3891]),
           _S1, _S2,
           vertex(x3, [_S2, _S1, vertex(..., ...)|...]),
           vertex(x2, [_S3, vertex(..., ...)|...]), _S3],
           % where
          _S1 = vertex(x6, [...]),
          _S2 = vertex(x5, [...]),
          _S3 = vertex(x1, [...]) */