CSC 345 Study Guide - Final Guide: Directed Acyclic Graph, Graph Traversal, Adjacency List

• School: University of Arizona
• Department: Computer Science Main
• Course: CSC 345
• Professor: Lu

Document Summary

Graphs: definition, a graph g=(v,e) consists of a collection v of vertices (nodes), and a collection e of edges, each of which join two verticies, two kinds of graphs, undirected. An edge e in e is a pair of nodes in v e = u, v{ u, v v u and v are ends of e: directed. A directed edge, e", is an ordered pair, (u,v), we call u the tail of e" and v is the head of e". How to implement a graph (graph representation: 1) adjacency matrix (array, 2) adjacency list, n vertices and m edges. Size: o(n^2), finding the number of adjacent nodes: o(n) Adjacency list: (array of size n: adj[n] = [ [0 -> 1 - > 3 ], [1 -> 0 -> 2 -> 3 ->4 ] , Graph traversal: (search operation: have a graph and want to know if two nodes are connected by a path.