CS234 Lecture Notes - Lecture 12: Adjacency List
25 Sep 2017
School
Department
Course
Professor
Document Summary
Undirected graph: a speci c type of tree: ordering of nodes doesn"t matter. Every node that is adjacent to the node is neighbor of the node. Incident: an edges is incident to a node if they are connected. Degree: of a node is the number of edges connected with it. Path: a set of nodes that you will follow to get one node from another. Depth- rst search: visits all nodes, and check if a node"s neighbors are all visited, if visited then mark as black, otherwise keep visiting. Mark every node that has all of its neighbors visited. Doesn"t compute any node to every node, but starts from a source node s to the shortest path of the designated node t . Distance from a node to itself is 0. Assume that there is in nite costs between every node (paths) until we have found a path. Adjacency list: relax all edges pointing from the source node.
