Skip to main content
Engineering LibreTexts

4.4: Unit Summary

  1. Last updated
  2. Save as PDF
  • Page ID
    49348

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    This unit presented two advanced data structures, hash table and graph, along with some popular graph algorithms. Hash tables use hash functions to generate indexes for keys to be stored or accessed from array/list. A good hash function design is instrumental to the hash table performance expected to have a constant access time. The graph data structure is defined by a set of vertices and edges. It is very useful in problems modeled as networks.

    A topological sort runs a depth-first search algorithm on acyclic digraph to order the vertices so that the keys are enumerated in descending order. The shortest path problem seeks to find a shortest path between a pair of vertices. The Dijkstra algorithm finds the shortest path for a single source graph with non-negative edge weights, and the Bellman Ford algorithm is like the Dijkstra algorithm but also works for graphs with negative edge weights. For the case of multiple sourced graphs, the two algorithms can be adapted with some loss of efficiency, though. For this reason, the Floyd-Warshall algorithm is used to finds shortest paths in multiple sourced graphs and arbitrary edge weights.

    Unit Assessment

    Check your understanding!

    Graphs, DFS and BFS

    1. Consider a graph in Figure 4.4.1 .
      Fig18_Graph.png
      Figure 4.4.1 : A graph

    Figure 18

    1. Write the adjacency matrix and adjacency list for this graph
    2. Starting from vertex a (and resolving ties by the vertex alphabetical order), list the vertices using a DFS traversal.
    3. Starting from vertex a (and resolving ties by the vertex alphabetical order), list the vertices using a BFS traversal.
  • One can model a maze by having a vertex for a starting point, finishing point, dead ends, and all the points in the maze where more than one path can be taken and then connecting the vertices according to the paths. Consider a maze shown in Figure 4.4.2 .
    1. Construct a graph for the maze
    2. Which traversal between DFS and BFS would you use if you found yourself in a maze and why?
    Fig19_Maze.png
    Figure 4.4.2 : A maze

    • Answers

    mailto:njulumi@gmail.com

    Grading Scheme

    As per the offering Institution grading policy.

    Unit Readings and Other Resources

    The readings in this unit are to be found at course level readings and other resources.

    This page titled 4.4: Unit Summary is shared under a not declared license and was authored, remixed, and/or curated by Godfry Justo (African Virtual University) .

    1. Back to top
    • Was this article helpful?

    Recommended articles

    1. Article type
      Section or Page
      Author
      Godfry Justo
      License Version
      3.0
    2. Tags
      This page has no tags.