Вырезать вершину (или) точку сочленения - PullRequest
0 голосов
/ 27 марта 2019

Может ли кто-нибудь предоставить мне подробное наглядное объяснение того, что происходит внутри этого кода?

int adjMatrix[256][256];
int dfsnum[256], num = 0, low[256];
void cutVertices(int u) {
    low[u] = dfsnum[u] = num++;
    for(int v = 0; v<256; ++v) {
        if(adjMatrix[u][v] && dfsnum[v] == -1) {
            if(low[v] > dfsnum[u]) 
                printf("CutVertex:%d",u);
            low[u] = min(low[u], low[v]);
       }
       else {
           low[u] = min(low[u], dfsnum[v]);
   }
   }

На самом деле это метод нахождения резцов с использованием результирующего дерева поиска DFS.

метод говорит, что корневая вершина является вырезанной вершиной тогда и только тогда, когда у нее есть по крайней мере два потомка. Некорневая вершина u является разрезанной вершиной тогда и только тогда, когда существует такой сын v, что low (v)> = dfsnum (u). где low (v) = вершина с наименьшим номером, достижимая из v путем взятия нуля или нескольких ребер дерева и, возможно, одного заднего ребра (в этом порядке).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...