Graphics Traversal Chapter 1

University:
Boston University
Course:
CAS MA 555 | Numerical Analysis I
Academic year:

2022
Views:

372

Pages:

15
Author:

Cordell Nielsen

Graph Traversal Can you name all the nodes? B E P D T G X K A R H M Breadth-First Search Depth-First Search Breadth-First Search L0 L1 A B L2 C E D F Breadth-First Search Breadth-first search (BFS) is a general technique for traversing a graph. A BFS traversal of a graph returns the nodes of the graph level by level. L0 L1 L2 L3 What is a BFS traversal? L0 Let’s start at A A L1 B L2 C E D F What is a BFS traversal? L0 1 L1 2 L2 3 5 4 6 What is a BFS traversal? L0 Let’s start at A A L1 B L2 ABCDEF C E D F Is that the only BFS? What is a BFS traversal? L0 1 L1 4 L2 3 6 2 5 Computer Algorithm A computer does not see the BIG PICTURE of a graph. It has a list of nodes in a graph and a list of edges, and it knows which nodes are connected by which edge. How would a computer perform BFS? A Adjacency Matrix B C E D F A B C D E F A 0 1 1 1 0 0 B 1 0 0 0 0 0 C 1 0 0 0 1 1 D 1 0 0 0 0 1 E 0 0 1 0 0 0 F 0 0 1 1 0 0 Queue A queue is a line. If you’re the first to get in a bus line, you’re the first to get on the bus. First In, First Out Example L0 Let’s start at A A B C E Enqueue the root A. Queue: A D F Enqueue means to put something at the end of the line. Here’s Our Algorithm Each time, we’re going to take out one node (we’ll call it node X) from the queue. We call the process dequeue. Then, we’re going to add to the queue all of the new neighbors of node X. We call that process enqueue.