Gain insights into array and linked list-based implementations, delve into advanced structures like skiplists and trees, and explore template-based collections for efficient data optimization and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in C++

In this lesson we present two algorithms for exploring a graph, starting at one of its vertices, `i`, and finding all vertices that are reachable from `i`. Both of these algorithms are best suited to graphs represented using an adjacency list representation. Therefore, when analyzing these algorithms we will assume that the underlying representation is an `AdjacencyLists`.

# Breadth-first-search


The **breadth-first-search algorithm** starts at a vertex `i` and visits, first, the neighbors of `i`, then the neighbors of the neighbors of `i`, then the
neighbors of the neighbors of the neighbors of `i`, and so on. This algorithm is a generalization of the breadth-first traversal algorithm for binary trees, and is very similar; it uses a queue, `q`, that initially contains only `i`. It then repeatedly extracts an element from `q` and adds its neighbors to `q`, provided that these neighbors have never been in `q` before. The only major difference between the breadth-first-search algorithm for graphs and the one for trees is that the algorithm for graphs has to ensure that it does not add the same vertex to `q` more than once. It does this by using an auxiliary boolean array, `seen`, that tracks which vertices have already been discovered.




void bfs(Graph g, int r) {
  boolean[] seen = new boolean[g.nVertices()];
  Queue < Integer > q = new SLList < Integer > ();
  q.add(r);
  seen[r] = true;
  while (!q.isEmpty()) {
    int i = q.remove();
    for (Integer j: g.outEdges(i)) {
      if (!seen[j]) {
        q.add(j);
        seen[j] = true;
      }
    }
  }
}

## Visual demonstration of breadth-first search
An example of running `bfs(g, 0)` on the graph is shown in the illustration below.

An example of bread-first-search starting at node $0$. Nodes are labeled with the order in which they are added to `q`. Edges that result in nodes being added to `q` are drawn in black, and other edges are drawn in grey.

Analyzing the running-time of the `bfs(g, i)` routine is fairly straightforward. The use of the seen array ensures that no vertex is added to `q` more than once. Adding (and later removing) each vertex from `q` takes
constant time per vertex for a total of $O(n)$ time. Since each vertex is processed by the inner loop at most once, each adjacency list is processed at
most once, so each edge of $G$ is processed at most once. This processing,
which is done in the inner loop takes constant time per iteration, for a
total of $O(m)$ time. Therefore, the entire algorithm runs in $O(n + m)$ time.


The following theorem summarizes the performance of the `bfs(g, r)` algorithm.

**Theorem 1:** When given as input a `Graph`, $g$, that is implemented using
the `AdjacencyLists` data structure, the `bfs(g, r)` algorithm runs in $O(n + m)$ time.


A breadth-first traversal has some very special properties. Calling
`bfs(g, r)` will eventually enqueue (and eventually dequeue) every vertex `j` such that there is a directed path from `r` to `j`. Moreover, the vertices at distance `0` from `r` (`r` itself) will enter `q` before the vertices at distance `1`, which will enter `q` before the vertices at distance `2`, and so on. Therefore, the `bfs(g, r)` method visits vertices in increasing order of distance from `r`, and vertices that cannot be reached from `r` are never visited at all.



A particularly useful application of the breadth-first-search algorithm
is, therefore, in computing shortest paths. To compute the shortest path
from `r` to every other vertex, we use a variant of `bfs(g, r)` that uses an
auxiliary array, `p`, of length `n`. When a new vertex `j` is added to `q`, we set `p[j] = i`. In this way, `p[j]` becomes the second last node on the shortest path from `r` to `j`. Repeating this, by taking `p[p[j]`, `p[p[p[j]]]`, and so on we can reconstruct the (reversal of) the shortest path from `r` to `j`.

Learn about BFS and DFS  searching algorithms.

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Graph Traversal