Master Hash Tables, Heaps, and Graph Algorithms: From Basics to Dijkstra

Data structures and algorithms are fundamental to computer science, providing the abstract basis for storing and processing data. Mastering them is essential for selecting appropriate structures and algorithms to solve business and data problems.

Hash Table (Hash Map)

A hash table, also called a hash map, stores key‑value pairs by applying a hash function f(key) to compute an array index. This enables fast direct access, but insertion and deletion can be slower, often mitigated by using chaining (array of linked lists) or, in modern Java, a combination of arrays and red‑black trees.

Hash tables are widely used in collections such as HashMap and Hashtable. They excel at look‑ups but require careful handling of collisions.

Heap

A heap is a specialized tree‑based structure represented as an array, satisfying the heap property: each node’s value is not greater (min‑heap) or not smaller (max‑heap) than its parent’s value. Heaps are complete binary trees and are used for priority queues and heap sort.

Graph

A graph consists of a finite set of vertices V and edges E. Graphs can be directed or undirected. They model complex relationships and support many algorithms for traversal, shortest paths, spanning trees, and topological ordering.

Shortest‑Path Problems

Shortest‑path algorithms find the minimum‑weight path between vertices. They are classified as:

Single‑source shortest path (e.g., from a source to all other vertices)

All‑pairs shortest path

For unweighted graphs, Breadth‑First Search (BFS) solves the single‑source problem.

For weighted graphs without negative edges, Dijkstra’s algorithm is used.

The Floyd‑Warshall algorithm (published in 1962) solves all‑pairs shortest paths by iteratively allowing intermediate vertices.

Minimum Spanning Tree (MST)

An MST connects all vertices with the minimum total edge weight, using a greedy approach.

Prim’s algorithm grows a tree by repeatedly adding the cheapest edge from the current tree to a new vertex.

Kruskal’s algorithm merges disjoint trees (a forest) by adding the smallest edge that connects two different components.

Topological Sorting

Topological order arranges vertices such that for every directed edge V→W, V appears before W. It is applicable to Directed Acyclic Graphs (DAGs) and is used in scheduling and build systems.

Dijkstra Algorithm Implementation (Java)

package 图论;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class dijkstra {
    static class node {
        int x; // vertex index
        int lenth; // distance from source
        public node(int x, int lenth) {
            this.x = x;
            this.lenth = lenth;
        }
    }

    public static void main(String[] args) {
        int[][] map = new int[6][6];
        initmap(map);
        boolean[] bool = new boolean[6];
        int[] len = new int[6];
        for (int i = 0; i < 6; i++) {
            len[i] = Integer.MAX_VALUE;
        }
        Queue<node> q1 = new PriorityQueue<>(com);
        len[0] = 0; // start from vertex 0
        q1.add(new node(0, 0));
        int count = 0;
        while (!q1.isEmpty()) {
            node t1 = q1.poll();
            int index = t1.x;
            int length = t1.lenth;
            bool[index] = true;
            count++;
            for (int i = 0; i < map[index].length; i++) {
                if (map[index][i] > 0 && !bool[i]) {
                    node nd = new node(i, length + map[index][i]);
                    if (len[i] > nd.lenth) {
                        len[i] = nd.lenth;
                        q1.add(nd);
                    }
                }
            }
        }
        for (int i = 0; i < 6; i++) {
            System.out.println(len[i]);
        }
    }

    static Comparator<node> com = new Comparator<node>() {
        public int compare(node o1, node o2) {
            return o1.lenth - o2.lenth;
        }
    };

    private static void initmap(int[][] map) {
        map[0][1] = 2; map[0][2] = 3; map[0][3] = 6;
        map[1][0] = 2; map[1][4] = 4; map[1][5] = 6;
        map[2][0] = 3; map[2][3] = 2;
        map[3][0] = 6; map[3][2] = 2; map[3][4] = 1; map[3][5] = 3;
        map[4][1] = 4; map[4][3] = 1;
        map[5][1] = 6; map[5][3] = 3;
    }
}

Critical Path and AOV/AOE Graphs

Critical‑path analysis on activity‑on‑vertex (AOV) or activity‑on‑edge (AOE) graphs helps optimize project schedules by identifying the longest sequence of dependent tasks.

Conclusion

Hash tables and heaps provide efficient data retrieval and priority management, while graph algorithms such as shortest‑path, MST, and topological sorting enable solving real‑world optimization problems like routing, project planning, and resource allocation.