Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:bowmang:chapter3 [2018/01/30 03:08] – created bowmang | courses:cs211:winter2018:journals:bowmang:chapter3 [2018/02/07 07:02] (current) – bowmang | ||
|---|---|---|---|
| Line 3: | Line 3: | ||
| ===== Chapter 3.1 (Basic Definitions and Applications of Graphs) ===== | ===== Chapter 3.1 (Basic Definitions and Applications of Graphs) ===== | ||
| - | Definition | + | __Definition |
| * Graph = way of encoding pairwise relationships among a set of objects | * Graph = way of encoding pairwise relationships among a set of objects | ||
| * Consists of a collection of both nodes and edges | * Consists of a collection of both nodes and edges | ||
| Line 14: | Line 14: | ||
| * Where the edge points from is the tail of the edge | * Where the edge points from is the tail of the edge | ||
| - | Examples | + | __Examples |
| * Transportation network - nodes are airports while edges are possible flights | * Transportation network - nodes are airports while edges are possible flights | ||
| * Communication network - nodes are computers while edges are direct links or within signal reach | * Communication network - nodes are computers while edges are direct links or within signal reach | ||
| Line 20: | Line 20: | ||
| * Dependency network - nodes are college courses while directed edges signify prerequisites. | * Dependency network - nodes are college courses while directed edges signify prerequisites. | ||
| - | Paths and Connectivity | + | __Paths |
| * Two types of paths - simple and cycle | * Two types of paths - simple and cycle | ||
| * Simple - sequence of connected distinct nodes | * Simple - sequence of connected distinct nodes | ||
| Line 30: | Line 30: | ||
| * Distance - minimum number of edges between two nodes | * Distance - minimum number of edges between two nodes | ||
| - | Trees | + | __Trees__ |
| * Definition = undirected graph that is connected and does not contain a cycle | * Definition = undirected graph that is connected and does not contain a cycle | ||
| * Root = from what the rest of the tree "hangs off of". | * Root = from what the rest of the tree "hangs off of". | ||
| Line 37: | Line 37: | ||
| * Leaf = node with no children | * Leaf = node with no children | ||
| * Every n-node tree has exactly n-1 edges | * Every n-node tree has exactly n-1 edges | ||
| + | |||
| + | ===== Chapter 3.2 (Graph Connectivity and Graph Traversal) ===== | ||
| + | |||
| + | __Maze-Solving Problem__ | ||
| + | * S-T connectivity problem (if you have a node s and a node t, is there a path between the two) | ||
| + | * Two algorithms to solve this problem are Breadth-First Search (BFS) and Depth-First Search (DFS) | ||
| + | |||
| + | __Breadth-First Search__ | ||
| + | * Algorithm ( O(n + m) ) | ||
| + | * Start with node s | ||
| + | * Add nodes one layer at a time (everything that s is connected to) | ||
| + | * Continue to add all additional nodes that are connected by an edge to any of the nodes in the first layer | ||
| + | * Repeat until no new nodes can be found. | ||
| + | * Whatever layer node t is in can determine the minimum distance between it and node s | ||
| + | * Breadth-First Search creates a tree with the root at node s | ||
| + | |||
| + | __Depth-First Search__ | ||
| + | * Algorithm ( O(n + m) ) | ||
| + | * Start with node s | ||
| + | * For each node adjacent to node s: | ||
| + | * If unexplored: | ||
| + | * Run algorithm recursively on said node | ||
| + | * | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
