Algorytmy i Struktury Danych - Punkty artykulacji w grafie

Naiwny sposób rozwiązania tego problemu jest następujący:

Obliczamy wstępnie liczbę spójnych składowych w grafie (możemy tutaj wykorzystać algorytm opisany w rozdziale o spójnych składowych) i zapamiętujemy ją. Następnie przechodzimy przez kolejne wierzchołki grafu. Każdy bieżący wierzchołek usuwamy wraz ze wszystkimi incydentnymi z nim krawędziami i ponownie obliczamy liczbę spójnych składowych. Jeśli jest ona większa od zapamiętanej, to usunięty wierzchołek jest punktem artykulacji i zapamiętujemy go na liście. Wierzchołek wstawiamy z powrotem wraz ze wszystkimi usuniętymi poprzednio krawędziami i przechodzimy do następnego wierzchołka. Gdy algorytm zakończy działanie, lista będzie zawierała wszystkie punkty artykulacji grafu.

Algorytm naiwny wyszukiwania punktów artykulacji w grafie nieskierowanym

Wejście:

n : liczba wierzchołków w grafie; n ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

L : lista par wierzchołków, które tworzą krawędzie-mosty.

Elementy pomocnicze:

ccn(n, graf) : funkcja zwracająca liczbę spójnych składowych w grafie.
nc : liczba spójnych składowych grafu; nc ∈ C.
v : numery wierzchołka grafu; v ∈ C.

Lista kroków:

K01: Utwórz pustą listę L
K02: nc ← ccn(n, graf) ; zapamiętujemy liczbę spójnych składowych
K03: Dla v = 0, 1, …, n-1, ; przechodzimy przez
     wykonuj kroki K04…K06 ; kolejne wierzchołki grafu
K04:   Usuń wierzchołek v z grafu wraz z jego krawędziami
K05:   Jeśli ccn(v, graf) > nc, ; jeśli v jest punktem artykulacji,
       to dodaj v do L ; to zapamiętujemy go w L
K06:   Odtwórz wierzchołek v w grafie wraz z jego krawędziami
K07: Zakończ ; punkty artykulacji w L

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie punkty artykulacji i wypisuje je w oknie konsoli. Ponieważ usuwanie i odtwarzanie wierzchołka grafu może być kłopotliwe, zastosowaliśmy dodatkową tablicę logiczną VU. Elementy tej tablicy odpowiadają wierzchołkom grafu. Wierzchołek obecny w grafie ma w tej tablicy wartość true. Wierzchołek usunięty ma wartość false.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

8 11
0 1
0 2
0 3
0 5
1 4
1 5
2 3
3 6
3 7
4 5
6 7

Pascal

// Wyszukiwanie punktów artykulacji
// w grafie nieskierowanym
// Data: 29.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------

program artpnts;

// Typy dla dynamicznej tablicy
// list sąsiedztwa, stosu
// i listy punktów artykulacji
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    v    : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//-------------------------------
function Stack.top : integer;
begin
  if s <> nil then
    top := S^.v
  else
    top := -2;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
begin
  if S <> nil then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Funkcja oblicza liczbę
// spójnych składowych w grafie
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// VU - tablica dostępności
//      krawędzi grafu
//---------------------------------
function ccn(n : integer;
             var graf : TList;
             VU : array of boolean)
                : integer;
var
  C : array of integer;
  S : Stack;
  cc, i, v, u : integer;
  p : PSLel;

begin
  // Tworzymy pusty stos
  S.init;
  // Tworzymy tablicę
  // spójnych składowych
  SetLength(C, n);
  for i := 0 to n-1 do
    // Zerujemy tablicę
    // spójnych składowych
    C[i] := 0;
  // Zerujemy licznik
  // spójnych składowych
  cc := 0;
  for i := 0 to n-1 do
    // Szukamy nieodwiedzonego
    // jeszcze wierzchołka
    if VU[i] and (C[i] = 0) then
    begin
      // Zwiększamy licznik
      // składowych
      inc(cc);
      // Na stosie umieszczamy
      // numer bieżącego węzła
      S.push(i);
      // Wierzchołek numerujemy
      // i oznaczamy
      // jako odwiedzony
      C[i] := cc;
      // Przechodzimy graf
      // algorytmem DFS
      while not S.empty do
      begin
        // Pobieramy wierzchołek
        v := S.top;
        // Usuwamy go ze stosu
        S.pop;
        // Przeglądamy sąsiadów
        // wierzchołka v
        p := graf[v];
        while p <> nil do
        begin
          u := p^.v;
          if VU[u] and
            (C[u] = 0) then
          begin
            // Na stos idą
            // sąsiedzi
            // nieodwiedzeni
            S.push(u);
            // i ponumerowani
            C[u] := cc
          end;
          p := p^.next;
        end;
      end;
    end;
  // Usuwamy tablicę C
  SetLength(C, 0);
  // Usuwamy stos
  S.destroy;
  // Zwracamy wynik
  ccn := cc;
end;

// **********************
// *** Program główny ***
// **********************

var
  // Liczba wierzchołków
  // i krawędzi
  n, m : integer;
  // Tablica list sąsiedztwa
  A : TList;
  nc, i, v, u : integer;
  L, p, r : PSLel;
  VU : array of boolean;

begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  SetLength(VU, n);
  for i := 0 to n-1 do
  begin
    A[i]  := nil;
    VU[i] := true;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako w
    p^.v := u;
    // Dodajemy go na początek
    // listy A[v]
    p^.next := A[v];
    A[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    p^.next := A[u];
    A[u] := p;
  end;
  // Algorytm znajdowania
  // punktów artykulacji
  //---------------------
  // Pusta lista
  // punktów artykulacji
  L := nil;
  // Zapamiętujemy liczbę
  // spójnych składowych
  nc := ccn(n, A, VU);
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for v := 0 to n-1 do
  begin
    // Oznaczamy wierzchołek v
    // jako usunięty
    VU[v] := false;
    // Sprawdzamy, czy v jest
    // punktem artykulacji
    if ccn(n, A, VU) > nc then
    begin
      // Jeśli tak,
      // dołączamy go do listy
      new(p);
      p^.v := v;
      p^.next := L;
      L := p;
    end;
    // Odtwarzamy wierzchołek
    VU[v] := true;
  end;
  writeln;
  // Wypisujemy znalezione
  // punkty artykulacji,
  // jednocześnie usuwając
  // listę L
  while L <> nil do
  begin
    write(L^.v, ' ');
    p := L;
    L := L^.next;
    dispose(p);
  end;
  writeln;
  // Usuwamy pozostałe
  // struktury dynamiczne
  for i := 0 to n-1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(A, 0);
  SetLength(VU, 0);
end.

C++

// Wyszukiwanie punktów artykulacji
// w grafie nieskierowanym
// Data: 29.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list
// sąsiedztwa, stosu i listy punktów
// artykulacji
struct SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

  public:
    Stack(); // konstruktor
    ~Stack(); // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty (void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top (void)
{
  if(S)
    return S->v;
  else
    return -2;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja oblicza liczbę
// spójnych składowych
// w grafie
// n - liczba wierzchołków
//     w grafie
// graf - tablica list
//        sąsiedztwa
// VU - tablica dostępności
//      krawędzi grafu
//-------------------------
int ccn(int n,
        SLel ** graf,
        bool * VU)
{
  int * C, cc, i, v, u;
  Stack S;
  SLel * p;

  // Tworzymy tablicę
  // spójnych składowych
  C = new int [n];

  // Zerujemy tablicę
  // spójnych składowych
  for(i = 0; i < n; i++)
    C[i] = 0;
  // Zerujemy licznik
  // spójnych składowych
  cc = 0;
  for(i = 0; i < n; i++)
    // Szukamy nieodwiedzonego
    // jeszcze wierzchołka
    if(VU[i] && !C[i])
    {
      // Zwiększamy licznik
      // składowych
      cc++;
      // Na stosie umieszczamy
      // numer bieżącego węzła
      S.push(i);
      // Wierzchołek numerujemy
      // i oznaczamy jako odwiedzony
      C[i] = cc;
      // Przechodzimy graf
      // algorytmem DFS
      while(!S.empty())
      {
        // Pobieramy wierzchołek
        v = S.top();
        // Usuwamy go ze stosu
        S.pop();
        // Przeglądamy sąsiadów
        // wierzchołka v
        for(p = graf[v];
            p;
            p = p->next)
        {
          u = p->v;
          if(VU[u] && !C[u])
          {
            // Na stos idą
            // sąsiedzi nieodwiedzeni
            S.push(u);
            // i ponumerowani
            C[u] = cc;
          }
        }
      }
    }

  // Usuwamy tablicę C
  delete [] C;
  // Zwracamy wynik
  return cc;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  // Liczba wierzchołków
  // i krawędzi
  int n, m;
  // Tablica list sąsiedztwa
  SLel ** A;
  int nc, i, v, u;
  SLel * L, * p, * r;
  bool * VU;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy zmienne
  // dynamiczne
  //-----------------
  // Krawędzie aktywne
  VU = new bool [n];
  // Tablica list sąsiedztwa
  A  = new SLel * [n];
  // Tablicę wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
  {
    A[i] = nullptr;
    VU[i] = true;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    p = new SLel;
    p->v = u;
    p->next = A[v];
    A[v] = p;
    p = new SLel;
    p->v = v;
    p->next = A[u];
    A[u] = p;
  }
  // Algorytm znajdowania
  // punktów artykulacji
  //---------------------
  // Pusta lista
  // punktów artykulacji
  L = nullptr;
  // Zapamiętujemy liczbę
  // spójnych składowych
  nc = ccn(n, A, VU);
  // Przechodzimy przez
  // kolejne wierzchołki
  // grafu
  for(v = 0; v < n; v++)
  {
    // Oznaczamy wierzchołek v
    // jako usunięty
    VU[v] = false;
    // Sprawdzamy, czy v jest
    // punktem artykulacji
    if(ccn(n, A, VU) > nc)
    {
      // Jeśli tak,
      // dołączamy go do listy
      p = new SLel;
      p->v = v;
      p->next = L;
      L = p;
    }
    // Odtwarzamy wierzchołek
    VU[v] = true;
  }
  cout << endl;
  // Wypisujemy znalezione
  // punkty artykulacji,
  // jednocześnie usuwając
  // listę L
  while(L)
  {
    cout << L->v << " ";
    p = L;
    L = L->next;
    delete [] p;
  }
  cout << endl;
  // Usuwamy dynamiczne
  // struktury danych
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] VU;
  return 0;
}

Basic

' Wyszukiwanie punktów artykulacji
' w grafie nieskierowanym
' Data: 29.12.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa, stosu
' i listy punktów artykulacji
Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack()
  While S
  	 pop
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function Stack.top As Integer
  If S <> 0 Then
    top = S->v
  Else
    top = -2
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
    e = S
    S = S->next
    Delete e
  End If
End Sub

' Funkcja oblicza liczbę spójnych
' składowych w grafie
' n - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' VU - tablica dostępności krawędzi
'      grafu
'---------------------------------
Function ccn(ByVal n As Integer, _
         ByVal graf As SLel Ptr Ptr, _
         ByVal VU As Byte Ptr) _
                  As Integer
  Dim As Integer Ptr C
  Dim As Integer cc, i, v, u
  Dim As Stack S
  Dim As SLel Ptr p

  ' Tworzymy tablicę
  ' spójnych składowych
  C = New Integer [n]
  For i = 0 To n-1
    ' Zerujemy tablicę
    ' spójnych składowych
    C[i] = 0
  Next
  ' Zerujemy licznik
  ' spójnych składowych
  cc = 0
  For i = 0 To n-1
    ' Szukamy nieodwiedzonego
    ' jeszcze wierzchołka
    If (VU[i] = 1) AndAlso _
       (C[i] = 0) Then
      ' Zwiększamy licznik składowych
      cc += 1
      ' Na stosie umieszczamy numer
      ' bieżącego węzła
      S.push(i)
      ' Wierzchołek numerujemy
      ' i oznaczamy jako odwiedzony
      C[i] = cc
      ' Przechodzimy graf
      ' algorytmem DFS
      While S.empty = 0
        ' Pobieramy wierzchołek
        v = S.top
        ' Usuwamy go ze stosu
        S.pop
        ' Przeglądamy sąsiadów
        ' wierzchołka v
        p = graf[v]
        While p
          u = p->v
          if (VU[u] = 1) Andalso _
             (C[u] = 0) Then
            ' Na stos idą
            ' sąsiedzi nieodwiedzeni
            S.push(u)
            ' i ponumerowani
            C[u] = cc
          End If
          p = p->next
        Wend
      Wend
    End If
  Next
  ' Usuwamy tablicę C
  Delete [] C
  ' Zwracamy wynik
  Return cc
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer n, m, nc, i, v, u
Dim As SLel Ptr Ptr A
Dim As SLel Ptr L, p, r
Dim As Byte Ptr VU

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
A = New SLel Ptr [n]
' Krawędzie aktywne
VU = New Byte [n]
' Tablicę A wypełniamy
' pustymi listami, a tablicę C
' wypełniamy zerami
For i = 0 To n-1
  A[i] = 0
  VU[i] = 1
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 0 To m-1
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek
  ' listy A[v]
  p->next = A[v]
  A[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = new SLel
  p->v = v
  p->next = A[u]
  A[u] = p
Next
' Algorytm znajdowania
' punktów artykulacji
'---------------------
' Pusta lista punktów artykulacji
L = 0
' Zapamiętujemy liczbę
' spójnych składowych
nc = ccn(n, A, VU)
' Przechodzimy przez kolejne
' wierzchołki grafu
For v = 0 To n-1
  ' Oznaczamy wierzchołek v
  ' jako usunięty
  VU[v] = 0
  ' Sprawdzamy, czy v jest
  ' punktem artykulacji
  If ccn(n, A, VU) > nc Then
    ' Jeśli tak,
    ' dołączamy go do listy
    p = New SLel
    p->v = v
    p->next = L
    L = p
  End If
  ' Odtwarzamy wierzchołek
  VU[v] = 1
Next
Print
' Wypisujemy znalezione
' punkty artykulacji,
' jednocześnie usuwając listę L
While L
  print L->v;
  p = L
  L = L->next
  Delete [] p
Wend
Print
' Usuwamy dynamiczne
' struktury danych
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] A
Delete [] VU
End

Python (dodatek)

# Wyszukiwanie punktów artykulacji
# w grafie nieskierowanym
# Data: 13.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------------

# Klasy dla dynamicznej tablicy
# list sąsiedztwa, stosu
# i listy punktów artykulacji
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu.
    def top(self):
        if self.s:
            return self.s.v
        else:
            return -2


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Funkcja oblicza liczbę spójnych
# składowych w grafie
# n - liczba wierzchołków w grafie
# graf - tablica list sąsiedztwa
# VU - tablica dostępności krawędzi
#      grafu
def ccn(n, graf, vu):
    s = Stack()

    # Tworzymy tablicę
    # spójnych składowych
    c = [0] * n
    # Zerujemy licznik
    # spójnych składowych
    cc = 0
    for i in range(n):
        # Szukamy nieodwiedzonego
        # jeszcze wierzchołka
        if vu[i] and not c[i]:
            # Zwiększamy licznik
            # składowych
            cc += 1
            # Na stosie umieszczamy numer
            # bieżącego węzła
            s.push(i)
            # Wierzchołek numerujemy
            # i oznaczamy jako odwiedzony
            c[i] = cc
            # Przechodzimy graf
            # algorytmem DFS
            while not s.empty():
                # Pobieramy wierzchołek
                v = s.top()
                # Usuwamy go ze stosu
                s.pop()
                # Przeglądamy sąsiadów
                # wierzchołka v
                p = graf[v]
                while p:
                    u = p.v
                    if vu[u] and not c[u]:
                        # Na stos idą
                        # sąsiedzi
                        # nieodwiedzeni
                        s.push(u)
                        # i ponumerowani
                        c[u] = cc
                    p = p.next
    # Usuwamy tablicę C
    del c
    # Zwracamy wynik
    return cc


# **********************
# *** Program główny ***
# **********************

# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
a = [None] * n
# Krawędzie aktywne
vu = [True] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek
    # listy A[v]
    p.next = a[v]
    a[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    p.next = a[u]
    a[u] = p
# Algorytm znajdowania
# punktów artykulacji
#---------------------
# Pusta lista punktów artykulacji
lst = None
# Zapamiętujemy liczbę
# spójnych składowych
nc = ccn(n, a, vu)
# Przechodzimy przez kolejne
# wierzchołki grafu
for v in range(n):
    # Oznaczamy wierzchołek v
    # jako usunięty
    vu[v] = False
    # Sprawdzamy, czy v jest
    # punktem artykulacji
    if ccn(n, a, vu) > nc:
        # Jeśli tak,
        # dołączamy go do listy
        p = SLel()
        p.v = v
        p.next = lst
        lst = p
    # Odtwarzamy wierzchołek
    vu[v] = True
print()
# Wypisujemy znalezione
# punkty artykulacji,
# jednocześnie usuwając listę lst
while lst:
    print(lst.v, end=" ")
    lst = lst.next
print()
# Usuwamy dynamiczne
# struktury danych
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vu

Wynik:
8 11 0 1 0 2 0 3 0 5 1 4 1 5 2 3 3 6 3 7 4 5 6 7 3 0

do podrozdziału do strony

Do szybkiego wyszukiwania punktów artykulacji wykorzystujemy podobny algorytm jak do wyszukiwania mostów. Idea tego algorytmu również opiera się na drzewie rozpinającym grafu oraz na przejściu wstecznym za pomocą DFS. W algorytmie wykorzystuje się dwie własności punktów artykulacji:

Korzeń drzewa rozpinającego w głąb grafu jest punktem artykulacji tylko wtedy, jeśli posiada co najmniej dwóch synów. Uzasadnienie tego faktu jest bardzo proste. Gdy uruchomimy przejście DFS przy tworzeniu drzewa rozpinającego, to dojdzie ono do każdego wierzchołka, do którego istnieje w grafie ścieżka od wierzchołka startowego. Zatem po uruchomieniu w korzeniu drzewa DFS odwiedzi wszystkich sąsiadów korzenia, do których w grafie istnieje ścieżka. Jeśli jakiś sąsiad zostanie nieodwiedzony przy powrocie z DFS uruchomionego dla pierwszego z synów, to znaczy, że w grafie nie było do niego innej ścieżki oprócz krawędzi bezpośrednio od korzenia do tego sąsiada. W takim przypadku powstaje kolejny syn korzenia (gdyż DFS musimy ponownie uruchomić dla każdego nieodwiedzonego sąsiada). Pomiędzy poprzednim synem istnieje droga tylko poprzez korzeń drzewa (gdyby istniała inna, to DFS by ją znalazło i dany wierzchołek nie zostałby synem korzenia, lecz jego dalszym potomkiem). Jeśli korzeń zostanie teraz usunięty z grafu, to wszyscy jego synowie na drzewie rozpinającym znajdą się w oddzielnych spójnych składowych grafu. Liczba tych składowych wzrośnie, zatem korzeń będzie punktem artykulacji.

Wierzchołek nie będący korzeniem drzewa rozpinającego w głąb jest punktem artykulacji, jeśli przynajmniej dla jednego z jego synów nie istnieje krawędź wtórna, która łączy potomka tego wierzchołka z jego przodkiem. Wyjaśnienie jest również proste. Istnienie krawędzi wtórnej oznacza, że do syna można dojść również inną drogą, która nie wiedzie poprzez dany wierzchołek. Skoro tak, to jego usunięcie nie odłączy syna od reszty grafu, gdyż wciąż będzie się znajdował w tej samej spójnej składowej z uwagi na krawędź łączącą jego potomków z innym przodkiem. Zatem liczba składowych nie wzrośnie. Jeśli natomiast taka krawędź wtórna nie istnieje, to do tego syna można przejść w grafie tylko krawędzią, która łączy go z jego ojcem. Jeśli usuniemy ojca, krawędź zniknie i syn znajdzie się w oddzielnej spójnej składowej. Liczba składowych grafu wzrośnie, zatem ojciec musi być punktem artykulacji.

Sprawdzenie pierwszej własności jest proste. Drugą własność sprawdzamy następująco:

Przechodzimy przez graf algorytmem DFS, numerując po drodze wszystkie odwiedzone wierzchołki oraz obliczając dla nich parametr Low po odwiedzeniu wszystkich sąsiadów. Przypomnijmy, parametr Low jest najmniejszą wartością z numerów nadanych przez DFS bieżącemu wierzchołkowi, wierzchołkowi połączonemu z bieżącym krawędzią wtórną oraz parametrom Low wszystkich synów na drzewie rozpinającym. Czym dokładnie jest ten parametr dla danego wierzchołka? Otóż jest to najmniejszy numer nadany przez DFS wierzchołkowi, do którego istnieje ścieżka w dół drzewa (później ścieżka ta może zawracać i tworzyć cykl). Jeśli parametr Low dla jednego z synów będzie większy lub równy numerowi DFS bieżącego wierzchołka, to będzie to oznaczało, że ścieżka zawierająca wierzchołek bieżący i tego syna nie posiada krawędzi wtórnej do przodka wierzchołka bieżącego (w takim przypadku parametr Low syna byłby mniejszy od numeru DFS jego ojca). Skoro tak, to wierzchołek bieżący jest punktem artykulacji.

Zobaczmy na prostym przykładzie, jak działa algorytm Tarjana:

	Oto nasz przykładowy graf, w którym mamy znaleźć wszystkie punkty artykulacji. Graf przejdziemy algorytmem DFS, tworząc po drodze drzewo rozpinające w głąb oraz numerując wierzchołki grafu (numeracja DFS nie ma nic wspólnego z numerami wierzchołków w definicji grafu – określa ona kolejność odwiedzin poszczególnych wierzchołków). Numery te posłużą później do wyznaczenia dla każdego wierzchołka parametru Low, gdy zostaną już przetworzeni wszyscy sąsiedzi.
	Rozpoczynamy od wierzchołka 0 (punkt startowy nie ma wpływu na wynik pracy algorytmu). Wierzchołek zaznaczamy jako odwiedzony i nadajemy mu numer DFS 1. Wierzchołek posiada trzech nieodwiedzonych jeszcze sąsiadów: 1, 2 i 3.
	Odwiedzamy wierzchołek nr 1. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 2. Krawędź 0–1 staje się krawędzią drzewa rozpinającego w głąb. Wierzchołek 0 jest korzeniem drzewa, wierzchołek 1 jest jego synem. Wierzchołek posiada jednego nieodwiedzonego sąsiada: 2.
	Odwiedzamy wierzchołek 2. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 3. Krawędź 1–2 zostaje dopisana do drzewa rozpinającego (1 jest ojcem, 2 jest synem). Wierzchołek 2 nie posiada już nieodwiedzonych sąsiadów. Wierzchołek nie ma synów, nie może być zatem punktem artykulacji. Przetwarzamy go, obliczając parametr Low jako najmniejszą liczbę z 3 (numer DFS wierzchołka) i 1 (numer DFS wierzchołka 0, który łączy się krawędzią wtórną). Wierzchołek 2 nie posiada synów na drzewie rozpinającym. Low(2) = min(3, 1) = 1 Wracamy do wierzchołka nr 1.
	Jesteśmy z powrotem w wierzchołku nr 1. Wierzchołek posiada syna nr 2, lecz parametr Low(2) = 1 jest mniejszy od numeru DSF wierzchołka nr 1 równego 2 (a oznacza to, że istnieje krawędź wtórna łącząca potomka (2) z przodkiem (0): tutaj jest to krawędź 2–0). Zatem wierzchołek ten nie może być punktem artykulacji. Ponieważ wszyscy sąsiedzi zostali już odwiedzeni, przetwarzamy wierzchołek, obliczając dla niego parametr Low. Będzie to najmniejsza wartość z 2 (numer DFS wierzchołka) i 1 (parametr Low dla jego syna 2). Low(1) = min(2, 1) = 1. Wracamy do wierzchołka 0.
	Odwiedzamy ostatniego sąsiada wierzchołka 0, czyli wierzchołek nr 3. Oznaczamy go jako odwiedzony i nadajemy mu numer DFS 4. Krawędź 0–3 zostaje dopisana do drzewa rozpinającego. Wierzchołek nr 3 ma dwóch nieodwiedzonych sąsiadów: 4 i 5.
	Odwiedzamy wierzchołek nr 4. Oznaczamy go jako odwiedzonego i nadajemy mu numer DFS 5. Krawędź 3–4 zostaje dopisana do drzewa rozpinającego. Wierzchołek posiada jednego nieodwiedzonego sąsiada: 5.
	Odwiedzamy wierzchołek 5. Oznaczamy go jako odwiedzonego i nadajemy mu numer DFS 6. Krawędź 4–5 zostaje dopisana do drzewa rozpinającego. Wierzchołek nr 5 nie posiada nieodwiedzonych sąsiadów. Wierzchołek nr 5 nie posiada synów, nie może być punktem artykulacji. Wyliczamy parametr Low jako najmniejszą wartość z 6 (numer DFS wierzchołka) i 4 (numer DFS wierzchołka 3, który łączy się krawędzią wtórną). Low(5) = min(6, 4) = 4.
	Wracamy do wierzchołka nr 4. Wszyscy sąsiedzi są odwiedzeni. Wierzchołek nr 4 posiada syna 5, lecz parametr Low(5) jest mniejszy od numeru DFS wierzchołka. Zatem wierzchołek nr 4 nie jest punktem artykulacji. Obliczamy parametr Low jako najmniejszą wartość z 5 (numer DFS wierzchołka) i 4 (parametr Low jego syna 5). Low(4) = min(5, 4) = 4.
	Wracamy do wierzchołka nr 3. Zauważamy, iż parametr syna Low(4) = 4 spełnia kryterium punktu artykulacji (jest większy lub równy numerowi DFS wierzchołka). Zatem wierzchołek nr 3 jest punktem artykulacji. Wyznaczamy parametr Low(3) jako najmniejszą wartość z 4 (numer DFS wierzchołka), 4 (parametr Low( 4) syna na drzewie rozpinającym) i 6 (numer DFS wierzchołka 5 połączonego krawędzią wtórną). Low(3) = min(4, 4, 6) = 4.
	Wracamy do wierzchołka 0. Wszyscy sąsiedzi są odwiedzeni. Ponieważ wierzchołek 0 jest korzeniem drzewa rozpinającego, to sprawdzamy dla niego pierwsze kryterium. Posiada dwóch synów na drzewie rozpinającym, zatem jest punktem artykulacji (parametru Low nawet nie musimy dla niego obliczać, gdyż nie będzie on już dalej potrzebny).

Algorytm Tarjana wyszukiwania punktów artykulacji w grafie nieskierowanym

Funkcja rekurencyjna DFSap(v,vf,graf,D,dv,L)

Wejście:

v : wierzchołek startowy; v ∈ C.
vf : ojciec wierzchołka v na drzewie rozpinającym w głąb; vf ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
D : tablica numerów DFS dla poszczególnych wierzchołków. Elementy są liczbami całkowitymi.
dv : referencja do zmiennej zewnętrznej przechowującej numery wierzchołków. Przy pierwszym wywołaniu zmienna powinna zawierać 2; dv ∈ C.
L : lista punktów artykulacji.

Wyjście:

Wartość parametru Low dla wierzchołka v. Jeśli zostanie znaleziony punkt artykulacji, to będzie on dopisany do listy L.

Elementy pomocnicze:

Low : wartość parametru Low dla bieżącego wierzchołka; Low ∈ C.
temp : chwilowo przechowuje wynik wywołania rekurencyjnego; temp ∈ C.
test : zawiera wynik testu na punkt artykulacji.

Lista kroków:

K01: D[v] ← dv ; numerujemy wierzchołek
K02: Low ← dv ; wstępna wartość parametru
K03: dv ← dv+1 ; kolejny wierzchołek będzie miał numer o 1 większy
K04: test ← false
K05: Dla każdego sąsiada u wierzchołka v: ; przeglądamy wszystkich
     wykonuj kroki K06…K12 ; sąsiadów wierzchołka bieżącego
K06:   Jeśli u = vf, ; pomijamy ojca
       to następny obieg pętli K05
K07:   Jeśli D[u] = 0, ; sąsiad nieodwiedzony?
       to idź do kroku K10
K08:   Jeśli D[u] < Low, ; odwiedzony, krawędź wtórna.
       to Low ← D[u] ; Modyfikujemy parametr Low
K09:   Następny obieg pętli K04
K10:   temp ← DFSb(u,v,graf,T,D,dv,L) ; rekurencyjne wywołanie funkcji
K11:   Jeśli temp < Low, ; modyfikujemy parametr Low
       to Low ← temp
K12:   Jeśli temp ≥ D[v], ; robimy test na punkt artykulacji
       to test ← true
K13: Jeśli test = true, ; jeśli va jest punktem artykulacji,
     to dodaj v do L ; to dodajemy go do listy L
K14: Zakończ z wynikiem Low

Algorytm główny

Wejście:

n : liczba wierzchołków w grafie; n ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

L : lista numerów wierzchołków, które są punktami artykulacji.

Elementy pomocnicze:

dv : przechowuje numery wierzchołków dla DFS; dv ∈ C.
D : dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi.
v, u : numery wierzchołków w grafie; v, u ∈ C.
nc : liczba synów na drzewie rozpinającym dla korzenia; nc ∈ C.

Lista kroków:

K01: Twórz n elementową tablicę D
K02: Zeruj tablicę D
K03: Twórz pustą listę L
K04: Dla v = 0, 1, …, n-1: ; przechodzimy przez kolejne
     wykonuj kroki K05…K13 ; wierzchołki grafu
K05:   Jeśli D[v] > 0, ; szukamy nieodwiedzonego wierzchołka
       to następny obieg pętli K04
K06:   dv ← 2 ; początek numeracji DFS dla synów
K07:   nc ← 0 ; liczba synów na drzewie rozpinającym w głąb
K08:   D[v] ← 1 ; korzeń ma zawsze numer DFS równy 1
K09:   Dla każdego sąsiada u wierzchołka v: ; przeglądamy sąsiadów
       wykonuj kroki K10…K12
K10:     Jeśli D[u] > 0, ; szukamy nieodwiedzonego sąsiada
         to następny obieg pętli K09
K11:     nc ← nc+1 ; znaleźliśmy syna, zwiększamy licznik synów
K12:     DFSap(u,v,graf,D,dv,L) ; wywołujemy przejście DFS
K13:   Jeśli nc > 1, ; korzeń ma co najmniej dwóch synów
       to dodaj v do L ; - jest punktem artykulacji
K14: Zakończ z wynikiem L

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie punkty artykulacji i wyświetla je w oknie konsoli. Aby uprościć funkcję rekurencyjną DFSap(), większość jej parametrów została zrealizowana jako zmienne globalne.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

8 11
0 1
0 2
0 3
0 5
1 4
1 5
2 3
3 6
3 7
4 5
6 7

Pascal

// Wyszukiwanie punktów artykulacji
// w grafie nieskierowanym
// Data: 30.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------

program bridges;

// Typy dla dynamicznej tablicy
// list sąsiedztwa
// i listy punktów artykulacji
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Zmienne globalne
var
  // Liczba wierzchołków,
  // krawędzi, numeracja
  n, m, dv : integer;
  // Tablica list sąsiedztwa
  graf : TList;
  // Numery DFS
  D : array of integer;
  // Lista mostów
  L : PSLel;

// Funkcja rekurencyjna wyszukująca
// punkty artykulacji
// v - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka
//      na drzewie rozpinającym
// Reszta parametrów
// to zmienne globalne
//----------------------------------
function DFSap(v, vf : integer)
                     : integer;
var
  Low, temp, u : integer;
  test : boolean;
  p : PSLel;
begin
  // Numerujemy wierzchołek
  D[v] := dv;
  // Wstępna wartość parametru Low
  Low := dv;
  // Następny numer wierzchołka
  inc(dv);
  test := false;
  // Przeglądamy listę sąsiadów
  p := graf[v];
  while p <> nil do
  begin
    // u - numer wierzchołka
    // sąsiada
    u := p^.v;
    // u nie może być ojcem v
    if u <> vf then
    begin
      // Jeśli sąsiad u
      // nie był odwiedzany,
      // to
      if D[u] = 0 then
      begin
        // rekurencyjnie
        // odwiedzamy go
        temp := DFSap(u, v);
        if temp < Low then
          Low := temp;
        if temp >= D[v] then
          // Test na punkt
          // artykulacji
          test := true;
      end
      else if D[u] < Low then
             Low := D[u];
    end;
    // Następny wierzchołek
    // na liście
    p := p^.next;
  end;
  // Wszyscy sąsiedzi
  // zostali odwiedzeni,
  // sprawdzamy wynik testu
  if test then
  begin
    // Mamy nowy
    // punkt artykulacji
    new(p);
    p^.v := v;
    p^.next := L;
    L := p;
  end;
  // Wynik
  DFSap := Low;
end;

// **********************
// *** Program główny ***
// **********************

var
  // Numery wierzchołków,
  // licznik synów korzenia
  i, u, v, nc : integer;
  p, r : PSLel;
begin
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy zmienne
  // dynamiczne
  SetLength(graf, n);
  SetLength(D, n);
  L := nil;
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    D[i] := 0;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołki
    // tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // Dodajemy go
    // na początek
    // listy graf[v]
    p^.next := graf[v];
    graf[v] := p;
    // To samo dla krawędzi
    // w drugą stronę
    new(p);
    p^.v := v;
    p^.next := graf[u];
    graf[u] := p;
  end;
  // Szukamy
  // punktów artykulacji
  for v := 0 to n-1 do
    // Szukamy
    // nieodwiedzonego
    // wierzchołka
    if D[v] = 0 then
    begin
      // Numer DFS
      // dla pierwszego syna
      dv := 2;
      // Zerujemy licznik synów
      nc := 0;
      // Korzeń zawsze ma
      // numer DFS 1
      D[v] := 1;
      // Przeglądamy sąsiadów v
      p := graf[v];
      while p <> nil do
      begin
        // Numer wierzchołka
        // sąsiedniego
        u := p^.v;
        // Szukamy
        // nieodwiedzonego sąsiada
        if D[u] = 0 then
        begin
          // Zwiększamy
          // licznik synów
          inc(nc);
          // Szukamy punktów
          // artykulacji w grafie
          DFSap(u, v);
        end;
        p := p^.next;
      end;
      // Czy korzeń jest
      // punktem artykulacji?
      if nc > 1 then
      begin
        // Tak,
        // dodajemy go do listy
        new(p);
        p^.v := v;
        p^.next := L;
        L := p;
      end;
    end;
  writeln;
  // Wypisujemy znalezione
  // punkty artykulacji
  while L <> nil do
  begin
    write(L^.v, ' ');
    p := L;
    L := L^.next;
    dispose(p);
  end;
  writeln;
  // Usuwamy struktury dynamiczne
  SetLength(D, 0);
  for i := 0 to n-1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(graf, 0);
end.

C++

// Wyszukiwanie punktów artykulacji
// w grafie nieskierowanym
// Data: 30.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------

#include <iostream>

using namespace std;

// Typ dla dynamicznej tablicy
// list sąsiedztwa
// i listy punktów artykulacji
struct SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne
//-----------------
// Liczba wierzchołków,
// krawędzi, numeracja
int n, m, dv;
// Tablica list sąsiedztwa
SLel ** graf;
// Numery DFS
int *D;
// Lista mostów
SLel * L;

// Funkcja rekurencyjna wyszukująca
// punkty artykulacji
// v - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka
//      na drzewie rozpinającym
// Reszta parametrów to
// zmienne globalne
//----------------------------------
int DFSap(int v, int vf)
{
  int Low, temp, u;
  bool test;
  SLel * p;

  D[v] = Low = dv++;
  test = false;
  // Przeglądamy listę sąsiadów
  for(p = graf[v]; p; p = p->next)
  {
    // u - numer wierzchołka
    //     sąsiada
    u = p->v;
    // u nie może być ojcem v
    if(u != vf)
    {
      // Jeśli sąsiad u nie
      // był odwiedzany, to
      if(!D[u])
      {
        // rekurencyjnie
        // odwiedzamy go
        temp = DFSap(u, v);
        if(temp < Low)
          Low = temp;
        if(temp >= D[v])
          // Test
          // na punkt artykulacji
          test = true;
      }
      else if(D[u] < Low)
             Low = D[u];
    }
  }
  // Wszyscy sąsiedzi zostali
  // odwiedzeni, sprawdzamy
  // wynik testu
  if(test)
  {
    // Mamy nowy
    // punkt artykulacji
    p = new SLel;
    p->v = v;
    p->next = L;
    L = p;
  }
  // Wynik
  return Low;
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  // Numery wierzchołków,
  // licznik synów korzenia
  int i, u, v, nc;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy
  // zmienne dynamiczne
  graf = new SLel * [n];
  D = new int [n];
  L = nullptr;
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    D[i] = 0;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołki
    // tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    p->next = graf[v];
    graf[v] = p;
    // To samo dla krawędzi
    // w drugą stronę
    p = new SLel;
    p->v = v;
    p->next = graf[u];
    graf[u] = p;
  }
  // Szukamy
  // punktów artykulacji
  for(v = 0; v < n; v++)
    // Szukamy
    // nieodwiedzonego
    // wierzchołka
    if(!D[v])
    {
      // Numer DFS
      // dla pierwszego syna
      dv = 2;
      // Zerujemy licznik synów
      nc = 0;
      // Korzeń zawsze
      // ma numer DFS 1
      D[v] = 1;
      // Przeglądamy sąsiadów v
      for(p = graf[v];
          p;
          p = p->next)
      {
        // Numer wierzchołka
        // sąsiedniego
        u = p->v;
        // Szukamy
        // nieodwiedzonego
        // sąsiada
        if(!D[u])
        {
          // Zwiększamy
          // licznik synów
          nc++;
           // Szukamy punktów
           // artykulacji
           // w grafie
           DFSap(u, v);
        }
      }
      // Czy korzeń jest
      // punktem artykulacji?
      if(nc > 1)
      {
        // Tak, dodajemy
        // go do listy
        p = new SLel;
        p->v = v;
        p->next = L;
        L = p;
      }
    }
  cout << endl;
  // Wypisujemy znalezione
  // punkty artykulacji
  while(L)
  {
    cout << L->v << " ";
    p = L;
    L = L->next;
    delete p;
  }
  cout << endl;
  // Usuwamy struktury
  // dynamiczne
  delete [] D;
  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete graf;
  return 0;
}

Basic

' Wyszukiwanie punktów artykulacji
' w grafie nieskierowanym
' Data: 30.12.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------------

' Typ dla dynamicznej tablicy
' list sąsiedztwa
' i listy punktów artykulacji
Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne
'------------------
' Liczba wierzchołków,
' krawędzi, numeracja
Dim Shared As Integer n, m, dv
' Tablica list sąsiedztwa
Dim Shared As SLel Ptr Ptr graf
' Numery DFS
Dim Shared As Integer Ptr D
' Lista mostów
Dim Shared As SLel Ptr L

' Funkcja rekurencyjna wyszukująca
' punkty artykulacji
' v - numer bieżącego wierzchołka
' vf - ojciec bieżącego wierzchołka
'      na drzewie rozpinającym
' Reszta parametrów to zmienne
' globalne
'---------------------------------
Function DFSap(ByVal v As integer, _
               ByVal vf As Integer) _
                        As Integer
  Dim As Integer Low, temp, u, test
  Dim As SLel Ptr p

  D[v] = dv: Low = dv: dv += 1
  test = 0
  ' Przeglądamy listę sąsiadów
  p = graf[v]
  While p <> 0
    ' u - numer wierzchołka sąsiada
    u = p->v
    ' u nie może być ojcem v
    If u <> vf Then
      ' Jeśli sąsiad u
      ' nie był odwiedzany, to
      If D[u] = 0 Then
        ' rekurencyjnie
        ' odwiedzamy go
        temp = DFSap(u, v)
        If temp < Low Then _
          Low = temp
        ' Test na punkt artykulacji
        If temp >= D[v] Then _
          test = 1
      Else
        If D[u] < Low Then _
          Low = D[u]
      End If
    End If
    p = p->next
  Wend
  ' Wszyscy sąsiedzi
  ' zostali odwiedzeni,
  ' sprawdzamy wynik testu
  If test = 1 Then
    ' Mamy nowy punkt artykulacji
    p = New SLel
    p->v = v
    p->next = L
    L = p
  End If
  ' Wynik
  Return Low
End Function

' **********************
' *** Program główny ***
' **********************

' Numery wierzchołków,
' licznik synów korzenia
Dim As Integer i, u, v, nc
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Odczytujemy liczbę wierzchołków
' i krawędzi
Input #1, n, m
' Tworzymy zmienne dynamiczne
graf = New SLel Ptr [n]
D    = New Integer [n]
L    = 0
For i = 0 To n-1
  graf[i] = 0
  D[i]    = 0
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 0 To m-1
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako u
  p->v = u
  ' Dodajemy go na początek
  ' listy graf[v]
  p->next = graf[v]
  graf[v] = p
  ' To samo dla krawędzi
  ' w drugą stronę
  p = new SLel
  p->v = v
  p->next = graf[u]
  graf[u] = p
Next
Close #1
' Szukamy punktów artykulacji
For v = 0 To n-1
  ' Szukamy nieodwiedzonego
  ' wierzchołka
  If D[v] = 0 Then
    ' Numer DFS dla pierwszego syna
    dv   = 2
    ' Zerujemy licznik synów
    nc   = 0
    ' Korzeń zawsze ma numer DFS 1
    D[v] = 1
    ' Przeglądamy sąsiadów v
    p = graf[v]
    While p <> 0
      ' Numer wierzchołka sąsiedniego
      u = p->v
      ' Szukamy nieodwiedzonego
      ' sąsiada
      If D[u] = 0 Then
        ' Zwiększamy licznik synów
        nc += 1
        ' Szukamy punktów
        ' artykulacji w grafie
        DFSap(u, v)
      End If
      p = p->next
    Wend
    ' Czy korzeń jest
    ' punktem artykulacji?
    If nc > 1 Then
      ' Tak, dodajemy go do listy
      p = New SLel
      p->v = v
      p->next = L
      L = p
    End If
  End if
Next
Print
' Wypisujemy znalezione
' punkty artykulacji
While L <> 0
  print L->v;
  p = L
  L = L->next
  Delete p
Wend
Print
' Usuwamy dynamiczne
' struktury danych
For i = 0 To n-1
  p = graf[i]
  While p <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] D
Delete [] graf
End

Python (dodatek)

# Wyszukiwanie punktów artykulacji
# w grafie nieskierowanym
# Data: 16.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------------

# Klasa dla dynamicznej tablicy
# list sąsiedztwa
# i listy punktów artykulacji
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Funkcja rekurencyjna wyszukująca
# punkty artykulacji
# v - numer bieżącego wierzchołka
# vf - ojciec bieżącego wierzchołka
#            na drzewie rozpinającym
# Reszta parametrów to zmienne
# globalne
#---------------------------------
def dfs_ap(v, vf):
    global d, dv, graf, lst
    d[v] = dv
    low = dv
    dv += 1
    test = False
    # Przeglądamy listę sąsiadów
    p = graf[v]
    while p:
        # u - numer wierzchołka sąsiada
        u = p.v
        # u nie może być ojcem v
        if u != vf:
            # Jeśli sąsiad u
            # nie był odwiedzany, to
            if not d[u]:
                # rekurencyjnie
                # odwiedzamy go
                temp = dfs_ap(u, v)
                if temp < low:
                    low = temp
                # Test na punkt artykulacji
                if temp >= d[v]:
                    test = True
            else:
                if d[u] < low:
                    low = d[u]
        p = p.next
    # Wszyscy sąsiedzi
    # zostali odwiedzeni,
    # sprawdzamy wynik testu
    if test:
        # Mamy nowy punkt artykulacji
        p = SLel()
        p.v = v
        p.next = lst
        lst = p
    # Wynik
    return low


# **********************
# *** Program główny ***
# **********************

# Odczytujemy liczbę wierzchołków
# i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy zmienne dynamiczne
graf = [None] * n
d = [0] * n
lst = None
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako u
    p.v = u
    # Dodajemy go na początek
    # listy graf[v]
    p.next = graf[v]
    graf[v] = p
    # To samo dla krawędzi
    # w drugą stronę
    p = SLel()
    p.v = v
    p.next = graf[u]
    graf[u] = p
# Szukamy punktów artykulacji
for v in range(n):
    # Szukamy nieodwiedzonego
    # wierzchołka
    if not d[v]:
        # Numer DFS dla pierwszego syna
        dv = 2
        # Zerujemy licznik synów
        nc = 0
        # Korzeń zawsze ma numer DFS 1
        d[v] = 1
        # Przeglądamy sąsiadów v
        p = graf[v]
        while p:
            # Numer wierzchołka sąsiedniego
            u = p.v
            # Szukamy nieodwiedzonego
            # sąsiada
            if not d[u]:
                # Zwiększamy licznik synów
                nc += 1
                # Szukamy punktów
                # artykulacji w grafie
                dfs_ap(u, v)
            p = p.next
        # Czy korzeń jest
        # punktem artykulacji?
        if nc > 1:
            # Tak, dodajemy go do listy
            p = SLel()
            p.v = v
            p.next = lst
            lst = p
print()
# Wypisujemy znalezione
# punkty artykulacji
while lst:
    print(lst.v, end=" ")
    lst = lst.next
print()
# Usuwamy dynamiczne
# struktury danych
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del d, graf

Wynik:
8 11 0 1 0 2 0 3 0 5 1 4 1 5 2 3 3 6 3 7 4 5 6 7 0 3

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Znajdowanie punktów artykulacji w grafie

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania punktów artykulacji w grafie nieskierowanym

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm Tarjana wyszukiwania punktów artykulacji w grafie nieskierowanym

Funkcja rekurencyjna DFSap(v,vf,graf,D,dv,L)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm główny

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy