daily pastebin goal
38%
SHARE
TWEET

Untitled

a guest Mar 26th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #include <iostream>
  3. #include <string>
  4. #include <fstream>
  5.  
  6. using namespace std;
  7.  
  8. int vertex; //đỉnh
  9. int edge; //cạnh
  10.  
  11. int minKey(int *key, bool *arr_not_review) {
  12.     int min = INT_MAX;
  13.     int min_index;
  14.     for (int i = 0; i < vertex; i++) {
  15.         if (arr_not_review[i] == false && key[i] < min) {
  16.             min = key[i];
  17.             min_index = i;
  18.         }
  19.     }
  20.     return min_index;
  21. }
  22.  
  23. void WriteFile(char *outputName, int *parent1, int *parent2, int *key) {
  24.     fstream fileoutput;
  25.     fileoutput.open(outputName, ios_base::out);
  26.  
  27.     int sum = 0;
  28.     for (int i = 0; i < vertex; i++) {
  29.         sum = sum + key[i];
  30.     }
  31.     fileoutput << sum << endl;
  32.  
  33.     for (int i = 1; i < vertex; i++) {
  34.         if (i == vertex - 1) {
  35.             fileoutput << "(" << parent1[i] << ";" << parent2[i] << ")";
  36.         }
  37.         else {
  38.             fileoutput << "(" << parent1[i] << ";" << parent2[i] << "), ";
  39.         }
  40.     }
  41. }
  42.  
  43. void Prim(int **arrGraph, bool *arr_not_review, char *outputName) {
  44.     int *parent1 = new int[vertex]; // array vertex head
  45.     int *parent2 = new int[vertex]; // array vertex tail
  46.     int *key = new int[vertex];
  47.     for (int i = 0; i < vertex; i++) {
  48.         key[i] = INT_MAX;
  49.     }
  50.     key[0] = 0;
  51.     parent1[0] = -1;
  52.     parent2[0] = -1;
  53.     // prim
  54.     for (int count = 0; count < vertex - 1; count++) {
  55.         // find vertex have key min
  56.         int u = minKey(key, arr_not_review);
  57.         arr_not_review[u] = true;
  58.         for (int i = 1; i < vertex; i++) {
  59.             if (arrGraph[u][i] && arr_not_review[i] == false && arrGraph[u][i] < key[i]) {
  60.                 parent1[i] = u;
  61.                 parent2[i] = i;
  62.                 key[i] = arrGraph[u][i];
  63.             }
  64.         }
  65.     }
  66.  
  67.     // sort result (edge)
  68.     for (int i = 1; i <= vertex -1; i++) {
  69.         for (int j = 1; j <= vertex - i - 1; j++) {
  70.             if (parent1[j] > parent1[j + 1]) {
  71.                 int temp1 = parent1[j];
  72.                 parent1[j] = parent1[j + 1];
  73.                 parent1[j + 1] = temp1;
  74.  
  75.                 int temp2 = parent2[j];
  76.                 parent2[j] = parent2[j + 1];
  77.                 parent2[j + 1] = temp2;
  78.             }
  79.             if (parent1[j] == parent1[j + 1]) {
  80.                 if (parent2[j] > parent2[j + 1]) {
  81.                     int temp1 = parent1[j];
  82.                     parent1[j] = parent1[j + 1];
  83.                     parent1[j + 1] = temp1;
  84.  
  85.                     int temp2 = parent2[j];
  86.                     parent2[j] = parent2[j + 1];
  87.                     parent2[j + 1] = temp2;
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.     //write file
  94.     WriteFile(outputName, parent1, parent2, key);
  95. }
  96.  
  97. void Run(char *inputName, char *outputName) {
  98.     //read file
  99.     fstream fileInput;
  100.     fileInput.open(inputName, ios_base::in);
  101.     if (fileInput.fail()) //check exists
  102.     {
  103.         cout << "Failed to open this file!" << endl;
  104.     }
  105.     else if(fileInput.peek() == std::ifstream::traits_type::eof()) // check empty
  106.     {
  107.         cout << "Empty file!" << endl;
  108.     }
  109.     else {
  110.         // read vertex - edge
  111.         fileInput >> vertex; fileInput >> edge;
  112.    
  113.         if (edge == 0 || vertex == NULL || edge == NULL) {
  114.             fstream fileoutput;
  115.             fileoutput.open(outputName, ios_base::out);
  116.             fileoutput << "NULL";
  117.         }
  118.         else {
  119.             // declare matrix graph
  120.             // declare row
  121.             int **arrGraph = new int*[vertex];
  122.             // declare col
  123.             for (int i = 0; i < vertex; i++) {
  124.                 arrGraph[i] = new int[vertex];
  125.             }
  126.  
  127.             // array vertex not review
  128.             bool *arr_not_review = new bool[vertex];
  129.             for (int i = 0; i < vertex; i++) {
  130.                 // set label for vertexs
  131.                 arr_not_review[i] = false;
  132.                 // set items of matrix = 0
  133.                 for (int j = 0; j < vertex; j++) {
  134.                     arrGraph[i][j] = 0;
  135.                 }
  136.             }
  137.  
  138.             //read and import edge (create matrix)
  139.             int head, tail, width;
  140.             int checkformat = 0;
  141.             for (int i = 0; i < edge; i++) {
  142.                 fileInput >> head >> tail >> width;
  143.                 // check format (width = 0 => fail)
  144.                 if (width == 0 || width == NULL) {
  145.                     checkformat++;
  146.                 }
  147.                 arrGraph[head][tail] = width;
  148.                 arrGraph[tail][head] = width;
  149.             }
  150.  
  151.             if (checkformat == 0) {
  152.                 // Prim
  153.                 Prim(arrGraph, arr_not_review, outputName);
  154.                 cout << "Successfull." << endl;
  155.             }
  156.             else {
  157.                 cout << "Width incorrect format!" << endl;
  158.             }
  159.         }  
  160.     }
  161.     fileInput.close();
  162. }
  163.  
  164.  
  165.  
  166. int main(int argc, char *argv[])
  167. {
  168.     Run(argv[1], argv[2]);
  169.     return 0;
  170. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top