0

Попробовал сделать функцию для поиска точек сочленения графа через обход в глубину, весь интернет перекопал, но так и не смог интерпретировать это на СИ, получился такой код,вроде верный, но точки он не ищет, можете подсказать что может быть не так? Массив Matrix это изначальный массив графа где указаны связи. matrix имеет вид

0 1 0 1 0 0
1 0 1 1 0 0
0 1 0 0 0 0
1 1 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0

и функция должна выводить 2 и 4

int time, tin[100], up[100], visit[100], count;
 
void dfs (int v, int p) {
    time++;
    visit[v] = 1;
    tin[v] = time;
    up[v] = time;
    count = 0;
    
    for (int i = 0; i < n; i++) {
        int to = matrix[v][i];
        if (to == p)  continue;
        if (visit[to] == 1)
            if (up[v] > tin[to]) up[v] = tin[to];
        else {
            dfs (to, v);
            count++;
            if (up[v] > up[to]) up[v] = up[to];
            if (up[to] >= tin[v] && p != -1)
                printf("%d", v);
        }
    }
    if (p == -1 && count > 1)   printf("%d", v);
} 

void findCutPoints(){
    for (int i = 0; i < n; i++){
        if  (visit[i] != 1){
            dfs(i, -1);
        }
    }
}
0

1 ответ 1

0

Это код с емакса. Однако вы используете его с матрицей, а не со списками смежности, и не учли этого - в to надо заносить номер смежной вершины, а не наличие ребра.

Я подправил начало цикла, теперь выводит 1 3 (2 и 4 при нумерации с единицы), и логику ифов, но, видимо, чего-то ещё не заметил, и ещё и 0 добавляет.

int timer, tin[100], up[100], visit[100], count, n=6;
int matrix[6][6] = 
   {{0, 1, 0, 1, 0, 0},
    {1, 0, 1, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 1},
    {0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 1, 0}};

void dfs(int v, int p) {
    visit[v] = 1;
    timer++;
    tin[v] = timer;
    up[v] = timer;
    count = 0;

    for (int i = 0; i < n; i++) {
        if (matrix[v][i]==0 || i==v)
            continue;
        int to = i;
        if (to == p)  continue;
        if (visit[to] == 1) {
            if (up[v] > tin[to])
                up[v] = tin[to];
        }
        else{
                dfs(to, v);
                if (up[v] > up[to]) up[v] = up[to];
                if (up[to] >= tin[v] && p != -1)
                    printf("%d", v);
                count++;
        }
    }
    if (p == -1 && count > 1)   printf("%d", v);
}

void findCutPoints() {
    for (int i = 0; i < n; i++) {
        if (visit[i] != 1) {
            dfs(i, -1);
        }
    }
}

int main()
{
    findCutPoints();
} 
3
  • спасибо, но если у нас будет матрица {0, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 0}, {0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 0} то оно выводит 1, 3, хотя должно 2, 4
    – qyver
    17 мая 2022 в 17:16
  • printf("%d", v+1);
    – MBo
    17 мая 2022 в 17:26
  • Ну что, получилось?
    – MBo
    18 мая 2022 в 5:00

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.