어떻게 그래프로 bicomponents를 찾을 수 있습니까? 불리는 블럭

Question

나의 tryings와 copypastings. 하지만 biconnectedcomponent (블록이라고 부름)를 찾으려면 무엇을 써야합니까?

#include <fstream> 
#include <vector> 
using namespace std; 
ifstream cin ("test3.txt"); 
ofstream cout ("output.txt"); 

const int l = 6; 
int G[l][l]; 
int MAXN; 
int used[l]; 
int number[l], low[l], counter = 1, kids = 0; 
vector <int> block[l]; 

void BiComp(int curr, int prev) { 
    int kids = 0; 
    low[curr] = number[curr] = counter++; 
    used[curr] = 1; 
    for(int i = 0; i < MAXN; i++) { 
     if(G[curr][i] == 1) { 
      if (i != prev) { 
       if (used[i] == 0) { 

        kids++; 
        block[0].push_back(curr); 
        block[0].push_back(i); 
        BiComp(i, curr); 
        low[curr] = min(low[curr], low[i]); 
        if(low[i] >= number[curr] && (prev != -1 || kids >= 2)) { 
         cout << "tochka " << curr + 1 << endl; 

        } 



       } else { 

        block[0].push_back(i); 
        block[0].push_back(prev); 
        cout<<block<<endl; 
        low[curr] = min(low[curr], number[i]); 
       } 
      } 
     } 
    } 
} 

void main() 
{ 
    MAXN = 6; 
    for (int i = 0; i < MAXN; i++) 
    { 
     for (int j = 0; j < MAXN; j++) 
     { 
      cin >> G[i][j]; 
      cout << G[i][j] << " "; 
     } 
     cout << endl; 
    } 
    //for (int i = 0; i < MAXN; i++) { 
     //if (number[i] == 0) { 
      BiComp(0, -1); 
     //} 
    //} 
} 

어떻게하면이 코드를 통해 같은 시간 블록에서 절단 점을 찾을 수 있습니까 ??? 그래프 이론에서 biconnected 구성 요소 (또는 2 연결 구성 요소)는 최대 biconnected 하위 그래프입니다.

Answer 1

좋아요. 내 머리에 떠오르는 점은 확장 성이 좋지 않은 매우 강력한 접근 방식이지만, 이중 연결 구성 요소를 찾는 것이 실제로 계산적으로 어려운 문제라는 것을 기억합니다. 그런 다음 최적화가 수행되는지 확인하십시오.

N 개 노드 세트가 주어지면 노드의 각 가능한 서브 세트가 biconnected 구성 요소를 형성하는지 여부를 점검하십시오. 일반적으로 가장 큰 구성 요소를 사용할 수 있기를 원할 것입니다. 전체 그래프로 시작한 다음 N-1 노드, N-2 등의 모든 하위 그래프로 시작하십시오. 한 가지 해결책을 찾 자마자 가능한 가장 큰 크기 중 하나를 찾았고 그럴 수 있다는 것을 알게됩니다. 그래도 최악의 경우 2^N 하위 그래프를 검사하게됩니다. 먼저 테스트 할 그래프를 만드는 루프부터 시작하십시오.

K 노드가있는 주어진 그래프가 이중 연결 구성 요소인지 확인하려면 모든 K * (K-1)/2 쌍의 노드를 반복하여 그 사이에 두 개의 독립된 경로가 있는지 확인하십시오.

두 노드 i와 j가 이중 연결되어 있는지 확인하려면 먼저 노드 사이의 모든 경로를 찾습니다. 각 경로에 대해 해당 경로에 대한 대체 연결이 있는지 확인하십시오. 하나를 찾으면 그 쌍을 위해 끝났습니다. 그렇지 않다면 찾고있는 그래프가 이중 연결이 아니며 모든 루프에서 끊어져 바깥 쪽 그래프에서 벗어나 다음 그래프를 테스트 할 수 있다는 증거를 발견했습니다.

i와 j 사이에 다른 연결이 있는지 확인하려면 첫 번째 경로에서 사용한 모든 가장자리를 제거하고 다른 경로를 찾을 수 있는지 확인하십시오. 할 수 있다면, 당신은 i와 j에서 괜찮습니다. 그렇지 않으면 찾은 경로의 초기 목록에서 다음 경로를 계속하십시오. 관련 에지를 제거 할 때 대안이없는 경로 목록의 끝 부분에 도달하면 두 노드는 이중 연결이 아니므로 전체 그래프가 아닌 것입니다.

Answer 2

깊이 우선 검색을 사용하여 주어진 그래프에서 모든 절단 점 (또는 절단 점 또는 관절 점)을 찾는 선형 실행 시간 알고리즘이 있습니다.

모든 절단 점을 찾으면 모든 이중 요소를 쉽게 찾을 수 있습니다.