Хорошо, я должен сделать алгоритм топологической сортировки на графе. Мне нужно найти узел со степенью 0 и поставить его в очередь, затем распечатать и удалить все ребра, идущие к нему. Я удаляю ребра, уменьшая количество ребер, входящих в него в карте countList. У меня есть список смежности в виде карты, а количество в градусах для каждого узла в виде карты. Мой алгоритм обращается только к первому элементу списка смежности. поэтому моя очередь вывода отображает только первый ключ карты списка смежности. вновь и вновь. Я остановил цикл while на 25, чтобы он не был бесконечным.
string z = "";
string a = "";
cout << "Queue: ";
do{
for(it = countList.begin(); it!=countList.end(); ++it){
if(it->second == 0){
Q.push(it->first);
countList.at(it->first)--;
z = adjList[it->first];
cout <<"z: " << z <<endl;
//remove edges
for(int i = 0; i< z.length(); i++){
a = z.at(i);
cout << "z at " <<i << " : " <<a <<endl;
countList.at(a)--;
}//end for
}//end if
//cout << Q.front() << ", ";
//Q.pop();
}//end for
cout << Q.front() << ", ";
Q.pop();
}while(!Q.empty());
Может ли кто-нибудь помочь мне понять, почему он не проходит через countList и остается только на первом элементе?
Спасибо.
Поэтому я изменил countList.at (a) — + 1, на countList.at (a) — для правильного уменьшения.
Теперь результат больше, чем просто первая вершина, которая была 0 в градусе. Но вывод все еще не верен.
Вот и все.
Мои объявления переменных
vector<string> E;
map<string, string> adjList;
map<string, int>countList;
map<string, int>::iterator it;
queue<string> Q;
Я не хочу выставлять код для adjacencyList или countList, но вот как они выглядят.
//These represent the edges between the two paired nodes
AdjacencyList: (1,2) (1,4) (1,3) (2,4) (2,5) (3,6) (4,6) (4,7) (4,3) (5,4) (5,7) (7,6)
//The first is the node name and the second element is how many edges come into that node.
countList: (1,0) (2,1) (3,2) (4,3) (5,1) (6,3) (7,2)
Мой вывод должен быть либо:
Queue: 1,2,5,4,3,7,6
//or
Queue: 1,2,5,4,7,3,6
Хорошо я добавил
countList.at (IT-> первый) -;
после того, как я помещаю вершину в очередь. Так что это должно уменьшить счет этой вершины до -1.
Это сузило мой выход много.
ОК, ЭТО РАБОТАЕТ СЕЙЧАС !!!
Я изменил цикл while, чтобы он останавливался после того, как очередь пуста, и напечатал очередь в цикле while, и это устранило проблему.
Мой вывод сейчас:
Queue: 1, 2, 5, 4, 7, 3, 6,
Хорошо, этот код будет работать, только если имена узлов имеют только одно значение.
Как бы я изменил отображение adjList для значений, имена которых длиннее одного символа?
Возможно связанный список, на который указывает значение ключа? И если так, как бы я это сделал?
Хорошо, теперь мы куда-то добираемся.
Самая первая версия (перед вашим редактированием) неправильно уменьшала количество входящих фронтов.
Теперь есть еще одна проблема: в каждой итерации вы многократно берете уже взятые узлы (хороший пример — узел № 1), потому что они все еще имеют нулевой счет (количество входящих ребер). Снижая их предков снова и снова, некоторые из счетчиков упадут ниже нуля (например, для узла № 2).
Вы должны как-то пометить уже использованные узлы и не использовать их снова и снова в каждом цикле. Это может быть достигнуто либо а) установкой некоторого флага для узла, б) использованием набора используемых узлов, в) удалением узла из списка, либо (вероятно, самым простым) г) установлением их числа ребер в отрицательное значение. число (например, -1) после помещения их в очередь вывода.
После вашего второго редактирования алгоритм как таковой должен работать (он работает для меня после некоторых незначительных изменений). Однако использование adjList довольно странно — как вы точно включаете несколько ребер для одного узла в карту?
Других решений пока нет …