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

• School: Cornell University
• Department: Computer Science
• Course: CS 2110
• Professor: Gries

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); }}