Class Notes (1,100,000)
US (490,000)
Cornell (1,000)
CS (100)
CS 2110 (30)
Gries (30)
Lecture 18

CS 2110 Lecture Notes - Lecture 18: Directed Acyclic Graph, List Of Algorithms, Topological Sorting


Department
Computer Science
Course Code
CS 2110
Professor
Gries
Lecture
18

This preview shows page 1. to view the full 4 pages of the document.
Lecture 18 - Graphs
oWe ARE NOT talking about graphs like bar graphs, circle graphs
oWe are talking about shit like the brain, like correspondence between people
Like the Mono web!!!
This is a Spring 2017 thing for you future readers
Airline transport graphs
Graphical models that can recogniz a face through pixels and shit
Abstract graphs
Don’t worry bout it right now bro
oDirected graph
Has directed lines
Also known as (digraph)
A directed graph is a pair (V, E), where
V is a finite set
E is a set of ordered pairs (u, v) where u, v are in V
Often require u != v
Element of V is called a vertex or node
Element of E is called an edge or arc
|V| is size of V
oUndirected Graph
Like a directed graph but no arrows, just lines connecting stuff
Literally like the mono web
Can easily be converted to a directed graph by turning each line to an
arrow in both directions
oGraph Terminology
Vertices u and v are called the source and sink
Two vertices are adjacent if they are connected by an edge
The outdegree of a vertex is the number of edges that go out
The indegree of a vertex is the number of edges that go in
degree
A path is a sequence of vertices from u to v
The length of a path is its number of EDGES
NOT VERTICES
A cycle is a path that starts and ends at the same node
A cycle is simple if it does not repeat any vertices except the first and last
A graph is acyclic if it has no cycles
A directed acyclic graph is called a DAG
Pretty cool stuff
oDAG
If a directed graph is a DAG, there must be a vertex with indegree 0
We can start to think of an algorithm
A digraph is a DAG if and only if we can iteratively delete
indegree-0 nodes until the graph disappears
This algorithm is called a topological sort
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version