Algorithms & Data Structures — Assignment 4 (AITU)

Overview

Generic graph implementations (unweighted and weighted, directed or undirected) with three classic traversal/shortest-path algorithms. The demo in Main models a small map of Kazakhstani cities and finds routes using all three algorithms.

What it implements

• Vertex<V> — graph node storing typed data and an adjacency map (Vertex → weight). Uses a static counter for a stable hashCode.
• Edge<V> — weighted directed edge with source, destination, and double weight.
• MyGraph<V> — adjacency-list graph (directed or undirected) for unweighted edges. Backed by a HashMap<V, Vertex<V>>.
• WeightedGraph<V> — same structure extended for weighted edges; addEdge accepts a double weight.
• Search<V> — abstract base holding marked (visited set) and edgeTo (path map); provides hasPathTo and pathTo (reconstructs path by walking edgeTo).
• BreadthFirstSearch<V> — BFS using a Queue; visits vertices level-by-level; time O(V+E).
• DepthFirstSearch<V> — recursive DFS; explores as deep as possible before backtracking; time O(V+E).
• Dijkstra<V> — greedy shortest-path on a WeightedGraph; uses an unsettled-node set for relaxation; time O(V²) with linear scan (noted in Javadoc as improvable to O(E + V log V) with a priority queue).

Project structure

src/
├── Main.java                      # Demo: Almaty → Kyzylorda via Dijkstra, DFS, BFS
└── graphs/
    ├── Vertex.java                # Graph node with weighted adjacency map
    ├── Edge.java                  # Weighted directed edge
    ├── MyGraph.java               # Unweighted adjacency-list graph
    ├── WeightedGraph.java         # Weighted adjacency-list graph
    ├── Search.java                # Abstract base: marked, edgeTo, pathTo
    ├── BreadthFirstSearch.java    # BFS traversal
    ├── DepthFirstSearch.java      # DFS traversal
    └── Dijkstra.java              # Dijkstra's shortest-path algorithm

How to run

javac -d out src/graphs/*.java src/Main.java
java -cp out Main

Sample output:

Dijkstra:
Almaty -> Astana -> Kyzylorda ->
DFS:
Almaty -> Shymkent -> Kyzylorda ->
BFS:
Almaty -> Shymkent -> Kyzylorda ->

---

Adil Ormanov — GitHub