Оптимизация алгоритма для проверки того, «есть ли для данного ориентированного графа только один способ сортировки графа с использованием топологической сортировки, или нет»
Мой алгоритм для этого:
- Сначала рассчитать степень свободы каждого узла, то есть подсчитать, сколько
есть ребра, для которых этот узел является приемником для них. - Теперь будут помещены только те в очереди, у которых значение Indegree == 0, потому что они будут первыми, кто появится в отсортированном топологическом списке графа.
- Если сейчас начальный размер очереди равен нулю. это означает «График не может быть отсортирован».
- иначе мы начнем метод сортировки.
- Если мы сталкиваемся с тем, что более 2 вершин присутствуют в очереди в любое время, это означает, что «Возможны несколько последовательностей»
- Но может быть случай, когда дальнейшая последовательность не будет возможна.
- Поэтому я отслеживаю узел, который вытолкнул (удален из Front) из очереди. и считать их тоже.
- Если в конце счетчик == число узлов. И флаг для нескольких последовательностей не установлен, то последовательность возможна «График может быть отсортирован».
- или если установлено число == количество узлов и флаг для последовательности Mutiple. мы говорим: «Возможна множественная последовательность»
- если считать! = количество узлов. тогда «График не может быть отсортирован»
Вот моя реализация моей идеи
vector<vector<int> >list(10000); // Graph is represented as Adjacency list
void topological_sort()
{
int i,l,item,j;
k=0;
queue<int>q; // Queue
vector<int>:: iterator it;
for(i=1;i<=n;i++) // Pushing nodes those who have indegree=0
{
if(indegree[i]==0)
q.push(i);
}
l=q.size();
if(l==0)
{
flag=2; // means no sequence is possible
return;
}
while(q.empty()==0)
{
l=q.size();
if(l>1)
flag=1; // multiple sequence possible for sure but check whether this is fully possible or not
item=q.front();
q.pop();
ans[k++]=item;
for(it=list[item].begin();it!=list[item].end();it++)
{
j=*it;
indegree[j]--;
if(indegree[j]==0)
q.push(j);
}
}
if(k!=n)
flag=2; // no sequence is possible.
}
Этот алгоритм слишком медленный! или просто наивная реализация. Какие дальнейшие улучшения возможны для этого. или как я могу использовать топологическую сортировку с использованием DFS для этого?
Решение
Теорема:
Ориентированный граф имеет уникальную топологическую сортировку тогда и только тогда, когда он является ориентированной цепью.
Доказательство оставлено как упражнение для вас
Чтобы определить, имеет ли ориентированный граф уникальный топологический вид, все, что вам нужно сделать, это:
- Найти любой узел с градусом 0
- Если его нет, график имеет цикл и не иметь уникальный топологический вид
- Повторно следуйте первому выходу текущего узла, добавляя посещенные узлы в набор по мере продвижения
- Остановитесь, когда:
- Вы достигнете узла, который вы уже посетили — график имеет цикл, поэтому он не иметь уникальный топологический вид
- Вы попадаете в тупик — граф имеет уникальную топологическую сортировку тогда и только тогда, когда набор посещенных узлов содержит все узлы в графе.
Ваш код, кажется, не следует этому простому подходу. (Поправьте меня, если я ошибаюсь!) Поэтому, вместо того, чтобы пытаться выяснить, верен ли ваш код или нет, я бы предложил просто использовать схему алгоритма, приведенную выше.
Другие решения
Других решений пока нет …