A graph is a data structure made of nodes, also called vertices, joined by connections called edges. It is the natural way to represent anything that consists of things and relationships between them: a road map (intersections and roads), a social network (people and friendships), a dependency list (tasks and the tasks they must follow), or a web of hyperlinked pages. The graph itself says nothing about geometry; it only records which nodes are connected to which.
Edges can be directed or undirected. In an undirected graph an edge between A and B means the connection runs both ways, like a two-way street. In a directed graph each edge points one way, like a one-way street or a prerequisite that must come before another. Edges can also carry weights, such as the distance of a road or the cost of a step, which turns a plain graph into the input for shortest-path and minimum-spanning-tree problems.
Two representations dominate in practice. An adjacency list stores, for each node, the list of nodes it connects to; it uses space proportional to the number of edges and is efficient for sparse graphs where most pairs of nodes are not connected. An adjacency matrix stores a full grid of yes/no (or weight) entries for every possible pair, which makes checking a single connection instant but costs space proportional to the square of the number of nodes. The MIT 6.006 lecture on breadth-first search introduces graphs through the adjacency-list view because most real graphs are sparse, and almost every graph algorithm is analyzed in terms of V, the number of vertices, and E, the number of edges.
Graphs generalize many simpler structures. A tree is a graph with no cycles and a single path between any two nodes; a linked list is a graph where each node points to one other. Knuth treats this family of information structures, including linear lists and trees, in Volume 1 of The Art of Computer Programming, before the general graph traversals that build on them.