Two common ways to represent graphs on a computer are as an adjacency list or as an adjacency matrix.
Both representations allow us to represent directed graphs, since we can have an edge from to , but lack one from to . To represent undirected graphs, we simply make sure that are edges are listed twice: once from to , and once from to .
Which representation is best? Both. If graph has a large portion of its edges, then the adjacency matrix doesn't waste much space, and it indicates whether edge exists with one access (rather than following a list). However, if graph is sparse (not many of its vertex pairs have edges between them), then an adjacency list becomes preferable. For example, if has 10,000 vertices and only about 20,000 edges, then its adjacency matrix representation will need (100 million) entries -- 400 megabytes if each took a word. Representing the same with an adjacency list might require, say, 10,000 words for the node plus 20,000 words for the list of neighbours: 30,000 words or 120K. The difference may make one representation feasible and the other infeasible.