PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Somewhat Frequent
 0/7

Introduction to Graphs

Authors: Darren Yao, Benjamin Qi

Visualizing problems as graphs with resources covering basic terminology.

Note: Graphs will become a key topic in higher divisions. For Bronze, graphs are just a nice way to think about the structure of our data.

Graphs can be used to represent many things, from images to wireless signals, but one of the simplest analogies is to a map. Consider a map with several cities and bidirectional roads connecting the cities. Some problems relating to graphs are:

  1. Is city AA connected to city BB? Consider a region to be a group of cities such that each city in the group can reach any other city in said group, but no other cities. How many regions are in this map, and which cities are in which region? (Silver)

  2. What's the shortest distance I have to travel to get from city AA to city BB? (Gold)

For now, it suffices to learn how graphs are represented (usually adjacency lists).

Resources
CSAinteractive
CSAinteractive - adjacency lists and matrices
CPHgraph terminology, representation
IUSACOgraph basics and representation, trees
PAPSadjacency matrices, lists, maps

What Does a Bronze Graph Problem Look Like?

All of the problems below fall into at least one of the following two categories:

  • The graph's structure is special (it's a tree, path, or a cycle).
  • To solve the problem, all you need to do is iterate over the adjacency list of every vertex.

Knowing DFS can be helpful but it should not be required.

Problems

StatusSourceProblem NameDifficultyTagsSolution
SilverNormal
Show Tags

tree, coloring

External Sol
BronzeHard
Show Tags

coloring

External Sol
BronzeHard
Show Tags

path

External Sol
BronzeHard
Show Tags

tree

External Sol
BronzeHard
Show Tags

permutation, cycle

External Sol
BronzeVery Hard
Show Tags

tree

External Sol
BronzeVery Hard
Show Tags

tree

External Sol

Module Progress:

Give Us Feedback on Introduction to Graphs!

PrevNext