Algorytmy i Struktury Danych - Badanie spójności grafu

Badanie spójności grafu nieskierowanego wykonuje się następująco.

Tworzymy licznik odwiedzonych wierzchołków i ustawiamy go na zero. Następnie uruchamiamy przejście DFS od dowolnie wybranego wierzchołka. W każdym odwiedzonym wierzchołku zwiększamy nasz licznik. Gdy przejście DFS się zakończy, w liczniku będzie liczba wszystkich odwiedzonych wierzchołków. Jeśli liczba ta będzie równa liczbie wierzchołków grafu, to graf jest spójny. Inaczej nie jest spójny.

Algorytm badania spójności grafu nieskierowanego

Wejście:

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

Wyjście:

true : graf jest spójny
false : graf nie jest spójny

Elementy pomocnicze:

vs : n elementowa tablica logiczna odwiedzin wierzchołków.
vc : licznik odwiedzonych wierzchołków; vc ∈ C.
S : stos wierzchołków.
v, u : numery wierzchołków w grafie; v, u ∈ C.

Lista kroków:

K01: Utwórz tablicę vs o n elementach
K02: Tablicę vs wypełnij wartościami false
K03: Utwórz pusty stos S
K04: vc ← 0 ; inicjujemy licznik odwiedzonych wierzchołków
K05: S.push(0) ; przejście DFS rozpoczniemy od wierzchołka 0
K06: vs[0] ← true ; wierzchołek oznaczamy jako odwiedzony
K07: Dopóki S.empty() = false, ; przechodzimy przez graf
     wykonuj kroki K08…K14
K08:   v ← S.top() ; pobieramy wierzchołek ze stosu
K09:   S.pop() ; pobrany wierzchołek usuwamy ze stosu
K10:   vc ← vc+1 ; zwiększamy licznik odwiedzonych wierzchołków
K11:   Dla każdego sąsiada u wierzchołka v, ; przeglądamy
       wykonuj kroki K12...K14 ; kolejnych sąsiadów
K12:     Jeśli vs[u] = true, ; szukamy sąsiadów
         to następny obieg pętli K11 ; jeszcze nieodwiedzonych
K13:     vs[u] ← true ; oznaczamy sąsiada jako odwiedzonego
K14:     S.push(u) ; i umieszczamy go na stosie
K15: Jeśli vc = n, ; wszystkie wierzchołki odwiedzone,
     to zakończ z wynikiem true ; graf jest spójny
K16: Zakończ z wynikiem false ; graf nie jest spójny

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 i bada, czy jest grafem spójnym. Jeśli tak, to wypisuje 'CONNECTED GRAPH', inaczej wypisuje 'DISCONNECTED GRAPH'.

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

Graf spójny
obrazek

Graf niespójny
obrazek

Pascal

// Badanie spójności grafu
// Data: 6.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program conngraph;

// Typy dla dynamicznej tablicy
// list sąsiedztwa oraz stosu
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 empty then
    top := -1
  else
    top := S^.v;
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;

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

var
  // Liczba wierzchołków i krawędzi
  n, m : integer;
  // Tablica list sąsiedztwa grafu
  A : TList;
  // Tablica odwiedzin
  vs : array of boolean;
  // Stos
  S : Stack;
  i, v, u, vc : integer;
  p, r : PSLel;

begin
  S.init;
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  SetLength(vs, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    vs[i] := false;
  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 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;
  // Badamy spójność grafu
  // ---------------------
  // Zerujemy licznik wierzchołków
  vc := 0;
  // Wierzchołek startowy na stos
  S.push(0);
  // Oznaczamy go jako odwiedzony
  vs[0] := true;
  // Wykonujemy przejście DFS
  while not S.empty do
  begin
    // Pobieramy wierzchołek
    // ze stosu
    v := S.top;
    // Pobrany wierzchołek
    // usuwamy ze stosu
    S.pop;
    // Zwiększamy licznik
    // wierzchołków
    inc(vc);
    // Przeglądamy sąsiadów
    p := A[v];
    while p <> nil do
    begin
      u := p^.v;
      // Szukamy wierzchołki
      // nieodwiedzone
      if not vs[u] then
      begin
        // Oznaczamy wierzchołek
        // jako odwiedzony
        vs[u] := true;
        // i umieszczamy go na stosie
        S.push(u);
      end;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  // Wyświetlamy wyniki
  writeln;
  if vc = n then
    writeln('CONNECTED GRAPH')
  else
    writeln('DISCONNECTED GRAPH');
  // Usuwamy tablice 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(vs, 0);
  S.destroy;
end.

C++

// Badanie spójności grafu
// Data: 6.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy
// list sąsiedztwa i stosu
struct SLel
{
  SLel * next;
  int v;
};

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

  public:
    // konstruktor
    Stack();
    // destruktor
    ~Stack();
    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(empty())
    return -1;
  else
    return S->v;
}

// 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;
  }
}

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

int main()
{
  // Liczba wierzchołków
  // i krawędzi
  int n, m;
  // Tablica list
  // sąsiedztwa grafu
  SLel ** A;
  // Tablica odwiedzin
  bool * vs;
  // Stos
  Stack S;
  int i, v, u, vc;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  A = new SLel * [n];
  vs = new bool [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
  {
    A[i] = nullptr;
    vs[i] = false;
  }
  // 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;
    // 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;
  }
  // Badamy spójność grafu
  // ---------------------
  // Zerujemy licznik wierzchołków
  vc = 0;
  // Wierzchołek startowy na stos
  S.push(0);
  // Oznaczamy go jako odwiedzony
  vs[0] = true;
  // Wykonujemy przejście DFS
  while(!S.empty())
  {
    // Pobieramy wierzchołek
    // ze stosu
    v = S.top();
    // Pobrany wierzchołek
    // usuwamy ze stosu
    S.pop();
    // Zwiększamy licznik
    // wierzchołków
    vc++;
    // Przeglądamy sąsiadów
    for(p = A[v]; p; p = p->next)
    {
      u = p->v;
      // Szukamy wierzchołków
      // nieodwiedzonych
      if(!vs[u])
      {
        // Oznaczamy wierzchołek
        // jako odwiedzony
        vs[u] = true;
        // i umieszczamy go na stosie
        S.push(u);
      }
    }
  }
  // Wyświetlamy wyniki
  cout << endl;
  if(vc == n)
    cout << "CONNECTED GRAPH";
  else
    cout << "DISCONNECTED GRAPH";
  cout << endl;
  // Usuwamy tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] vs;
  return 0;
}

Basic

' Badanie spójności grafu
' Data: 6.01.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa i stosu

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 empty Then
    top = -1
  Else
    top = S->v
  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

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

' Liczba wierzchołków i krawędzi
Dim As Integer n, m
' Tablica list sąsiedztwa grafu
Dim As SLel Ptr Ptr A
' Tablica odwiedzin
Dim As Byte Ptr vs
' Stos
Dim As Stack S
Dim As Integer i, v, u, vc
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 tablice dynamiczne
A = New SLel Ptr [n]
vs = New Byte [n]
' Inicjujemy tablice
For i = 0 To n-1
  A[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 1 To m
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' 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ę
  p = New SLel
  p->v = v
  p->next = A[u]
  A[u] = p
Next
Close #1
' Badamy spójność grafu
'----------------------
' Zerujemy licznik wierzchołków
vc = 0
' Wierzchołek startowy na stos
S.push(0)
' Oznaczamy go jako odwiedzony
vs[0] = 1
' Wykonujemy przejście DFS
While S.empty = 0
  ' Pobieramy wierzchołek ze stosu
  v = S.top
  ' Pobrany wierzchołek usuwamy ze stosu
  S.pop
  ' Zwiększamy licznik wierzchołków
  vc += 1
  p = A[v]
  ' Przeglądamy sąsiadów
  While p
    u = p->v
    ' Szukamy wierzchołków
    ' nieodwiedzonych
    If vs[u] = 0 Then
      ' Oznaczamy wierzchołek
      ' jako odwiedzony
      vs[u] = 1
      ' i umieszczamy go na stosie
      S.push(u)
    End If
    p = p->next
  Wend
Wend
' Wyświetlamy wyniki
Print
If vc = n Then
  Print "CONNECTED GRAPH"
Else
  Print "DISCONNECTED GRAPH"
End If
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Delete [] vs
End

Python (dodatek)

# Badanie spójności grafu
# Data: 29.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasy dla dynamicznej tablicy
# list sąsiedztwa i stosu
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.empty():
            return -1
        else:
            return self.s.v


    # 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 s:
            self.s = self.s.next


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

# Stos
s = Stack()
# 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
vs = [False] * 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
# Badamy spójność grafu
#----------------------
# Zerujemy licznik wierzchołków
vc = 0
# Wierzchołek startowy na stos
s.push(0)
# Oznaczamy go jako odwiedzony
vs[0] = True
# Wykonujemy przejście DFS
while not s.empty():
    # Pobieramy wierzchołek ze stosu
    v = s.top()
    # Pobrany wierzchołek
    # usuwamy ze stosu
    s.pop()
    # Zwiększamy licznik
    # wierzchołków
    vc += 1
    p = a[v]
    # Przeglądamy sąsiadów
    while p:
        u = p.v
        # Szukamy wierzchołków
        # nieodwiedzonych
        if not vs[u]:
            # Oznaczamy wierzchołek
            # jako odwiedzony
            vs[u] = True
            # i umieszczamy go na stosie
            s.push(u)
        p = p.next
# Wyświetlamy wyniki
print()
if vc == n:
    print("CONNECTED GRAPH")
else:
    print("DISCONNECTED GRAPH")
# Usuwamy tablice dynamiczne
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vs

Wynik:

17 28
0 1
0 2
0 3
1 2
1 5
1 9
1 14 
2 5
2 6
3 4
3 6
4 12
4 13
5 6
5 8
5 9
6 7
6 8
6 12
7 13
8 9
8 10
10 14
10 15
11 16
12 16
13 16
14 15

CONNECTED GRAPH

17 26
0 1
0 2
0 3
1 2
1 5
1 9
2 5
2 6
3 4
3 6
4 12
4 13
5 6
5 8
5 9
6 7
6 8
6 12
7 13
8 9
10 14
10 15
11 16
12 16
13 16
14 15

DISCONNECTED GRAPH

do podrozdziału do strony

Graf skierowany jest spójny, jeśli po zastąpieniu wszystkich jego krawędzi skierowanych krawędziami nieskierowanymi, otrzymamy nieskierowany graf spójny. Zatem badanie spójności grafu skierowanego będzie składało się z dwóch kroków:

Na podstawie grafu skierowanego budujemy graf nieskierowany.
Badamy spójność skonstruowanego grafu nieskierowanego za pomocą opisanego wcześniej algorytmu.

Graf nieskierowany możemy zbudować w osobnej strukturze danych lub w strukturze grafu skierowanym, jeśli nie będziemy go później potrzebować w postaci pierwotnej.

W pierwszym przypadku po prostu tworzymy nową strukturę grafu, następnie przeglądamy sąsiadów każdego wierzchołka grafu skierowanego i znalezione krawędzie umieszczamy w nowej strukturze, tak aby prowadziły w obu kierunkach – jeśli w grafie skierowanym jest krawędź u→v, to w nowej strukturze umieszczamy dwie krawędzie:u→v oraz v→u. Dzięki temu powstaną krawędzie nieskierowane, po których można przejść w obu kierunkach.

Algorytm budowania grafu podstawowego z grafu nieskierowanego

Wejście:

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

Wyjście:

T : n elementowa tablica list sąsiedztwa, która zawiera graf podstawowy.

Elementy pomocnicze:

v, u : wierzchołki; v, u ∈ C.

Lista kroków:

K01: Utwórz n elementową tablicę T
K02: Dla v = 0, 1, …, n-1: ; tablicę T wypełniamy
     wykonuj: T[v] ← nil ; pustymi listami
K03: Dla v = 0, 1, …, n-1: ; przechodzimy przez
     wykonuj kroki K04…K06 ; kolejne wierzchołki grafu
K04:   Dla każdego sąsiada u wierzchołka v: ; przeglądamy
       wykonuj kroki K05…K06 ; sąsiadów bieżącego wierzchołka
K05:   Dodaj u do listy T[v] ; tworzymy w T krawędź nieskierowaną
K06:   Dodaj v do listy T[u]
K07: Zakończ

W drugim przypadku przechodzimy w pętli przez kolejne wierzchołki grafu od wierzchołka 0 do n-1. W każdym wierzchołku przeglądamy listę sąsiadów. Sąsiada i wierzchołek bieżący umieszczamy na stosie. Gdy przeglądniemy cały graf, stos będzie zawierał informację o wszystkich krawędziach. Teraz należy pobierać ze stosu po dwa wierzchołki i dodawać do grafu odwrotne krawędzie. Gdy wyczerpiemy stos, graf będzie zawierał tylko krawędzie nieskierowane.

Algorytm budowania grafu podstawowego 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:

graf : zawiera graf podstawowy.

Elementy pomocnicze:

v, u : wierzchołki; v, u ∈ C.
S : pusty stos wierzchołków.

Lista kroków:

K01: Dla v = 0, 1, …, n-2: ; przechodzimy przez wierzchołki grafu
     wykonuj kroki K02…K03 ; od pierwszego do przedostatniego
K02:   Dla każdego sąsiada u wierzchołka v: ; przeglądamy sąsiadów
       wykonuj krok K03                     ; bieżącego wierzchołka
K03:   S.push(v); S.push(u); ; zapamiętujemy krawędź
                             ; v→u na stosie
K04: Dopóki S.empty() = false, 
     wykonuj kroki K05…K07
K05:   u ← S.top(); S.pop() ; pobieramy ze stosu krawędź
K06:   v ← S.top(); S.pop()
K07:   Dodaj krawędź u→v do grafu
K08: Zakończ

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 skierowanego, buduje w nim graf podstawowy i bada, czy jest grafem spójnym. Jeśli tak, to wypisuje 'CONNECTED GRAPH', inaczej wypisuje 'DISCONNECTED GRAPH'.

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

Skierowany graf spójny
obrazek

17 28
0 3
1 0
2 0
2 1
4 3
4 12
5 1
5 2
5 6
5 9
6 2
6 3
6 8
7 6
8 5
9 1
9 8
9 10
10 15
11 10
11 16
12 6
12 16
13 4
13 7
14 10
15 14
16 13

Skierowany graf niespójny
obrazek

17 24
0 3
1 0
2 0
2 1
4 12
5 1
5 2
5 6
5 9
6 2
6 3
6 8
7 6
8 5
9 1
9 8
10 15
11 10
11 16
12 16
13 4
14 10
15 14
16 13

Pascal

// Badanie spójności grafu skierowanego
// Data: 9.01.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------

program spojgraf;

// Typy dla dynamicznej tablicy
// list sąsiedztwa oraz stosu
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 empty then
    top := -1
  else
    top := S^.v;
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;

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

var
  // Liczba wierzchołków
  // i krawędzi
  n, m : integer;
  // Tablica list
  // sąsiedztwa grafu
  A : TList;
  // Tablica odwiedzin
  vs : array of boolean;
  // Stos
  S : Stack;
  i, v, u, vc : integer;
  p, r : PSLel;

begin
  S.init;
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(A, n);
  SetLength(vs, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    vs[i] := false;
  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 A[v]
    p^.next := A[v];
    A[v] := p;
  end;
  // Tworzymy graf podstawowy
  for v := 0 to n-1 do
  begin
    p := A[v];
    // Przeglądamy sąsiadów
    while p <> nil do
    begin
      S.push(v);
      // Krawędź v-u na stos
      S.push(p^.v);
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  while not S.empty do
  begin
    // Pobieramy zapamiętane
    // wierzchołki
    u := S.top; S.pop;
    v := S.top; S.pop;
    // Do grafu dodajemy
    // krawędź odwrotną
    new(p);
    p^.v := v;
    p^.next := A[u];
    A[u] := p;
  end;
  // Badamy spójność
  // grafu podstawowego
  //-------------------
  // Zerujemy licznik
  // wierzchołków
  vc := 0;
  // Wierzchołek startowy
  // na stos
  S.push(0);
  // Oznaczamy go
  // jako odwiedzony
  vs[0] := true;
  // Wykonujemy przejście DFS
  while not S.empty do
  begin
    // Pobieramy wierzchołek
    // ze stosu
    v := S.top;
    // Pobrany wierzchołek
    // usuwamy ze stosu
    S.pop;
    // Zwiększamy licznik
    // wierzchołków
    inc(vc);
    // Przeglądamy sąsiadów
    p := A[v];
    while p <> nil do
    begin
      u := p^.v;
      // Szukamy wierzchołków
      // nieodwiedzonych
      if not vs[u] then
      begin
        // Oznaczamy wierzchołek
        // jako odwiedzony
        vs[u] := true;
        // i umieszczamy go
        // na stosie
        S.push(u);
      end;
      // Następny sąsiad
      p := p^.next;
    end;
  end;
  // Wyświetlamy wyniki
  writeln;
  if vc = n then
    writeln('CONNECTED GRAPH')
  else
    writeln('DISCONNECTED GRAPH');
  // Usuwamy tablice 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(vs, 0);
  S.destroy;
end.

C++

// Badanie spójności grafu skierowanego
// Data: 9.01.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy
// list sąsiedztwa i stosu
struct SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;
  public:
    Stack();
    ~Stack();
    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(empty())
    return -1;
  else
    return S->v;
}

// 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;
  }
}

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

int main()
{
  // Liczba wierzchołków
  // i krawędzi
  int n, m;
  // Tablica list
  // sąsiedztwa grafu
  SLel ** A;
  // Tablica odwiedzin
  bool * vs;
  // Stos
  Stack S;
  int i, v, u, vc;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  A = new SLel * [n];
  vs = new bool [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
  {
    A[i] = NULL;
    vs[i] = false;
  }
  // 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 w
    p->v = u;
    // Dodajemy go na
    // początek listy A[v]
    p->next = A[v];
    A[v] = p;
 }
  // Tworzymy graf podstawowy
  for(v = 0; v < n; v++)
  {
    // Przeglądamy sąsiadów
    for(p = A[v]; p; p = p->next)
    {
      // Krawędź v-u na stos
      S.push(v);
      S.push(p->v);
    }
  }
  while(!S.empty())
  {
    // Pobieramy zapamiętane
    // wierzchołki
    u = S.top(); S.pop();
    v = S.top(); S.pop();
    // Do grafu dodajemy
    // krawędź odwrotną
    p = new SLel;
    p->v = v;
    p->next = A[u];
    A[u] = p;
  }
  // Badamy spójność
  // grafu podstawowego
  //-------------------
  // Zerujemy licznik
  // wierzchołków
  vc = 0;
  // Wierzchołek startowy
  // na stos
  S.push(0);
  // Oznaczamy go
  // jako odwiedzony
  vs[0] = true;
  // Wykonujemy przejście DFS
  while(!S.empty())
  {
    // Pobieramy wierzchołek
    // ze stosu
    v = S.top();
    // Pobrany wierzchołek
    // usuwamy ze stosu
    S.pop();
    // Zwiększamy licznik
    // wierzchołków
    vc++;
    // Przeglądamy sąsiadów
    for(p = A[v]; p; p = p->next)
    {
      u = p->v;
      // Szukamy wierzchołków
      // nieodwiedzonych
      if(!vs[u])
      {
        // Oznaczamy wierzchołek
        // jako odwiedzony
        vs[u] = true;
        // i umieszczamy go
        // na stosie
        S.push(u);
      }
    }
  }
  // Wyświetlamy wyniki
  cout << endl;
  if(vc == n)
    cout << "CONNECTED GRAPH";
  else
    cout << "DISCONNECTED GRAPH";
  cout << endl;
  // Usuwamy tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  delete [] vs;
  return 0;
}

Basic

' Badanie spójności grafu skierowanego
' Data: 9.01.2014
' (C)2014 mgr Jerzy Wałaszek
'-------------------------------------

' Typy dla dynamicznej tablicy
' list sąsiedztwa i stosu
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 empty Then
    top = -1
  Else
    top = S->v
  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

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

' Liczba wierzchołków
' i krawędzi
Dim As Integer n, m
' Tablica list sąsiedztwa grafu
Dim As SLel Ptr Ptr A
' Tablica odwiedzin
Dim As Byte Ptr vs
' Stos
Dim As Stack S
Dim As Integer i, v, u, vc
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 tablice dynamiczne
A = New SLel Ptr [n]
vs = New Byte [n]
' Inicjujemy tablice
For i = 0 To n-1
  A[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne
' definicje krawędzi.
For i = 1 To m
  ' 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
Next
Close #1
' Tworzymy graf podstawowy
For v = 0 To n-1
  p = A[v]
  ' Przeglądamy sąsiadów
  While p
    S.push(v)
    ' Krawędź v-u na stos
    S.push(p->v)
    ' Następny sąsiad
    p = p->next
  Wend
Next
While S.empty = 0
  ' Pobieramy zapamiętane wierzchołki
  u = S.top: S.pop
  v = S.top: S.pop
  ' Do grafu dodajemy krawędź odwrotną
  p = new SLel
  p->v = v
  p->next = A[u]
  A[u] = p
Wend
' Badamy spójność grafu podstawowego
' ----------------------------------
' Zerujemy licznik wierzchołków
vc = 0
' Wierzchołek startowy na stos
S.push(0)
' Oznaczamy go jako odwiedzony
vs[0] = 1
' Wykonujemy przejście DFS
While S.empty = 0
  ' Pobieramy wierzchołek ze stosu
  v = S.top
  ' Pobrany wierzchołek usuwamy ze stosu
  S.pop
  ' Zwiększamy licznik wierzchołków
  vc += 1
  p = A[v]
  ' Przeglądamy sąsiadów
  While p
    u = p->v
    ' Szukamy wierzchołków nieodwiedzonych
    If vs[u] = 0 Then
      ' Oznaczamy wierzchołek
      ' jako odwiedzony
      vs[u] = 1
      ' i umieszczamy go na stosie
      S.push(u)
    End If
    p = p->Next
  Wend
Wend
' Wyświetlamy wyniki
Print
If vc = n Then
  Print "CONNECTED GRAPH"
Else
  Print "DISCONNECTED GRAPH"
End If
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Delete [] vs
End

Python (dodatek)

# Badanie spójności grafu skierowanego
# Data: 30.12.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------------

# Klasy
#------

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.empty():
            return -1
        else:
            return self.s.v


    # 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


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

# Stos
s = Stack()
# 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
vs = [False] * 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
# Tworzymy graf podstawowy
for v in range(n):
    p = a[v]
    # Przeglądamy sąsiadów
    while p:
        # Krawędź v-u na stos
        s.push(v)
        s.push(p.v)
        # Następny sąsiad
        p = p.next
while not s.empty():
    # Pobieramy zapamiętane wierzchołki
    u = s.top()
    s.pop()
    v = s.top()
    s.pop()
    # Do grafu dodajemy krawędź odwrotną
    p = SLel()
    p.v = v
    p.next = a[u]
    a[u] = p
# Badamy spójność grafu podstawowego
# ----------------------------------
# Zerujemy licznik wierzchołków
vc = 0
# Wierzchołek startowy na stos
s.push(0)
# Oznaczamy go jako odwiedzony
vs[0] = 1
# Wykonujemy przejście DFS
while not s.empty():
    # Pobieramy wierzchołek ze stosu
    v = s.top()
    # Pobrany wierzchołek usuwamy ze stosu
    s.pop()
    # Zwiększamy licznik wierzchołków
    vc += 1
    p = a[v]
    # Przeglądamy sąsiadów
    while p:
        u = p.v
        # Szukamy wierzchołków nieodwiedzonych
        if not vs[u]:
            # Oznaczamy wierzchołek
            # jako odwiedzony
            vs[u] = True
            # i umieszczamy go na stosie
            s.push(u)
        p = p.next
# Wyświetlamy wyniki
print()
if vc == n:
    print("CONNECTED GRAPH")
else:
    print("DISCONNECTED GRAPH")
# Usuwamy tablice dynamiczne
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vs

Wynik:

17 28
0 3
1 0
2 0
2 1
4 3
4 12
5 1
5 2
5 6
5 9 
6 2
6 3
6 8
7 6
8 5
9 1
9 8
9 10
10 15
11 10
11 16
12 6
12 16
13 4
13 7
14 10
15 14
16 13

CONNECTED GRAPH

17 24
0 3
1 0
2 0
2 1
4 12
5 1
5 2
5 6
5 9
6 2
6 3
6 8
7 6
8 5
9 1
9 8
10 15
11 10
11 16
12 16
13 4
14 10
15 14
16 13

DISCONNECTED GRAPH

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.

Spójność grafu

Problem

Rozwiązanie dla grafu nieskierowanego

Algorytm badania spójności grafu nieskierowanego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla grafu skierowanego

Algorytm budowania grafu podstawowego z grafu nieskierowanego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm budowania grafu podstawowego w grafie nieskierowanym

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy