Как найти самый большой двухсторонний подграф в данном графе? - PullRequest
Новая
       64

Как найти самый большой двухсторонний подграф в данном графе?

0 голосов
/ 07 июня 2018

Учитывая неориентированный невзвешенный граф: он может быть циклическим, и каждая вершина имеет определенное значение, как показано на рисунке.график (наибольшее означает максимальное количество вершин (связанных) в этом графе)?

Ответ:

The solution is shown here

Самый большой график - оранжевый, поэтому ответ 8.

Мой подход: 

#define loop(i,n) for(int i=0;i<n;i++)                                    
int vis[N+1];
vector<int> adj[N+1]            // graph in adjacency vector list
int dfs(int current_vertex,int parent,int original_value,int other_value){
    int ans=0;
    vis[current_vertex]=1;                    // mark as visited  

    // map for adding values from neighbours having same value   
    map<int,int> mp;  
    // if curr vertex has value original_value then look for the neighbours  
    // having value as other,but if other is not defined define it   

    if(value[current_vertex]==original_value){   
        loop(i,adj[current_vertex].size()){
            int v=adj[current_vertex][i];
            if(v==parent)continue;
            if(!vis[v]){
                if(value[v]==other_value){
                   mp[value[v]]+=dfs(v,current_vertex,original,other);
                }
                else if(other==-1){  
                   mp[value[v]]+=dfs(v,current_vertex,original,value[v]);
                }
            }
        }
    }
   //else if the current_vertex has other value than look for original_value
    else{
        loop(i,adj[current_vertex].size()){
            int v=adj[current_vertex][i];
            if(v==p)continue;
            if(!vis[v]){
                if(value[v]==original){
                    mp[value[v]]+=dfs(v,current_vertex,original,other);
                }
            }
        }
    }    
    // find maximum length that can be found from neighbours of curr_vertex
    map<int,int> ::iterator ir=mp.begin();
    while(ir!=mp.end()){
        ans=max(ans,ir->second);
        ir++;
    }   
    return ans+1;
}

вызов: 

// N is the number of vertices in original graph : n=|V|
for(int i=0;i<N;i++){  
    ans=max(ans,dfs(i,-1,value[i],-1);  
    memset(vis,0,sizeof(vis));  
}

Но я бы хотел улучшить это, чтобы запустить в O(|V|+|E|) время.|V| - количество вершин, |E| - количество ребер, и как мне это сделать?

1 Ответ

0 голосов
/ 09 июня 2018

Это не кажется сложным.Пройдите по списку ребер и добавьте каждый к мультикарте, снабженной каноническими парами меток вершин (1,2,3 на диаграмме, например, с самым низким значением метки вершины первым в паре).

Теперь для каждого значения в мультикарте - который представляет собой список ребер - накапливается соответствующий набор вершин.

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

Этот алгоритм дважды пересекает каждое ребро, выполняя фиксированное число карт и операций набора для ребра.Таким образом, его амортизированное время выполнения и пространство действительно O (| V | + | E |).

Обратите внимание, что, вероятно, проще реализовать этот алгоритм с представлением списка смежности, чем с матрицей, потому что список явно дает преимущество.Матрица требует более тщательного обхода (например, DFS), чтобы избежать производительности Omega (| V | ^ 2).

...