Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:devlinn:chapter3 [2018/02/04 19:05] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter3 [2018/02/04 19:05] (current) – [3.3 Implementing Graph Traversal Using Queues and Stacks] devlinn
@@ Line 36: / Line 36: @@
 ===== 3.3 Implementing Graph Traversal Using Queues and Stacks =====
-The two basic ways to represent graphs are **adjacency matrices** and *adjacency lists**. When assessing the running time of algorithms which use either of these representations, the run time will be expressed as a function of two parameters, //n// for nodes and //m// for edges. The goal is to implement graph search algorithms in O(//m// + //n//) running time, referred to as linear time. An adjacency matrix is the simplest data structure to use for graph implementation, but it has its disadvantages. For one, it requires Θ(//n//) time. In addition, checking for all edges takes Θ(//n//) time when using an adjacency matrix, which is not ideal. Because of this, we prefer to use adjacency lists for graph implementation. The space required for an adjacency list is O(//m// + //n//) and checking all edges requires only O(deg(//u//)) running time.
+The two basic ways to represent graphs are **adjacency matrices** and **adjacency lists**. When assessing the running time of algorithms which use either of these representations, the run time will be expressed as a function of two parameters, //n// for nodes and //m// for edges. The goal is to implement graph search algorithms in O(//m// + //n//) running time, referred to as linear time. An adjacency matrix is the simplest data structure to use for graph implementation, but it has its disadvantages. For one, it requires Θ(//n//) time. In addition, checking for all edges takes Θ(//n//) time when using an adjacency matrix, which is not ideal. Because of this, we prefer to use adjacency lists for graph implementation. The space required for an adjacency list is O(//m// + //n//) and checking all edges requires only O(deg(//u//)) running time.
 When processing a set of elements, which often occurs in graph search algorithms, it is critical to determine how to ideally represent these elements. //Stacks// and //queues// are frequently used in this role, because it is frequently necessary to maintain a particular order for traversing the elements. Queue elements are extracted in //first-in, first-out// (FIFO) order, and stack elements are extracted in //last-in, first-out// (LIFO) order. The BFS algorithm uses a queue-like structure, as can be seen in the following sketch of the algorithm: