How Different Connection Types Change a Network

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

How Different Connection Types Change a Network

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

← Graphs and Their RepresentationsNext lesson: Cheapest Routes in a Weighted 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

Directed and weighted edges, depth-first traversal, and strong connectivity.

  • Distinguish directed, undirected, weighted, and unweighted edges and how each is stored
  • Trace depth-first traversal and explain its order V plus E cost with adjacency lists
  • Find connected components with repeated traversals
  • Test a directed graph for strong connectivity with a forward and a reversed traversal

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

Opening Question

Can Visitors Click Their Way Anywhere

A website's pages link to one another. Can a visitor get from any page to any other, just by clicking links? A friendship works both ways, but a web link doesn't. A road has a length, and a friendship has none. Those differences change how a network is stored, which questions make sense, and how we answer them. By the end, we'll have a two-step test for that website.

Edge Types

Directed or Undirected, Weighted or Not

Every edge answers two questions. Does it have a direction? And does it carry a number? An undirected edge works both ways, like a friendship or a two-way road. A directed edge goes one way only, like a follow, a web link, or a prerequisite. An unweighted edge only records that a connection exists. A weighted edge carries a number: a length, a cost, a time, or a capacity.

Storage

Stored at Both Ends or One End

Direction changes the storage. This sample has five vertices and six weighted edges, and the program stores them twice: undirected, then directed. In an adjacency list, an undirected edge goes in at both ends. A directed edge goes in once, where it starts. Each entry keeps its weight beside the neighbor. Run it. Undirected, the degrees are 2, 3, 3, 3, 1, adding up to 12: twice the six edges, since each edge counts at both ends. Directed, the out-degrees add up to six: one entry per edge. In a matrix, undirected edges fill a symmetric pattern, and directed ones don't.

Edge Limits

How Many Edges Are Possible

Direction also changes how many edges are possible. With n vertices, an undirected graph has at most n times n minus one, over two: each pair joined once. A directed graph can have twice that, since a to b and b to a are different edges. For 100 vertices, that's 4,950 against 9,900. Weights, though, change only the storage: a number beside each neighbor. Which vertices you can reach depends only on which edges exist. So the traversals in this lesson ignore weights. Weights matter for the cheapest route, in lesson 17.3.

Depth-First Traversal

Follow One Path, Then Back Up

Now explore a graph. A traversal visits every vertex reachable from a start. Depth-first traversal follows one path as far as it can go. Only at a dead end does it back up, to the most recent vertex that still has an unvisited neighbor. The call stack remembers the way back. It must mark each vertex as visited the moment it arrives. Otherwise, a cycle would send it round forever. Here are seven vertices and eight edges, with neighbors in alphabetical order. From A, the path runs A, B, D, E, F, then C. It backs up to F to reach G. Breadth-first search, from lesson 10.5, would visit the same vertices, level by level: A, B, C, D, E, F, G. Only the order differs.

Running Time

Lists Versus a Matrix for Traversal

What does it cost? Depth-first traversal marks each vertex once, and with adjacency lists, it reads each list entry once. That's V plus 2E steps for an undirected graph, so order V plus E. With a matrix, finding a vertex's neighbors means scanning a whole row of V cells. So a matrix costs order V squared, however sparse the graph. With 100,000 vertices and 300,000 edges, lists hold 600,000 entries. A matrix has 10 billion cells.

Quick Check

Reverse Alphabetical Neighbor Order

Quick check. Same graph, same start at A. But now each vertex takes its neighbors in reverse alphabetical order, from Z down to A. Which four vertices are visited first? Pause and predict. A, C, F, G. From A, the later neighbor is C. From C, only F is new. F's neighbors are G, E, and C, so G comes first. G is a dead end, so the search backs up to F, and then goes on to E. E isn't fourth, because G came first.

Recursion Limit

An Explicit Stack for a Million-Vertex Chain

Recursion has a limit. Each level of the path being followed takes one stack frame, and the stack has a fixed size. Here's a graph shaped like one long chain: a million vertices, each linked to the next. Recursive traversal would need a million frames. Run it. The recursive version overflows the stack. The remedy is an explicit stack of vertices still to visit, and that version reaches all million. On other graphs, the explicit-stack version reaches the same vertices, though the order can differ.

Components

Labeling Pieces With Repeated Traversals

A vertex w is reachable from v if some path leads there. In an undirected graph that works both ways, so the graph splits into separate pieces. A connected component is a largest group of vertices that all reach one another. To find them all, start a traversal at any unlabeled vertex, and label everything it reaches. Repeat until every vertex has a label. Each vertex and edge is still handled once, so the total stays order V plus E. Here, ten vertices and seven edges. The labels show four components. Vertex 9 has no edges at all, so it's a component of its own.

Random Networks

The Sudden Giant Component

How connected are random networks? Take 1,000 vertices, and add edges at random. The change is sudden, not gradual. In one test, with one connection per vertex on average, the largest piece held only about 83 vertices. With four connections per vertex, about 978 of the 1,000 were in one giant component. So a network doesn't need to be dense to be almost fully connected.

Strong Connectivity

Forward and Reversed Traversals

In a directed graph, reachability isn't symmetric. You might reach b from a, with no way back. A directed graph is strongly connected if every vertex can reach every other. It's only weakly connected if it's in one piece once you ignore the directions. This sample has seven vertices. Zero, one, and two form a cycle. So do three, four, and five. But once you cross from the first group to the second, there's no way back. A fast test: traverse from vertex zero along the edges, then along every edge turned around. If both reach everything, any vertex can get to any other through zero. Run it. Forward reaches 6 of 7, and reversed only 4. Not strongly connected. Add one edge, 5 to 6, and both reach all 7.

Application

The Website Test

That's the website test from the start. Traverse the links forward from the home page, then backward. If either traversal misses a page, the site isn't strongly connected. Some visitor can wander into a section with no link back out. The cost is two traversals: order V plus E in all.

Quick Check

Forward Reaches All, Reversed Does Not

Quick check. A directed graph has edges zero to one, one to two, two to zero, and two to three. Run the two-traversal test from zero. What does the program print? Pause and predict. Four, then three. Forward from zero reaches all four vertices. But in the reversed graph, the only edge at three leads out of it, so a traversal from zero never arrives there. So three can't get back to zero, and the graph isn't strongly connected. Reaching everything forward isn't enough: both traversals must.

Key Takeaways

Connection Types in Brief

To sum up. An edge may be directed or undirected, and weighted or unweighted. An undirected edge is stored at both ends. A directed edge is stored once, where it starts. Depth-first traversal costs order V plus E with lists. Use an explicit stack for very deep graphs. Components come from repeated traversals. Strong connectivity takes two: forward, and reversed.

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 How Different Connection Types Change a Network

What is the difference between a directed and an undirected graph?
In an undirected graph each edge works both ways, like a friendship, while in a directed graph each edge goes one way, like a web link or a follow. In an adjacency list, an undirected edge is stored at both endpoints and a directed edge only where it starts. With n vertices, a directed graph can have up to n(n-1) edges, twice the undirected maximum of n(n-1)/2.
How does depth-first search work?
Depth-first search follows one path as far as it can, and only at a dead end backs up to the most recent vertex that still has an unvisited neighbor. It marks each vertex as visited the moment it arrives, so cycles cannot trap it. With adjacency lists it costs order V plus E. On very deep graphs, an explicit stack avoids the stack overflow a recursive version can hit.
How do you check if a directed graph is strongly connected?
Run a traversal from any vertex along the edges, then another from the same vertex with every edge reversed. The graph is strongly connected exactly when both traversals reach every vertex, because then every vertex can reach the start and the start can reach every vertex. The test costs order V plus E. Reaching everything in the forward direction alone is not enough.
What is the difference between strongly and weakly connected graphs?
A directed graph is strongly connected if every vertex can reach every other along the edge directions, and weakly connected if it forms one piece once directions are ignored. For example, two cycles joined by a single one-way edge are weakly connected but not strongly connected, because once a path crosses from the first cycle to the second, there is no way back.

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 →