Skip to main content
Engineering LibreTexts

4: Hash Tables, Graphs and Graph Algorithms

  • Page ID
    46778
  • \( \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}}\)

    Unit Objectives

    Upon completion of this unit you should be able to:

    • Demonstrate understanding of hash tables and graph data structures
    • Apply the data structures in problem solving
    • Demonstrate understanding of graph algorithms

    Unit Introduction

    In this unit we will present more advanced data structures, hash tables and graphs and explore some graph algorithms. The hash table data structure uses hash functions to generate indexes where keys are stored or being accessed in an array. They find a wide use including implementation of associative arrays, database indexes, caches and object representation in programming languages.

    A graph data structure is represented as a collection of finite sets of vertices or nodes (V) and edges (E). Edges are ordered pairs such as (u, v) where (u, v) indicates that there is an edge from vertex u to vertex v. Edges may contain cost, weight or length. Graphs are widely used in modeling networks including computer networks, social networks or some abstract phenomena of interrelated conceptual objects. Graphs algorithm can be used to solve most problems occurring in situations modeled as networks.


    This page titled 4: Hash Tables, Graphs and Graph Algorithms is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by Godfry Justo (African Virtual University) .

    • Was this article helpful?