KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#developer-tools #typescript #dsh #dsh-plugin #ai-agent #codex #ai-agents #deepseek-harness #claude-code #cli #react #mcp

Finding-a-Short-Spanning-Walk-in-a-Connected-Graph-NP-Hard-Problem-

★ 13 Open GitHub ↗

finding a short spanning walk throw a connected graph (NP-HARD problem)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Finding a Short Spanning Walk in a Connected Graph (NP-Hard Problem)

This repository contains an implementation of algorithms designed to find a short spanning walk in a connected graph, a classic NP-hard problem. The project explores various algorithmic approaches and evaluates their performance on large datasets.

## Problem Overview

The task is to find a spanning walk that visits all vertices in a connected graph while minimizing the total path length. Given the NP-hard nature of this problem, we implemented several algorithms and tested them to determine their effectiveness.

## Approach

After extensive testing of various algorithms on a dataset consisting of a graph with **15,000 vertices** and **52,000 edges**, the following methods were applied:

### Algorithms Used

1. **Simple Depth-First Search (DFS)**  
   - **Result:** Path length greater than **28,000**  
   - **Description:** This algorithm explores as far as possible along each branch before backtracking, but does not guarantee an efficient path.

2. **Optimized Depth-First Search**  
   - **Result:** Path length greater than **24,000**  
   - **Description:** This variation of DFS incorporates heuristic optimizations to improve efficiency over the basic DFS.

3. **Simple Breadth-First Search (BFS)**  
   - **Result:** Path length greater than **28,000**  
   - **Description:** BFS explores all neighbors at the present depth prior to moving on to nodes at the next depth level, but also lacks efficiency in spanning all vertices.

4. **Combined DFS and BFS**  
   - **Result:** Path length greater than **28,000**  
   - **Description:** In this method, we use DFS to traverse deep into the graph initially. Given that the edges are unweighted, we utilize BFS to find the shortest path back instead of Dijkstra's algorithm, which is typically used for weighted graphs. However, this approach also results in an inefficient walk overall.

5. **Greedy Algorithm (Basic Version)**  
   - **Result:** Path length greater than **20,000**  
   - **Description:** This approach involves starting from a vertex and repeatedly moving to the nearest unseen vertex using BFS. This method improves efficiency but still does not yield the optimal solution.

6. **Degree-Based Greedy Algorithm**  
   - **Result:** Path length of approximately **18,000**  
   - **Description:** This method refines the greedy approach by prioritizing vertices based on their degree. It selects the nearest vertex with the smallest degree among the nearest unseen vertices, significantly improving the outcome.

## Results

The best performing method was the **Degree-Based Greedy Algorithm**, which produced a path length of approximately **18,000**. Given the presence of about **2,000 leaves** in the graph and **14,000 vertices**, the theoretical lower bound for the shortest spanning walk is no less than **16,000**. The result from this algorithm is very close to this theoretical lower bound, demonstrating its effectiveness.

## Conclusion

This project provides insights into various algorithmic strategies for solving the NP-hard problem of finding a short spanning walk in a connected graph. The Degree-Based Greedy Algorithm shows significant promise in terms of efficiency and effectiveness.

Finding-a-Short-Spanning-Walk-in-a-Connected-Graph-NP-Hard-Problem-

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README