Adjacency Matrix and List Representations | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 10.4 Free with a free account

Adjacency Matrix and List Representations

Discrete Mathematics · Chapter 10: Graph Theory: Hamiltonian Circuits, Coloring, and RepresentationsSection 10.4 · lesson 70 of 879 min · free with a free account

← Graph Coloring and TraversalNext lesson: Trees: Properties and Definitions →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

How a graph lives in memory - and what its matrix can count.

  • Build an adjacency matrix
  • Build an adjacency list
  • Compare their space and time costs
  • Count walks with matrix powers

Transcript

Everything said in the video, section by section (1,420 words). Read along, or search it.

Graph Theory: Hamiltonian Circuits, Coloring, and Representations

Adjacency Matrix and List Representations

This section closes chapter ten by asking how a graph is actually stored in a computer. We'll build the two standard representations, the adjacency matrix and the adjacency list, and compare their costs. Then we'll see something unexpected. Raising the matrix to a power counts walks through the graph.

The Opening Problem

The First Design Decision

When a ride-hailing app computes a route between a rider and a driver, the algorithm never touches a drawn map. It works on a graph stored in memory. And the very first design decision, long before any path-finding runs, is how to represent that graph as data. A city's road network can have many thousands of intersections, yet each one connects to only a handful of others. A large social network looks different, but shares that feature. An enormous number of people, each connected to a tiny fraction of everyone else. The wrong representation doesn't just waste memory. It can turn a route lookup that should take milliseconds into one that takes seconds.

Definition 10.4.1

The Adjacency Matrix

First, the adjacency matrix. Fix an ordering of the n vertices, and use it for both rows and columns. The entry in row i and column j is one, if vertices i and j are joined by an edge. Otherwise, it's zero. For an undirected graph, the matrix is symmetric. For a directed graph, a one in row i, column j records an edge from i to j specifically. For a weighted graph, the entry usually stores the weight instead of a one. Here's the running example: five stations, A through E, with edges A B, A C, B C, B D, C D and D E. Check all ten pairs, write a one for each edge, and a zero on the diagonal, since there are no loops. That gives this matrix. It's symmetric across the diagonal, and each row sums to that vertex's degree.

Definition 10.4.2

The Adjacency List

The adjacency list keeps one list per vertex, holding exactly that vertex's neighbors. To build it, scan the edge set once. For each edge, append each endpoint to the other endpoint's list. Sorted for readability, A's list is B and C. B's is A, C and D. C's is A, B and D. D's is B, C and E. And E's list has just one entry, D. E is a spur, reachable only through D. For a directed graph, each list holds only the vertices the edges point to. For a weighted graph, each entry is a pair, the neighbor and the weight.

Listing 10.4.1

Building Both From an Edge List

This function builds both structures from the same edge list. It maps each vertex label to an index, starts with an all-zero matrix and empty lists, then processes each edge once. For an undirected edge, it sets both matrix entries, i j and j i, and appends each endpoint to the other's list. At the end it sorts each list, for a predictable order. Run on the five stations, it reproduces the matrix and the lists built by hand.

10.4.3

Sparse and Dense Graphs

The two representations make very different commitments about space. Informally, a graph is sparse if its number of edges grows roughly in proportion to the number of vertices. It's dense if the edges grow toward the maximum possible, about n squared over two. That's a working distinction, not a strict cutoff. A matrix always allocates n squared cells, recording a zero or one for every pair, however few edges exist. A list allocates space only for edges that exist. Each edge contributes exactly two entries, one in each endpoint's list. So the total is proportional to n plus the number of edges. For our five stations, that's twenty-five matrix cells, against twelve list entries. Already smaller. And most real networks, roads, social graphs and the web's links, are sparse. A typical vertex connects to a small, roughly constant number of others. That's why large systems overwhelmingly favor adjacency lists.

Table 10.4.1

Space and Time Tradeoffs

Here's how the two compare, operation by operation. Space: theta of n squared for the matrix, and theta of n plus the number of edges for the list. Checking whether u v is an edge takes constant time in the matrix, a direct lookup. In the list, you may have to scan all of u's neighbors. Listing all neighbors of v is the reverse. The matrix scans a whole row of n entries. The list touches only the actual neighbors. Adding an edge is constant time in both. But adding a vertex means rebuilding the matrix, theta of n squared, while the list just creates one new empty list. So matrices suit dense graphs, and algorithms that need constant-time edge checks or matrix operations. Lists suit sparse graphs, and algorithms that mainly traverse neighbors, like breadth-first search.

10.4.4

Matrix Powers Count Walks

The adjacency matrix isn't only a storage format. It's an ordinary matrix, and it can be multiplied by itself. First, a definition. A walk of length k is a sequence of vertices, with an edge at each of its k steps. Unlike a path, a walk may repeat vertices and edges. The proposition says: for every k of at least one, the i j entry of A to the k counts the walks of length k, from vertex i to vertex j. The proof is by induction. For k equals one, the entry is one exactly when there's an edge, and that edge is the one walk of length one. For the inductive step, every walk of length k is a walk of length k minus one, to some middle vertex m, followed by one edge from m to j. Matrix multiplication sums, over every m, the number of shorter walks to m, times one if m is adjacent to j, and zero if not. That counts exactly the walks of length k.

Worked Example

The (A, D) Entry of A Squared

Let's compute one entry, row A, column D, of A squared. It's the dot product of row A, which is zero, one, one, zero, zero, with column D, which is zero, one, one, zero, one. Term by term, only the B and C positions contribute a one each. So the entry is two. And there really are two walks of length two from A to D. A, B, D, shown in teal, and A, C, D, shown in red. Each term of the dot product asks whether one middle vertex is adjacent to both ends. B and C are the only two that are.

Listing 10.4.2

Counting Walks, No Libraries

This code confirms it, with no external libraries. The multiply function computes each entry as a dot product, of a row of X, and a column of Y. To take the k-th power, start from the identity matrix, which is the zeroth power, and multiply by the adjacency matrix k times. Squaring the running example's matrix, and reading row zero, column three, which is the A D entry, prints two.

A Warning

Walks Are Not Paths

Where could this be useful? A mapping service could use A squared, A cubed, and higher powers to quickly estimate how many short routes connect two intersections, without running a full search. But there's a warning sign on the diagonal. In the running example, the A A entry of A squared is two. It counts the closed walks A, B, A and A, C, A. Each goes out along an edge, and straight back along the same edge. Those are legitimate walks. But they aren't new connections, and no path can revisit its starting vertex like that. In fact, each diagonal entry of A squared is just that vertex's degree. So a system that reports matrix power counts as if they counted genuinely new, simple connections risks quietly overcounting.

Takeaways

Store It to Suit the Graph

To summarize. An adjacency matrix stores all n squared pairs explicitly. It gives constant-time edge checks, at the cost of n squared space, however many edges exist. An adjacency list stores only the edges that exist. It uses space proportional to n plus the number of edges, and lists neighbors quickly, but edge checks can be slower. Most real-world networks are sparse, which is why large systems favor lists. Matrices still win for dense graphs, and for matrix-based algorithms. Raising the matrix to the k-th power counts walks of length k, linking graph theory to linear algebra. But walks may repeat vertices, so treat those counts with care. Here's something to think about. An engineer proposes using the i j entry of A squared, for two different people, as their number of length-two connections. Off the diagonal, in a simple graph, does the walk versus path distinction actually cause a problem? And what changes if the graph allows multiple edges, or if the length grows to three or more?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Adjacency Matrix and List Representations

What is an adjacency matrix, and how do you build one for an undirected graph?
An adjacency matrix is an n \times n table in which entry (i,j) is 1 if vertices i and j share an edge and 0 otherwise. Fix one vertex ordering for rows and columns, then fill in a 1 for each edge. For an undirected graph without loops, the matrix is symmetric with zeros on the diagonal, and each row sum equals that vertex's degree.
How do you build an adjacency list from a graph's edge set?
Create one list per vertex, then scan the edges once and append each endpoint to the other endpoint's list. For edges AB, AC, BC, BD, CD, and DE, A's list is B, C, and E's list is just D. In a directed graph, each list holds only the vertices its edges point to. In a weighted graph, each entry is a neighbor-weight pair.
When should I use an adjacency matrix instead of an adjacency list?
Use a matrix for dense graphs, or when an algorithm needs constant-time edge checks or matrix operations. A matrix uses \Theta(n^2) space, while a list uses \Theta(n+m) for m edges, so lists suit sparse graphs and neighbor traversal such as breadth-first search. Checking one edge is a direct lookup in a matrix, but may require scanning a neighbor list.
How does the matrix power A^k count walks, and why are walks not the same as paths?
The (i,j) entry of A^k equals the number of walks of length k from vertex i to vertex j. For example, the (A,D) entry of A^2 is 2, from walks A-B-D and A-C-D. Walks may repeat vertices and edges, so the diagonal entries of A^2 count out-and-back walks, and these counts should not be mistaken for simple paths.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →