Telling Networks Apart by Shape, Density, and Loops, Explained

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

Telling Networks Apart by Shape, Density, and Loops

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.5 · lesson 82 of 879 min · free with a free account

← Graphs Through the Lens of Discrete MathematicsNext lesson: Solving Real Problems by Modeling Them as Networks →

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

Recognizing trees, DAGs, bipartite graphs, and dense or sparse graphs.

  • Test whether a graph is a tree or a forest by counting edges and pieces
  • Test whether a graph is bipartite with two-coloring
  • Detect cycles in undirected and directed graphs with depth-first search
  • Explain what a topological order and a graph's density make possible

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,242 words). Read along, or search it.

Opening Question

Family Trees, Road Maps, and Task Lists

A family tree has no loops at all. A road map is full of them. And a task list has arrows that must never loop back on themselves. All three are graphs, but they behave very differently. Knowing which kind you hold tells you which algorithms are safe, which are fast, and how to store it. So how does a program tell them apart?

Three Questions

Shape, Density, and Direction

Every graph here has n vertices and E edges. We ask it three questions. Shape: does it contain a cycle, a path that returns to its start? And is it in one connected piece? Density: how many of the possible edges are present? And direction: if the edges have arrows, can you follow them around in a circle?

Trees and Forests

Counting Edges to Rule Out Cycles

A tree is an undirected graph that's connected and has no cycle. A forest has no cycle, so each of its pieces is a tree. There's a neat counting fact. With n vertices, E edges, and c pieces, the graph has no cycle exactly when E equals n minus c. So a tree is a connected graph with exactly n minus one edges. Testing that needs no search for cycles: one scan to count the pieces, and one comparison. Run it on four graphs. The path and the tree pass. The forest has 4 edges, exactly 7 minus 3, so no cycle, but three pieces means it's not a tree. The cycle has 5 edges where a tree on 5 vertices has 4. That one extra edge is the one that closes the loop.

DAGs

Directed Graphs Without Directed Cycles

A DAG, a directed acyclic graph, is a directed graph with no directed cycle. Build tasks and course prerequisites are DAGs: nothing can depend on itself. Careful, though. In the diamond, zero to one, zero to two, one to three, and two to three, there are two routes from zero to three. Ignore the arrows and that's a loop. But you can't follow the arrows around it, so the diamond is a perfectly good DAG.

Bipartite Graphs

Two-Coloring and Odd Cycles

In a complete graph, K n, every pair of vertices is joined: n times n minus one, over two edges. K 5 has 10, and K 8 has 28. A graph is bipartite when its vertices split into two groups, with every edge running between the groups. K 3 3 joins each of three vertices to each of three others. The test is two-coloring. Color a start vertex 0, its neighbors 1, their neighbors 0, scanning breadth first. An edge joining two equal colors means it's not bipartite. Run it. The path, K 3 3, and the six-cycle color cleanly. The five-cycle fails. That's the general rule: a graph is bipartite exactly when it has no odd cycle. Colors alternate, so an odd loop returns to its start with the wrong color.

Quick Check

A Six-Cycle With One Chord

Quick check. Take a six-cycle, and add one chord, straight across, from vertex 0 to vertex 3. Does the two-coloring still succeed? Pause and predict. Yes, it's still two-colorable. Around the six-cycle, colors alternate 0, 1, 0, 1, so vertex 3 gets color 1, the opposite of vertex 0. The chord joins two different colors. It creates two new loops, each of length four, and neither is odd.

Density

Sparse Versus Dense Storage Costs

Density is the edges present, divided by the edges possible: a number from zero to one. A sparse graph's edges grow like n, as in a tree or a road map. A dense graph's edges grow like n squared, as in a complete graph. The difference decides between adjacency lists and a matrix. This program scans four graphs of 1,000 vertices both ways, and counts the places it looks at. The matrix always costs a million cells. Lists cost two entries per edge: 1,998 for the tree, 500 times less. For the complete graph, the advantage is gone. A matrix keeps one advantage the counts don't show: it answers whether u and v are joined in a single step.

Undirected Cycles

The Parent Rule

Now, cycles. A program often has to find out whether one exists. Both searches here are depth-first, but what counts as evidence differs by direction. The obvious rule says a visited vertex means a cycle. In an undirected graph that's wrong: every edge can be followed backward, straight to the parent. The parent rule skips the edge the search just came along. Any other visited vertex really does close a cycle. Run it. On the path zero, one, two, the naive rule claims a cycle. The parent rule correctly says no, and still finds the triangle.

Directed Cycles

An Edge Back Onto the Current Path

In a directed graph, reaching a visited vertex isn't enough either. In the diamond, two routes reach vertex three, with no loop. A directed cycle exists exactly when an edge leads back, to a vertex that's still on the current search path. So each vertex has three states: new, on the path, or finished. A vertex is finished when the search returns from it, with every route from it explored. Run it. In the diamond, the edge two to three reaches a finished vertex: a second route, not a loop. In the tail leading into a loop, the edge four to two reaches a vertex still on the path. That's a cycle. Both searches take order n plus E.

Quick Check

A Triangle That Is Not a Directed Cycle

Quick check. A directed graph has edges zero to one, zero to two, one to two, and two to three. Ignore the arrows, and zero, one, two form a triangle. Does the current-path rule report a cycle? Pause and predict. No cycle. The search goes zero, one, two, three. Then it backs out, finishing three, two, and one. When it tries zero to two, vertex two is already finished, not on the path. Every arrow points away from zero, so it's a DAG.

Topological Order

Lining Up a DAG So Edges Point Forward

What does knowing the kind buy you? A DAG can be lined up so that every edge points forward. That's a topological order. To find one, repeatedly remove a vertex with no incoming edge. If that gets stuck early, the vertices left over contain a cycle, so it doubles as a cycle test. With the order, hard questions become one pass. The longest path ending at each vertex comes from improving each successor, in order. Run it. The DAG lines up as 0, 1, 2, 3, 5, 4, and its longest path has length three. On the cyclic digraph, only one of four vertices gets placed.

Counting Paths

One Path in Trees, Thousands in Complete Graphs

Trees buy something too. Between any two vertices of a tree there's exactly one simple path, a path that uses no vertex twice. Cycles multiply the choices. An eight-vertex cycle offers two. In complete graphs, the count explodes: 16 in K 5, 1,957 in K 8, and 13,700 in K 9. Each added vertex multiplies the count by more than the last one did. An algorithm that tries every route is hopeless on dense graphs, and trivial on trees.

Payoff

What Knowing the Kind Buys You

So the kind is worth knowing. Trees and forests give unique paths, and a cycle test by counting. A DAG gives a topological order, and one-pass longest paths. Bipartite graphs color in order n plus E. Sparse graphs call for adjacency lists. Dense ones can use a matrix, with its one-step edge test.

Key Takeaways

Kinds of Graphs in Brief

To sum up. A tree is connected with n minus one edges. A graph is acyclic exactly when E equals n minus c. Bipartite means two-colorable, which means no odd cycle. Undirected cycle search skips the parent. Directed search looks for an edge back onto the current path. And a DAG always has a topological order.

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 Telling Networks Apart by Shape, Density, and Loops

How do you check if a graph is a tree?
An undirected graph is a tree when it is connected and has exactly n minus 1 edges for n vertices. More generally, a graph with n vertices, E edges, and c connected pieces has no cycle exactly when E equals n minus c. So one scan to count pieces and one comparison settle it, with no separate search for cycles. A forest has no cycle but may have several pieces.
How do you check if a graph is bipartite?
Check whether a graph is bipartite by two-coloring it: give a start vertex color 0, its neighbors color 1, their neighbors color 0, and so on, scanning breadth first. If any edge joins two vertices of the same color, the graph is not bipartite. A graph is bipartite exactly when it has no odd cycle, so a five-cycle fails while a six-cycle colors cleanly.
How do you detect a cycle in a directed graph?
Use depth-first search with three states per vertex: new, on the current path, or finished. A directed cycle exists exactly when an edge leads to a vertex still on the current search path. Reaching a finished vertex only means a second route, as in a diamond where vertex 0 reaches vertex 3 through both 1 and 2. The search costs order n plus E.
Why does a simple visited check report false cycles in undirected graphs?
In an undirected graph every edge can be followed backward, so a search that treats any visited neighbor as a cycle will step back to its parent and report a cycle even on a simple path. The parent rule fixes this by skipping the edge the search just came along; reaching any other visited vertex really does close a cycle. Directed graphs instead check for an edge back onto the current path.

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 →