Минимальное связующее дерево

Постановка задачи

Найдите минимальное остовное дерево связного неориентированного графа со взвешенными ребрами.

Рассмотрим следующий граф.

Минимальное остовное дерево приведенного выше графика будет:

Подсказка

  • Минимальный вес края

Попробуйте сами

  • C ++
  • C++
  • C ++
  • Java
  • Java
  • Python
  • h> Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 #include  #include  с использованием пространства имен std; вершина класса {private: int id;  посещено bool; общедоступно: вершина (int id, посещено bool) {this-> id = id;  это-> посетил = посетил;  } int getId () {идентификатор возврата;  } void setId (int id) {this-> id = id;  } bool isVisited () {возвращение посещено;  } void setVisited (булево посещено) {это-> посетил = посетил;  }}; край класса {private: int weight;  bool посетили;  вершина * src;  вершина * dest; общедоступный: край (int weight, bool посещено, вершина * src, вершина * dest) {this-> weight = weight;  это-> посетил = посетил;  this-> src = src;  this-> dest = dest;  } int getWeight () const {вернуть вес;  } void setWeight (int weight) {this-> weight = вес;  } bool isVisited () const {возвращение посещено;  } void setVisited (булево посещено) {это-> посетило = посетило;  } вершина * getSrc () const {return src;  } void setSrc (вершина * src) {this-> src = src;  } вершина * getDest () const {return dest;  } void setDest (вершина * dest) {this-> dest = dest;  }}; граф классов {private: vector  g; //вектор вершин  e; //Edgepublic: int find_min_spanning_tree () {//TODO: Write - Your - Code} const vector  & getG () const {return g;  } void setG (константный вектор  & g) {this-> g = g;  } const vector  & getE () const {return e;  } void setE (вектор констант  & е) {это-> е = е;  }//Этот метод возвращает вершину с заданным идентификатором,//если она уже существует в графе, возвращает NULL, иначе вершина * vertex_exists (int id) {for (int i = 0; i  g. размер();  я ++) {if (g [i] -> getId () == id) {return g [i];  }} return nullptr;  } строка print_graph () {строка результат = "";  for (int i = 0; i  getId ()  isVisited ()  getSrc () -> getId ()) + "->"  + std :: to_string (e [i] -> getDest () -> getId ()) + "],";  cout  getSrc () -> getId () "  getDest () -> getId ()  getWeight ()  isVisited () > edge) {//создаёт вершины для (int i = 0; i  g.push_back (v);  }//создаем ребра для (int i = 0; i  е. push_back (е);  }}}; 

Решение

  • C ++
  • C ++
  • C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 #include  #include  используя  пространство имен std; вершина класса {частный: int id;  bool посетили;  общедоступные: вершина (int id, bool посещено) {this-> id = id;  это-> посетил = посетил;  } int getId () {идентификатор возврата;  } void setId (int id) {this-> id = id;  } bool isVisited () {возвращение посещено;  } void setVisited (булево посещено) {это-> посетило = посетило;  }}; край класса {private: int weight;  bool посетили;  вершина * src;  вершина * dest;  public: edge (int weight, bool посещено, вершина * src, вершина * dest) {this-> weight = weight;  это-> посетил = посетил;  this-> src = src;  this-> dest = dest;  } int getWeight () const {вернуть вес;  } void setWeight (int weight) {this-> weight = вес;  } bool isVisited () const {возвращение посещено;  } void setVisited (булево посещено) {это-> посетило = посетило;  } вершина * getSrc () const {return src;  } void setSrc (вершина * src) {this-> src = src;  } вершина * getDest () const {return dest;  } void setDest (вершина * dest) {this-> dest = dest;  }}; граф классов {private: vector  g; //вектор вершин  e; //общедоступные ребра: const vector  & getG () const {return g;  } void setG (константный вектор  & g) {this-> g = g;  } const vector  & getE () const {return e;  } void setE (вектор констант  & е) {это-> е = е;  }//Этот метод возвращает вершину с заданным идентификатором,//если она уже существует в графе, возвращает NULL, иначе вершина * vertex_exists (int id) {for (int i = 0; i  g. размер();  я ++) {if (g [i] -> getId () == id) {return g [i];  }} return nullptr;  }//Этот метод генерирует граф с v вершинами//и e ребрами void generate_graph (int vertices, vector > edge) {//создаёт вершины для (int i = 0; i  g.push_back (v);  }//создаем ребра для (int i = 0; i  e.push_back (e);  }}//Этот метод находит MST графа с помощью//Алгоритма Прима//возвращает вес MST int find_min_spanning_tree () {int vertex_count = 0;  int weight = 0; //Добавляем первую вершину к вершине MST * current = g [0];  текущий-> setVisited (правда);  vertex_count ++; //Создаем оставшийся MST, используя//край с наименьшим весом while (vertex_count  isVisited () == false) {if (e [i] -> getSrc () -> isVisited ()  == true && e [i] -> getDest () -> isVisited () == false) {если (наименьшее == NULL) {наименьшее = e [i];  } иначе, если (е [я] -> getWeight ()  getWeight ()) {наименьшее = е [я];  }}}} наименьший-> setVisited (true);  наименьший-> getDest () -> setVisited (true);  вес + = наименьший-> getWeight ();  vertex_count ++;  } возвратный вес;  } void print_graph () {for (int i = 0; i  getId ()  isVisited (  )  getSrc () -> getId () "  getDest  () -> getId ()  getWeight ()  isVisited ()  isVisited () == true) {cout  getSrc () -> getId (  ) "  getDest () -> getId () > e = {{1, 1, 2}, {1, 1, 3}, {2, 2, 3}, {3,  2, 4}, {3, 3, 5}, {2, 4, 5}};  g.generate_graph (v, e);  g.print_graph ();  cout > e = {{2, 1, 4}, {1, 1, 3}, {2, 1, 2}, {1,  3, 4}, {3, 2, 4}, {2, 3, 5}, {2, 4, 7}, {1, 5, 6}, {2, 5, 7}};  g.generate_graph (v, e);  cout  

Объяснение решения

Сложность времени выполнения

Квадратичный, O ( n 2 ) O(n^{2}) O (n 2)

Здесь n — количество вершин.

Сложность памяти

Линейная, O (n + e) ​​

Здесь, ‘n’ — количество вершин, а ‘e’ — количество ребер.

Разбор решения

Остовное дерево связного, неориентированный граф — это подграф, который является деревом и соединяет все вершины вместе. У одного графа может быть много разных остовных деревьев. Граф с n вершинами имеет остовное дерево с n-1 ребром.

Каждому ребру графа можно присвоить вес. Вес остовного дерева — это сумма весов всех ребер остовного дерева. Минимальное остовное дерево (MST) для взвешенного связного и неориентированного графа — это остовное дерево с весом, меньшим или равным весу любого другого остовного дерева.

Мы найдем минимум остовное дерево графа с использованием алгоритма Прима. Этот алгоритм строит дерево по одной вершине за раз, начиная с любой произвольной вершины. Он добавляет ребро минимального веса из создаваемого дерева к вершине из оставшихся вершин на каждом шаге.

Алгоритм следующий:

  Инициализируйте MST произвольной вершиной из графа. Найдите ребро с минимальным весом от построенного графа к вершинам, еще не добавленным в граф. Добавьте это ребро и вершину в MST. Повторяйте шаги 2-3, пока все вершины не будут добавлены в MST. /code> 

Временная сложность нахождения ребра с минимальным весом составляет O ( n 2 ) O (n ^ {2}) O (n 2). Однако его можно улучшить, используя кучи для определения края минимального веса.

Оцените статью
nanomode.ru
Добавить комментарий