Может ли кто-нибудь предоставить мне подробное наглядное объяснение того, что происходит внутри этого кода?
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 путем взятия нуля или нескольких ребер дерева и, возможно, одного заднего ребра (в этом порядке).