📜 About Project

SAED stands for Synopsys Armenia Educational Department, the university where I received my bachelor's degree.
This project is course work that I have done during SAED's discrete mathematics course.
The program finds a spanning tree in the user's inputted graph.
For program-correct work, you must have Graphviz on your computer.

📶 Program Work Steps:

1. Get graph edges by reading the input file  input.txt
2. Build an adjacency matrix for the given graph.
3. By using the adjacency matrix, make a simple graph from the given graph.
4. Check if the simple graph is connected or not, because a given graph must be connected.
5. If the graph is connected, find the spanning tree using the DFS algorithm.
6. Visualize the inputted graph and the spanning tree with Graphviz.
   Input example      Output example

👨‍💻 Getting Started

1. Start by updating the packages list:  sudo apt update
2. Install the G++ compiler if you don't have:  sudo apt install build-essential
3. Check installation with the command:  g++ --version
4. Make must be installed with the build-essential package; check it:  make --version
5. Install the make package if you don't have:  sudo apt install make
6. Install Graphviz if you don't have:  sudo apt install graphviz
7. Check installation with the command:  dot -V
8. Clone this repo:  git clone https://github.com/dpetrosy/SAED_graph_project.git
9. Go to directory:  cd graph_course_project
10. Run the make and build program:  make
11. Run executable:  ./graph.exe

Congrats! Now you can see your inputted graph and found the spanning tree :)
You can change the input.txt file and see how the program works 😎