Graphs and Their Representations, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.1 Free with a free account

Graphs and Their Representations

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.1 · lesson 78 of 8711 min · free with a free account

← Huffman Coding: Shorter Codes for Frequent CharactersNext lesson: How Different Connection Types Change a Network →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Graph vocabulary and three ways to store a graph in Java.

  • Define vertices, edges, degree, paths, cycles, and connected components
  • Use the degree-sum rule to check that a graph was built correctly
  • Compare adjacency matrices, adjacency lists, and edge lists on space and operation costs
  • Choose a graph representation from a graph's density and size

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

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

Opening Question

Chains of Friends and the Most Friends

Can Asha reach Farid through a chain of friends? And who in the group has the most friends? An array can hold all eight names in a row. But neither question is about a row. Both are about who is connected to whom. The structure built for connections is the graph. By the end of this lesson, both questions have short, direct answers.

Definition

Vertices, Edges, and Modeling Choices

A graph is a set of things, called vertices, together with a set of edges. Each edge joins two vertices. To model anything as a graph, you decide two things: what the vertices are, and what it means for two of them to be joined. On a road map, the vertices are towns, and an edge is a road between two of them. In a friend network, the vertices are people, and an edge means they're friends. For an exam timetable, the vertices are exams, and an edge means at least one student takes both. Two joined exams can't be held at the same time. In a maze, the vertices are rooms, and the edges are doorways. Is there a way from the entrance to the exit? That's a question about the graph.

Vocabulary

Adjacency and Degree

Here's the graph used through this lesson: six vertices, numbered zero to five so they can be array indexes, and seven edges. Two vertices joined by an edge are adjacent. They're neighbors. Two and four are adjacent. Zero and three are not. The degree of a vertex is its number of edges, which is also its number of neighbors. Vertex one has degree three. Vertex five has degree one.

Paths and Cycles

Walking Along Adjacent Vertices

A path is a sequence of vertices in which each consecutive pair is adjacent. Its length is the number of edges it uses. Zero, one, three, four, five is a path of length four. A cycle is a path that comes back to where it started, without repeating any other vertex. Zero, one, two, and back to zero is a cycle of length three.

Degree Sum

Degrees Add Up to Twice the Edges

Now add up all six degrees: two, three, three, two, three, one. The total is fourteen, exactly twice the seven edges. That's no accident. Each edge touches two vertices, so it adds one to two degrees. In code, that makes a cheap check that a graph was built correctly: the degrees must add up to twice the number of edges.

Connectivity

When a Graph Falls Into Pieces

A graph is connected if a path joins every pair of vertices. Take the same graph, and remove two edges: two to four, and three to four. Now no path joins zero to five. The graph has fallen into separate pieces. Each piece is called a component: a largest group of vertices that can all reach one another. Here the components are zero, one, two and three, and then four and five.

Counting Components

A Stack and Seen Flags

A program can count the components. Start at any vertex not yet seen, and visit everything reachable from it. That's one component. Then move on to the next unseen vertex, and repeat. The graph is connected exactly when the count is one. The code keeps a seen flag for every vertex, and a stack of vertices still to explore. A vertex is marked the moment it goes on the stack, so it never goes on twice. Run on the whole graph, the count is one. Without those two edges, the count is two.

Quick Check

An Odd Degree Sum of Seventeen

Quick check. A program reads nine edges from a file, and builds a graph. Then it adds up every degree, and gets seventeen. What does that tell you? Is the graph in two pieces, does it contain a cycle, or is an edge stored at one end only? Pause, and decide. An edge is stored at one end only. Nine edges must give a degree sum of eighteen, so an odd total is impossible in a correct graph. Pieces and cycles never change the total. Only a half-stored edge can, because it adds one to a single degree, instead of two.

Adjacency Matrix

A Cell for Every Ordered Pair

To work with a graph, a program has to store it. Three ways are common. The first is an adjacency matrix: a table with a row and a column for every vertex. The entry in row u, column v, says whether u and v are adjacent. For six vertices, that's thirty-six cells: one for every ordered pair, whether or not they're joined. For an undirected graph the matrix is symmetric. The entry for one, three always equals the entry for three, one, so adding an edge must set both. And testing whether two vertices are adjacent is a single array read.

Adjacency List

Only the Neighbors That Exist

The second way is an adjacency list: for every vertex, a list of only the neighbors it really has. Zero's list holds one and two. Four's list holds two, three and five. An undirected edge appears twice, once in each endpoint's list, so the lists hold two times E entries in all. Here, that's fourteen. Finding the neighbors of a vertex means handing back its list, and its degree is just the length of that list.

Edge List

One Entry per Edge

The third way, the edge list, is the simplest of all: one entry per edge, so E entries. Seven, here. It's the natural form for a file of data, and the easiest to build. But almost any question about one vertex means scanning the whole list.

Operation Costs

Space, Edge Tests, and Neighbor Lists

All three describe the same graph, so they always give the same answers. What differs is how much work each answer takes. Space first. The matrix needs V squared cells. The lists need V plus E. The edge list needs E. Is there an edge from u to v? The matrix answers in one read. The adjacency list scans u's neighbors. The edge list may scan every edge. To list the neighbors of u, the matrix must read a whole row of V cells, while the adjacency list hands back only the real neighbors. And visiting every neighbor of every vertex costs V squared for the matrix, but only V plus E for the lists.

Measurement

Counting Reads on Random Graphs

Counting the work makes the difference concrete. Take random graphs with two thousand vertices. To visit every neighbor of every vertex, the matrix reads all four million cells, whatever the density, because it has to look at the missing edges too. The lists read two times E entries. With six thousand edges, that's twelve thousand entries: a few hundred times fewer. For a single edge test, the pattern reverses. The matrix reads one cell, while the list scans u's neighbors. That's about six comparisons on the sparse graph, and about seven hundred fifty when half of all possible edges are there.

Memory Limits

Ten Billion Cells Will Not Fit

Memory can settle the question before speed does. A road network, or a social network, might have a hundred thousand vertices. A matrix would need a hundred thousand times a hundred thousand cells: ten billion, about ten gigabytes at one byte each. Ask Java for that with a 256-megabyte heap, and the program stops with an OutOfMemoryError. The adjacency list holds only the edges that exist, and fits easily. The two only meet on dense graphs. A list of plain ints uses about as much memory as the matrix, once roughly a quarter of all possible edges are present.

Quick Check

Products Bought Together

Quick check. A store's app has five thousand products as vertices, and an edge joins two products often bought together. About half of all possible pairs are joined. The app tests millions of pairs, asking whether two products are joined. Should it store a matrix, adjacency lists, or an edge list? Pause, and decide. A matrix. Five thousand squared is twenty-five million cells, about twenty-five megabytes, which fits easily. And every pair test is one read. With half of all pairs joined, each adjacency list holds about twenty-five hundred neighbors, so every test is a long scan. And an edge list would scan millions of edges.

Decision Guide

Density and the Most Common Operation

So the choice comes down to two questions: how dense is the graph, and which operation does the program need most? A sparse graph, where E isn't much bigger than V, belongs in adjacency lists. A dense graph, or a program doing many edge tests, suits a matrix. A very large graph needs lists, because the matrix may not fit. Data read once from a file can stay an edge list, and be converted before queries. And a small graph of a few hundred vertices? All three are fast enough, so pick the simplest.

Worked Example

Can Asha Reach Farid

Back to Asha and Farid. To build their graph, a hash map turns each name into a number from zero to seven, so the names can be array indexes. Nine friendships become nine edges in an adjacency list. Cara has four friends, the most of anyone, and the degrees add up to eighteen, twice the nine friendships. Can Asha reach Farid? A search from Asha, with the same stack and seen flags, follows a chain: Asha, Cara, Esha, Farid. So, yes. Asha can't reach Gita, though. Gita and Hari form a second component, and the program counts two. Notice what the graph answered: whether a chain exists. Which chain is shortest is a question for the coming lessons.

Common Mistakes

Four Bugs in Graph Code

Four mistakes cause most bugs in graph code. Setting only one cell of the matrix for an undirected edge. The graph then says zero is joined to one, but one isn't joined to zero. Adding the same edge twice to a list. A person with one friend then shows degree two. Numbering vertices from one instead of zero. Vertex six, in a graph of six vertices, throws an ArrayIndexOutOfBoundsException. And exploring without marking vertices as seen. On a simple triangle, the search goes round and round, and never stops.

Key Takeaways

Graphs and Their Storage in Brief

To sum up. A graph is vertices and edges, and modeling means deciding what each one stands for. The degrees always add up to twice the edges, and a graph is either connected, or it falls into components. A matrix answers an edge test in one read, but needs V squared cells. Lists hold two E entries, and visit only real neighbors. Sparse and very large graphs belong in lists. Dense graphs with many edge tests suit a matrix.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 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 All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 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

Data Structures and Algorithms 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 Graphs and Their Representations

What is the difference between an adjacency matrix and an adjacency list?
An adjacency matrix is a V by V table whose entry in row u, column v records whether u and v are adjacent, while an adjacency list stores, for each vertex, only the neighbors it really has. The matrix needs V squared cells but answers an edge test in one read. The lists need space proportional to V plus E and visit only real neighbors, which suits sparse graphs.
Why does the sum of degrees equal twice the number of edges?
The degrees of an undirected graph add up to twice the number of edges because each edge touches two vertices and adds one to each of their degrees. For example, a graph with seven edges has a degree sum of fourteen. This gives a cheap correctness check in code: an odd total, such as seventeen for nine edges, means some edge was stored at only one end.
What is a connected component in a graph?
A connected component is a largest group of vertices that can all reach one another through paths. A graph is connected when it has exactly one component. To count components, start a search at any unseen vertex, mark everything reachable as seen, count one component, and repeat from the next unseen vertex. Marking each vertex the moment it goes on the stack keeps it from being added twice.
When should you use an adjacency matrix instead of an adjacency list?
Use an adjacency matrix when the graph is dense or the program performs many edge tests, and the matrix fits in memory. For 5,000 vertices, 25 million one-byte cells take about 25 megabytes, and each pair test is a single read. For a sparse or very large graph, use adjacency lists: a 100,000-vertex matrix would need ten billion cells, about ten gigabytes.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 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 Data Structures and Algorithms 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 Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 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 3 credits in Data Structures and Algorithms.

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

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →