min-spanning-tree

KO | EN

gitlite — search

#hacktoberfest #react #ai #typescript #go #deep-learning #docker #macos #windows #awesome #vue #security #pytorch #open-source

min-spanning-tree

(★ 2)

Implementation of Kruskal's and Prim's minimum spanning tree algorithms.

min-spanning-tree 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

Minimum Spanning Tree
=====================

Minimum spanning tree (MST) of a weighted, connected and undirected graph is
the subgraph that is still connected and has the minimum possible total edge
weight. Minimum spanning trees have many useful applications. It is most
helpful in designing networks with minimum cost; network can be anything from
telecommunication cable networks, electrical grid networks, water supply
networks, computer networks, transportation networks, etc. For theoretical
discussion and analysis, see `report.pdf`.

This project implements two most popular MST algorithms: Kruskal's and Prim's
algorithms.

Project Structure
-----------------

```sh
graphs                      # sample input graphs
src/                        # main source tree
    alg/                    # algorithms
        kruskal.py          # Kruskal's algorithm implementation
        prim.py             # Prim's algorithm implementation
    ds/                     # data structures
        disjointset.py      # disjoint set implementation
        graph.py            # graph implementation
        heap.py             # heap implementation
    viz.py                  # visualization helper functions
run.py                      # run the algorithm on an input graph file
README.md                   # this file
report.pdf                  # project report
requirements.txt            # third-party python packages used
```

Command-line Usage
------------------

Make sure you have `python3` with `matplotlib` and `networkx`.

To run the MST algorithm on a graph:

$ ./run.py graphs/small.graph

It will print the list of MST edges.

> Note: Graph files are simple text files containing list of edges (one per
> line). Each line contains 3 elements: source node, destination node,
> weight. See sample graphs in `graphs/` folder for examples.

For other functionalities (such as visualizing the graph), see:
`./run.py -h`.

Author
------

Manish Munikar<br>
UTA ID: 1001826846<br>
manish.munikar@mavs.uta.edu

min-spanning-tree

min-spanning-tree 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

min-spanning-tree

min-spanning-tree 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README