CS 2110 Lecture Notes - Lecture 19: Adjacency Matrix, Linked List, Dfs Furniture

44 views2 pages
user avatar
Published on 14 Jun 2017
School
Cornell University
Department
Computer Science
Course
CS 2110
Professor
Lecture 19 - More Graphs!
oRecall, there are two ways we can represent a graph
Adjacency List
Adjacency Matrix
Look at last lecture for examples
oWhich one is better?
Depends on properties of the graph and what kind of algorithms you plan
on executing on it
oRecall DAG’s
Directed Acyclic Graphs
No cycles!
oGraph Algorithms
Search
Depth-first-search
Given a graph and a node u, we want to visit each node reachable
from u
Essentially, we want to find all possible nodes that
someone can get to along a path from u
What things to we need to keep track of?
There may be multiple paths to the same node v
It would be a waste of time to double count
boolean[] visited;
If node v has been visited, then visited[v] is true
To visit v, visited[v] must be set to true.
v is REACHABLE* from u if there is a path (u, …,
v) in which all nodes of the path are unvisited.
Recursively
public static void dfs(int u) {
visited[u] = true;
for all edges (u, v) leaving u {
if v is unvisited then dfs(v); }}
Worst-case runtime - O(e*n)
For loop will be at most e edges
And worst case call this on all n elements
Worst-case space - O(n)
Imagine a linked list
Call stack will have n frames
Iteratively
Use a stack!
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Lecture 19 - more graphs: recall, there are two ways we can represent a graph. Depends on properties of the graph and what kind of algorithms you plan on executing on it: recall dag"s. Given a graph and a node u, we want to visit each node reachable from u. Essentially, we want to find all possible nodes that someone can get to along a path from u. There may be multiple paths to the same node v. It would be a waste of time to double count boolean[] visited; If node v has been visited, then visited[v] is true. To visit v, visited[v] must be set to true. v is reachable* from u if there is a path (u, : in which all nodes of the path are unvisited. Recursively public static void dfs(int u) { visited[u] = true; for all edges (u, v) leaving u { if v is unvisited then dfs(v); }}