CSE 274 Lecture Notes - Lecture 15: Adjacency List, Adjacency Matrix, Insertion Sort
6 Dec 2018
School
Department
Course
Professor
Document Summary
Array: typically a two-dimensional array called an adjacency matrix. List: referred to as an adjacency list. In this example, the matrix has the node on the left and puts a true to the things that is connected to on the right. In this example, we see a node for each vertice that has a list of adjacent nodes that are the connected vertices. Items can be added anywhere is list. Advantages of linked implementation: uses memory only as needed, when an entry is removed, unneeded memory is returned to the system, and it avoids moving data when adding or removing entries. Collection of pairs (k, v) of objects k and v. Choses one entry in array called the pivot. Pre-order traversal: visit root before we visit the root"s subtrees. In-order traversal: visit root of binary tree between visiting nodes in root"s subtrees. Post-order traversal: visit root of binary tree after visiting nodes in root"s subtrees.
