Introduction to GraphsGraph TraversalsCS 311 Data Structures and AlgorithmsLecture SlidesMonday, December 7, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell7 Dec 2009 CS 311 Fall 2009 2Unit OverviewTables & Priority QueuesMajor Topics Introduction to Tables Priority Queues Binary Heap algorithms Heaps & Priority Queues in the C++ STL 2-3 Trees Other balanced search trees Hash Tables Prefix Trees Tables in various languagesDONE7 Dec 2009 CS 311 Fall 2009 3The Rest of the CourseOverviewTwo Topics External Data Throughout this semester, we have dealt-with data stored in memory. What if we store data on an external device, accessed via a (relatively) slow connection. How does this change the design of algorithms and data structures? Graph Algorithms A graph is a way of modeling relationships between pairs of objects. This is a very general notion; thus, algorithms for graphs often have very general applicability.7 Dec 2009 CS 311 Fall 2009 4ReviewExternal Data — Introduction, Sorting, Tables: Hash TableWe considered data that are accessed via a slow channel. Overriding concern: Minimize use of the channel.Often, the channel transmits data in chunks: blocks. Thus: Minimize the number of block accesses.Sorting Stable Merge works well with block-access data. Use temporary files for the necessary buffers. Result: Reasonably efficient external Merge Sort.Table Implementation — Hash Table Avoid open addressing. Each bucket takes one block (or some small number of blocks?).Client Server“Here”: Where our program runs“There”: Has data storageSlow channel7 Dec 2009 CS 311 Fall 2009 5ReviewExternal Data — Tables: B-Trees [1/3]A B-Tree of degree m (m is odd) is essentially an (m+1)/2 … mTree. Each node has (m–1)/2 up to m–1 items. Exception: The root can have 1 … m–1 items. All leaves are at the same level. All non-leaves have 1 more child than # of items. Order property holds, as for 2-3 Trees and 2-3-4 Trees.A 2-3 Tree is precisely a B-Tree of degree 3. Degree = max # of children = # of items in an overfull node.Below is an example of a B-Tree of degree 7. In practice, a B-Tree could have much higher degree than this.12 58 842 7 10 15 27 28 34 39 52 87 88 91 93 9860 63 71 81Terminology varies. This is what the text uses.7 Dec 2009 CS 311 Fall 2009 6ReviewExternal Data — Tables: B-Trees [2/3]How B-Tree Algorithms Work Retrieve Like other search trees. Traverse Like other search trees (generalized inorder traversal). Note that we need only read each block once, if we have in-memory storage for h blocks, where h is the height of the tree. Insert Generalizes 2-3 Tree Insert algorithm: Find the leaf that an item “should” go in. Insert into this leaf. If overfull, split it and move up the middle item, recursively inserting it in the parent node. If the root becomes overfull, split and create a new root. Delete Generalizes 2-3 Tree Delete algorithm.7 Dec 2009 CS 311 Fall 2009 7ReviewExternal Data — Tables: B-Trees [3/3]Here is an illustration of B-Tree insert. We insert 40 into this B-Tree of degree 7.12 58 842 7 10 15 27 28 34 39 52 87 88 91 93 9860 63 71 8112 58 842 7 10 15 27 28 39 40 52 87 88 91 93 9860 63 71 813412 58 842 7 10 15 27 28 39 40 52 87 88 91 93 9860 63 71 81347 Dec 2009 CS 311 Fall 2009 8ReviewExternal Data — Tables: B+ TreesA common variation of a B-Tree is a B+ Tree. All data (the non-key portion of the value) is in the leaves. Keys in non-leaf nodes are duplicated in the leaves. Leaves are typically joined in an auxiliary Linked List. This minimizes the number of block accesses required for a traversal. Otherwise, same as a B-Tree.From the Wikipedia “B+ Tree” article (4 Dec 2009):btrfs, NTFS, ReiserFS, NSS, XFS, and JFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASI, PostgreSQL, Firebird and MySQL support this type of tree for table indices. Key-value database management systems such as Tokyo Cabinet and Tokyo Tyrant support this type of tree for data access.12 58 842 7 10 15 27 28 39 40 52 84 88 91 93 9860 63 71 813412 34 58 87Each key in a non-leaf node is duplicated in a leaf node.Data for key 84 are only stored here.Auxiliary Linked List7 Dec 2009 CS 311 Fall 2009 9ReviewExternal Data — Tables: Reliability IssuesIn practice, external storage is significantly less reliable than a computer’s main memory.Consider: What happens if the communications channel to externalstorage device fails in the middle of some algorithm? The data on the device may be left in an intermediate state.How can we take this into account when designing algorithms thatdeal with data on external storage? As much as possible, the intermediate state of data should be either: A valid state, Or, if that is not possible, a state that can easily fixed (made valid).In particular: When writing the equivalent of a pointer to data on an external storage, write the data first, then the pointer.7 Dec 2009 CS 311 Fall 2009 10Introduction to GraphsDefinitionA graph is consists of vertices and edges. An edge joins two vertices. An example of a graph is shown at right.Sometimes we give each edge a direction. The result is a directed graph or digraph.Graphs represent situations in which objects are related in pairs.vertex edge7 Dec 2009 CS 311 Fall 2009 11Introduction to GraphsApplicationsWe use graphs to model: Networks Vertices are nodes in network; edges are connections. Examples Communication Transportation Electrical Web (edges are links) State Spaces Vertices are states; edges are transitions between states. See CS 451 for more info. Generally, situations in which objects are related in pairs: Vertices are people, edges indicate relationships (friendship? common work?) Vertices are events at a conference; edges join events that cannot be held simultaneously. Vertices are data structure nodes; (directed) edges indicate (owning?) pointers.7 Dec 2009 CS 311 Fall 2009 12Introduction to GraphsRepresentationsTwo common ways to represent graphs: Adjacency matrix. 2-D array of Boolean values. Entry (i, j) answers the question “Does edge