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

by OC1014958

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