CSE 274 Lecture Notes - Lecture 14: Topological Sorting
Document Summary
Graph is collection of distinct vertices and distinct edges. Path between two vertices in a graph is a sequence of edges. The length of a path is the number of edges that it comprises. A cycle is a path that begins and ends at the same vertex. When finding paths, we have multiple choices. Weights or costs labeled to calculate weight of a path. Connected: graph that has a path between every pair of distinct vertices. Complete: graph that has an edge between every pair of distinct vertices. Vertices: adjacent in an undirected graph is they are joined by an edge. The first being that all trees are graphs, but not all graphs are trees. Graphs can also be used to represent airline routes, mazes, and course prerequisites. Starts at beginning and goes to each node that it points to, then each node that they point to, etc . Creates vertex and then puts the items in traversal order.