COMPSCI 61B Lecture Notes - Lecture 26: Eulerian Path, Isomorphism, Adjacency Matrix
1 Jun 2017
School
Department
Course
Professor
Document Summary
Graph: a set of nodes (a. k. a vertices) connected pairwise by edges. Undirected: no notion of directionality, and we can traverse the edges either way. Acyclic: no cycles exist in such a graph. A path is a sequence of vertices connected by edges. A cycle is a path whose rst and last vertices are the same. Two vertices are connected if there is a path between them. If all vertices are connected, we say the graph is connected. Graph problems: un-obvious which are easy, hard, or computationally intractable. Number nodes irrespective of label, and use number throughout the graph implementation. For undirected graph: each edge is represented twice in the matrix. Representation 2: edge sets: collection of all edges. Example: hashset, where each edge is a pair of ints. Common approach: maintain array of lists indexed by vertex number. Most graphs are sparse (not many edges in each bucket)
