Solving Real Problems by Modeling Them as Networks, Explained

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

Solving Real Problems by Modeling Them as Networks

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

← Telling Networks Apart by Shape, Density, and LoopsNext lesson: How Java Allocates, Tracks, and Reclaims Memory →

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

Turning friendships, roads, links, and task lists into graphs.

  • Model a problem as a graph by choosing vertices, edges, direction, and weights
  • Produce a topological order of tasks and detect impossible plans
  • Compute a project's length from a topological order and its longest chain
  • Match a modeled question to breadth-first search, shortest paths, topological sort, or components

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

Opening Question

Seven Tasks and Their Dependencies

A software team has seven tasks. Some can't start until others finish: you can't test code before it's written. In what order should the tasks run, and how many days will the project take? No algorithm can answer that until someone turns the problem into a graph. That step, modeling, is often harder than running the algorithm.

Modeling Method

Four Questions to Ask in Order

A reliable way to model is to ask four questions, in order. One: what are the things being connected? Those are the vertices. In a friend network, people. Two: what relationship joins two of them? That's an edge. Here, is friends with. Three: does the relationship work both ways, and does it carry a number? Friendship works both ways, with no number. Four: what must the answer look like? Say, who is within two friendships of me?

Friendship Network

Friend Suggestions Two Steps Away

In a friendship network, each person is a vertex, and each friendship is an undirected edge with no weight. Here are eight people. Counting friendships outward from Ana, with breadth-first search, gives everyone's distance. Ben and Cy are one step away. Dee and Eli are two. Fay is three steps away. The people exactly two steps away make natural friend suggestions. Dee shares two mutual friends with Ana, Ben and Cy, so she ranks first. Eli shares one, Cy, so he ranks lower. And Gus and Hal can't be reached at all: they form a separate group.

Follower Network

In-Degree Counts Followers

Many networks are directed. On a follower network, an edge from a to b means a follows b. Now the two degrees mean different things. The in-degree of an account is its number of followers. The out-degree is the number of accounts it follows. In a network of six accounts with ten follows, Ben has four followers, the most. Eli and Fay have none at all. Two pairs follow each other, and a pair of opposite edges behaves just like a friendship. The question, who is popular, needs the in-degree, which only exists because the model is directed.

Road Map

Kilometers or Minutes Changes the Route

On a road map, the vertices are intersections, and the edges are road segments. A two-way road is undirected. A one-way street is directed. Each road carries a weight, but which weight is a modeling choice: length in kilometers, or travel time in minutes. This map shows both. Measured in kilometers, the best route from A to F is A, D, F: eight kilometers, but thirty-two minutes. Measured in minutes, it's A, B, F: ten kilometers, but only twenty-four minutes. So the model decides the answer. A delivery van with a deadline should use minutes. A cyclist planning a day's effort may prefer kilometers.

Web Graph

A Crawler Never Finds the Old Page

On the web, each page is a vertex, and each link is a directed edge, because a link from page a to page b doesn't mean b links back. In this small website, the page called Old links to Home, but no page links to Old. A crawler that starts at Home follows links and reaches six of the seven pages. It never discovers Old, because reachability in a directed graph is one-way. Those six pages, which all reach each other, are the site's strongly connected core. And counting in-degree, the links pointing in, is the simplest way to rank pages by popularity.

Quick Check

Modeling the Lowest Airfare

Quick check. A travel site wants the lowest fare between two cities. A flight from Delhi to Pune doesn't mean there's one back, and prices differ by direction. Which model fits? Undirected with no weights, directed and weighted by fare, or undirected and weighted by distance? Pause, and decide. Directed, and weighted by fare. A one-way flight is a directed edge, and the price is the number the question asks about. Weighting by distance would find the shortest flight path, not the cheapest. The answer comes from the model you chose.

Topological Order

Tasks as a Directed Acyclic Graph

Back to the seven tasks. Model each task as a vertex, and each must-come-first rule as a directed edge: an edge from a to b means a must finish before b starts. A list of all the tasks, in an order that respects every edge, is called a topological order. One exists only if the graph has no cycle, that is, if it's a directed acyclic graph, a DAG. If testing had to come before the database, while the database leads to testing, no order could satisfy both.

Sorting Tasks

Counting Unfinished Prerequisites

The idea is to count, for every task, how many prerequisites are still unfinished. Any task with a count of zero is ready. Put it in the order, and tell each task that depends on it that one prerequisite is done. Repeat until nothing is ready. Each task and each edge is handled once, so the cost is order V plus E. On this project, the sort produced design, database, frontend, backend, testing, docs, launch. It's not the only valid order. Of all five thousand forty ways to arrange seven tasks, exactly seven respect all eight edges.

Scheduling

Sixteen Days and the Critical Chain

The order also answers the hook's second question: how many days? Process the tasks in topological order. A task can start when the last of its prerequisites finishes. Design runs from day zero to day three. Database and frontend both start on day three. Backend waits for the database, so it starts on day seven. Testing starts on day twelve, and launch finishes on day sixteen. The tasks add up to twenty-two days of work, yet the project takes sixteen, because frontend and docs run beside the main chain. That longest chain, design, database, backend, testing, launch, sets the length. Delay any task on it, and the whole project slips. Managers call it the critical chain.

Impossible Plans

A Cycle Leaves Tasks Unplaced

The sort also catches impossible plans. Suppose someone adds the rule: testing must come before the database. Now testing waits for backend, backend waits for the database, and the database waits for testing. Running the sort places only two of the seven tasks, design and frontend. The other five, the tasks on the cycle and everything waiting behind it, can never become ready. So the count of placed tasks is both the order, and a check that the plan is possible.

Quick Check

Valid Orders for Four Tasks

Quick check. A small project has four tasks, A, B, C and D. A comes before B and before C, and both B and C come before D. How many valid orders are there: one, two, or four? Pause, and decide. Two. A has no prerequisites, so it must come first, and D needs everything, so it must come last. B and C can go in either order between them: A, B, C, D, or A, C, B, D.

Choosing a Tool

Matching the Question to the Algorithm

Once the model is fixed, the question usually points to the tool. Do edges carry costs, and do you want the cheapest route? Use shortest paths, from lesson seventeen point three. Must some items come before others? Use topological sort. And remember, if it can't place everything, a cycle exists. Do you want the fewest steps, what's reachable, or separate groups? Breadth-first search, or depth-first traversal and components. Two cautions. A mismatch gives a plausible but wrong answer: breadth-first search on a road map finds the fewest roads, not the fewest kilometers. And if no tool fits, look again at what the vertices and edges stand for.

Worked Example

Fewest Terms for Six Courses

Now carry a model all the way through. A program has six courses. Courses can be taken in any number per term, as long as their prerequisites were finished in an earlier term. What's the fewest number of terms? Vertices are courses, and an edge means is a prerequisite of. The tool is a topological sort that takes, in each round, every course whose prerequisites are done. Each round is one term. Term one: Intro. Term two: Data, and Systems. Term three: Algo. Term four: Graphs. Term five: AI. Five terms, and no plan can do better, because Intro, Data, Algo, Graphs and AI form a chain where each course needs the one before it.

Worked Example

A Word Ladder From Cold to Warm

Next, a word ladder. Change cold into warm, one letter at a time, so that every step is a real word. What's the fewest number of steps? Vertices are words, and an edge joins two words that differ in exactly one letter. Undirected, and unweighted, so the tool is breadth-first search. From a list of fifty words, each four letters long, the search found cold, cord, card, ward, warm: four steps. A word like bait, one letter away from no other word in the list, sits in a component of its own, and no ladder reaches it.

Building the Graph

Blanked-Letter Patterns Instead of Pairs

Building that graph has its own trick. The obvious way compares every pair of words. With a thousand words, that's four hundred ninety-nine thousand, five hundred comparisons. Instead, give each word four patterns, each with one letter blanked out. Cord becomes underscore o r d, c underscore r d, and so on. Words that share a pattern differ in exactly one letter. A thousand words make only four thousand patterns: about a hundred twenty-five times less work.

Worked Example

Counting Islands on a Grid

Last, a map drawn as a grid of land and water. How many separate islands are there? Cells touching up, down, left, or right belong to the same island. Vertices are the land cells, and edges join land cells that touch. The tool is connected components, from lesson seventeen point two. This graph is implicit. No lists are ever built, because the neighbors of any cell can be computed from its row and column. Six islands, with sizes four, four, three, four, one and one. The two single cells touch only at a corner, so they're separate.

Key Takeaways

Modeling With Graphs in Brief

To sum up. Modeling means choosing the vertices, what an edge means, its direction and weight, and the form of the answer. Friendships are undirected. Follows and web links are directed, and their in-degree counts followers or incoming links. The weight you choose decides the best route. A topological order puts every prerequisite first. It exists only without a cycle, and the placed count checks it. The longest chain sets the project length. Then match the question to the tool.

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 Solving Real Problems by Modeling Them as Networks

How do you model a problem as a graph?
Model a problem as a graph by answering four questions in order: what things are connected, which become vertices; what relationship joins two of them, which becomes an edge; whether that relationship has a direction or carries a weight; and what form the answer must take. A friend network uses people and undirected friendships, while a road map uses intersections and road segments weighted by length or travel time.
What is a topological sort used for?
A topological sort lists the vertices of a directed graph so that every edge points forward, which puts every prerequisite before the tasks that depend on it. It is used for task scheduling, build order, and course planning. One exists only when the graph has no cycle. A common method repeatedly takes a task with zero unfinished prerequisites; if it cannot place every task, the plan contains a cycle.
How do you find the minimum time to finish a project with dependencies?
Process the tasks in topological order and start each one when the last of its prerequisites finishes; the project ends when the latest task finishes. The longest chain of dependent tasks, often called the critical path or critical chain, sets the length, so delaying any task on it delays the whole project. In one example, tasks totaling 22 days finish in 16, because some run beside the main chain.
Why is breadth-first search the wrong tool for road-map routes?
Breadth-first search finds the route with the fewest edges, which is the right answer only when every edge counts the same. On a road map, roads have different lengths or travel times, so the fewest roads can give a plausible but wrong route. Weighted questions need a shortest-path algorithm, and the chosen weight, kilometers or minutes, itself changes which route is best.

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 →