Создание списка смежности для DFS
У меня проблемы с созданием поиска в глубину для моей программы. Пока у меня есть класс ребер и класс областей. Я хочу хранить все связанные ребра внутри одного узла моего региона. Я могу сказать, связано ли что-то с функцией getKey (), которую я уже реализовал. Если два ребра имеют одинаковый ключ, то они соединены. Для следующего региона я хочу сохранить еще один набор связанных ребер внутри этого региона и т. Д. И т. Д. Однако я не до конца понимаю DFS и у меня возникли некоторые проблемы с его реализацией. Я не уверен, когда и где снова вызывать DFS. Любая помощь будет оценена!
class edge
{
private:
int source, destination, length;
int key;
edge *next;
public:
getKey(){ return key; }
}
class region
{
edge *data;
edge *next;
region() { data = new edge(); next = NULL; }
};
void runDFS(int i, edge **edge, int a)
{
region *head = new region();
aa[i]->visited == true;//mark the first vertex as true
for(int v = 0; v < a; v++)
{
if(tem->edge[i].getKey() == tem->edge[v].getKey()) //if the edges of the vertex have the same root
{
if(head->data == NULL)
{
head->data = aa[i];
head->data->next == NULL;
} //create an edge
if(head->data)
{
head->data->next = aa[i];
head->data->next->next == NULL;
}//if there is already a node connected to ti
}
if(aa[v]->visited == false)
runDFS(v, edge, a); //call the DFS again
} //for loop
}
Решение
при условии, что n — общее число ребер, k — конечное число областей.
Создание списка смежности для требуемой DFS может быть слишком дорогостоящим O (n ^ 2) (если k = 1, т.е. все ребра принадлежат одному региону), и, следовательно, dfs будет стоить вам O (V + E), т. Е. O (n ^ 2) в худший случай.
В противном случае задача легко решается в O (n * log (k)) следующим образом:
- Пройдите через все ребра, добавив их в заголовок соответствующих областей (используя сбалансированный bst, например, stl-map) [для этого вы также можете использовать хеширование]
- пройти через все регионы и соединить их нужным линейным способом
Я полагаю, что для этой проблемы не существует гарантированного решения O (n).
Другие решения
Я попытался реализовать функцию создания списка смежности. Следующий указатель структуры adj_list переносит вас вниз по списку смежности (нет связи между двумя узлами, соединенными следующим), а указатель списка является списком смежности. Узел имеет адрес adj_list, у которого есть список смежности.
struct node{
int id;
adj_list* adj;
};struct adj_list{
adj_list* next;
adj_list* list;
node* n;
adj_list(node& _n){
n = &(_n);
next = NULL;
list = NULL;
}
};
node* add_node(int id,std::queue<int> q , node* root)
{
node* n = new node(id);
adj_list* adj = new adj_list(*n);
n->adj = adj;
if(root == NULL){
return n;
}
std::queue<adj_list*> q1;
while(1){
adj_list* iter = root->adj;
if(q.empty())break;
int k = q.front();
q.pop();
while(iter){
if(iter->n->id == k){
q1.push(iter);
adj_list* temp = iter->list;
iter->list = new adj_list(*n);
break;
}
iter = iter->next;
}
}
adj_list* iter = root->adj;
while(iter->next){
iter = iter->next;
}
iter->next = adj;
while(!q1.empty()){
adj_list* temp = q1.front();
q1.pop();
adj->list = temp;
adj = temp;
}
return root;
}