Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Spójność grafu

SPIS TREŚCI
Podrozdziały

Problem

Należy zbadać, czy dany graf jest spójny.

Graf jest spójny ( ang. connected graph ), jeśli dla każdych dwóch jego wierzchołków istnieje ścieżka, które je ze sobą łączy. W przeciwnym razie graf jest niespójny ( ang. disconnected graph ). Spójność grafu ( ang. graph connectivity ) określa, czy jest on spójny, czy nie.

Rozwiązanie dla grafu nieskierowanego

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
Zmienne pomocnicze:
visited  –  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ę visited
o n  elementach
 
K02: Tablicę visited  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: visited [ 0 ] ← true wierzchołek oznaczamy jako odwiedzony
K07: Dopóki S.empty( ) = false,
wykonuj kroki K08...K14
przechodzimy przez graf
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,
   
wykonuj kroki K12..K14.
przeglądamy kolejnych sąsiadów
K12:         Jeśli visited [ u  ] = true,
        to następny obieg pętli K11
szukamy sąsiadów jeszcze nieodwiedzonych
K13:         visited [ u  ] ← true oznaczamy sąsiada jako odwiedzonego
K14:         S.push ( u  ) i umieszczamy go na stosie
K15: Jeśli vc  = n,
to zakończ z wynikiem true
wszystkie wierzchołki odwiedzone, 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

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
     Graf niespójny

obrazek

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
Pascal
// Badanie spójności grafu
// Data: 6.01.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program spojsklad;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

  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
  top := S^.v;
end;

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

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

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

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

begin
  S.init;

  read ( n, m );           // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength ( A, n );      // Tworzymy tablice dynamiczne
  SetLength ( visited, n );

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    A [ i ] := nil;
    visited [ i ] := false;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read ( v, u );         // Wierzchołki tworzące krawędź
    new ( p );             // Tworzymy nowy element
    p^.v := u;             // Numerujemy go jako w
    p^.next := A [ v ];    // Dodajemy go na początek listy A [ v ] 
    A [ v ] := p;
    new ( p );             // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := A [ u ];
    A [ u ] := p;
  end;

  // Badamy spójność grafu

  vc := 0;                 // Zerujemy licznik wierzchołków

  S.push ( 0 );            // Wierzchołek startowy na stos
  visited [ 0 ] := true;   // Oznaczamy go jako odwiedzony

  while not S.empty do     // Wykonujemy przejście DFS
  begin
    v := S.top;            // Pobieramy wierzchołek ze stosu
    S.pop;                 // Pobrany wierzchołek usuwamy ze stosu
    inc ( vc );            // Zwiększamy licznik wierzchołków
    p := A [ v ];          // Przeglądamy sąsiadów
    while p <> nil do
    begin
      u := p^.v;
      if not visited [ u ] then // Szukamy wierzchołków nieodwiedzonych
      begin
        visited [ u ] := true; // Oznaczamy wierzchołek jako odwiedzony
        S.push ( u );      // i umieszczamy go na stosie
      end;
      p := p^.next;        // Następny sąsiad
    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 ( visited, 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 slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  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 = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack( )
{
  while( S ) pop( );
}

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

// Zwraca szczyt stosu
//--------------------
int stack::top ( void )
{
  return S->v;
}

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

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

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

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

  cin >> n >> m;           // Odczytujemy liczbę wierzchołków i krawędzi

  A = new slistEl * [ n ]; // Tworzymy tablice dynamiczne
  visited = new bool [ n ];

  // Inicjujemy tablice

  for( i = 0; i < n; i++ )
  {
    A [ i ] = NULL;
    visited [ i ] = false;
  }

  // Odczytujemy kolejne definicje krawędzi.

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;      // Wierzchołki tworzące krawędź
    p = new slistEl;    // Tworzymy nowy element
    p->v = u;           // Numerujemy go jako w
    p->next = A [ v ];  // Dodajemy go na początek listy A [ v ] 
    A [ v ] = p;
    p = new slistEl;    // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = A [ u ];
    A [ u ] = p;
  }

  // Badamy spójność grafu

  vc = 0;               // Zerujemy licznik wierzchołków

  S.push ( 0 );         // Wierzchołek startowy na stos
  visited [ 0 ] = true; // Oznaczamy go jako odwiedzony

  while( !S.empty( ) )  // Wykonujemy przejście DFS
  {
    v = S.top( );       // Pobieramy wierzchołek ze stosu
    S.pop( );           // Pobrany wierzchołek usuwamy ze stosu
    vc++;               // Zwiększamy licznik wierzchołków
    for( p = A [ v ]; p; p = p->next ) // Przeglądamy sąsiadów
    {
      u = p->v;
      if( !visited [ u ] )    // Szukamy wierzchołków nieodwiedzonych
      {
        visited [ u ] = true; // Oznaczamy wierzchołek jako odwiedzony
        S.push ( u );         // i umieszczamy go na stosie
      }
    }
  }

  // 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 [ ] visited;

  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 slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  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
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push ( ByVal v As Integer )
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop( )
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

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

Dim As Integer n, m       ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A  ' Tablica list sąsiedztwa grafu
Dim As Byte Ptr visited   ' Tablica odwiedzin
Dim As stack S            ' Stos
Dim As Integer i, v, u, vc
Dim As slistEl Ptr p, r

Open Cons For Input As #1

Input #1, n, m            ' Odczytujemy liczbę wierzchołków i krawędzi

A = New slistEl Ptr [ n ] ' Tworzymy tablice dynamiczne
visited = New Byte [ n ] 

' Inicjujemy tablice

For i = 0 To n - 1
  A [ i ] = 0
  visited [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1, v, u        ' Wierzchołki tworzące krawędź
  p = New slistEl       ' Tworzymy nowy element
  p->v = u              ' Numerujemy go jako w
  p->next = A [ v ]     ' Dodajemy go na początek listy A [ v ] 
  A [ v ] = p
  p = New slistEl       ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = A [ u ] 
  A [ u ] = p
Next

Close #1

' Badamy spójność grafu

vc = 0                  ' Zerujemy licznik wierzchołków

S.push ( 0 )            ' Wierzchołek startowy na stos
visited [ 0 ] = 1       ' Oznaczamy go jako odwiedzony

While S.empty( ) = 0    ' Wykonujemy przejście DFS
  v = S.top( )          ' Pobieramy wierzchołek ze stosu
  S.pop( )              ' Pobrany wierzchołek usuwamy ze stosu
  vc += 1               ' Zwiększamy licznik wierzchołków
  p = A [ v ] 
  While p               ' Przeglądamy sąsiadów
    u = p->v
    If visited [ u ] = 0 Then ' Szukamy wierzchołków nieodwiedzonych
      visited [ u ] = 1 ' Oznaczamy wierzchołek jako odwiedzony
      S.push ( u )      ' i umieszczamy go na stosie
    End If
    p = p->Next
  Wend
Wend

' Wyświetlamy wyniki

Print

If vc = n Then Print "CONNECTED GRAPH": Else Print "DISCONNECTED GRAPH"

' 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 [ ] visited

End
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
Na początek:  podrozdziału   strony 

Rozwiązanie dla grafu skierowanego

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:

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

Graf nieskierowany możemy zbudować w osobnej strukturze danych lub w grafie 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.
Zmienne 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:
wykonuj
: T [ v  ] ← nil
tablicę T wypełniamy pustymi listami
K03: Dla v  = 0, 1, ..., n - 1:
wykonuj
kroki K04...K06
przechodzimy przez kolejne wierzchołki grafu
K04:     Dla każdego sąsiada u  wierzchołka v :
    wykonuj kroki K05...K06
przeglądamy 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.
Zmienne pomocnicze:
v, u  –  wierzchołki, v, u ∈ C.
S  –  pusty stos wierzchołków.

Lista kroków:

K01: Dla v  = 0, 1, ..., n - 2:
wykonuj kroki K02...K03
przechodzimy przez wierzchołki grafu od pierwszego do przedostatniego
K02:     Dla każdego sąsiada u  wierzchołka v :
    wykonuj krok K03
przeglądamy sąsiadów 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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

  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
  top := S^.v;
end;

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

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

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

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

begin
  S.init;

  read ( n, m );       // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength ( A, n );  // Tworzymy tablice dynamiczne
  SetLength ( visited, n );

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    A [ i ] := nil;
    visited [ i ] := false;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read ( v, u );      // Wierzchołki tworzące krawędź
    new ( p );          // Tworzymy nowy element
    p^.v := u;          // Numerujemy go jako w
    p^.next := A [ v ]; // Dodajemy go na początek listy A [ v ] 
    A [ v ] := p;
  end;

  // Tworzymy graf podstawowy

  for v := 0 to n - 1 do
  begin
    p := A [ v ];
    while p <> nil do  // Przeglądamy sąsiadów
    begin
      S.push ( v );
      S.push ( p^.v ); // Krawędź v-u na stos
      p := p^.next;    // Następny sąsiad
    end;
  end;

  while not S.empty do
  begin
    u := S.top; S.pop;
    v := S.top; S.pop; // Pobieramy zapamiętane wierzchołki
    new ( p );         // Do grafu dodajemy krawędź odwrotną
    p^.v := v;
    p^.next := A [ u ];
    A [ u ] := p;
  end;

  // Badamy spójność grafu podstawowego

  vc := 0;             // Zerujemy licznik wierzchołków

  S.push ( 0 );        // Wierzchołek startowy na stos
  visited [ 0 ] := true; // Oznaczamy go jako odwiedzony

  while not S.empty do // Wykonujemy przejście DFS
  begin
    v := S.top;        // Pobieramy wierzchołek ze stosu
    S.pop;             // Pobrany wierzchołek usuwamy ze stosu
    inc ( vc );        // Zwiększamy licznik wierzchołków
    p := A [ v ];      // Przeglądamy sąsiadów
    while p <> nil do
    begin
      u := p^.v;
      if not visited [ u ] then // Szukamy wierzchołków nieodwiedzonych
      begin
        visited [ u ] := true;  // Oznaczamy wierzchołek jako odwiedzony
        S.push ( u );  // i umieszczamy go na stosie
      end;
      p := p^.next;    // Następny sąsiad
    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 ( visited, 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 slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  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 = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack( )
{
  while( S ) pop( );
}

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

// Zwraca szczyt stosu
//--------------------
int stack::top ( void )
{
  return S->v;
}

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

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

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

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

  cin >> n >> m;             // Odczytujemy liczbę wierzchołków i krawędzi

  A = new slistEl * [ n ];   // Tworzymy tablice dynamiczne
  visited = new bool [ n ];

  // Inicjujemy tablice

  for( i = 0; i < n; i++ )
  {
    A [ i ] = NULL;
    visited [ i ] = false;
  }

  // Odczytujemy kolejne definicje krawędzi.

  for( i = 0; i < m; i++ )
  {
    cin >> v >> u;           // Wierzchołki tworzące krawędź
    p = new slistEl;         // Tworzymy nowy element
    p->v = u;                // Numerujemy go jako w
    p->next = A [ v ];       // Dodajemy go na początek listy A [ v ] 
    A [ v ] = p;
 }

  // Tworzymy graf podstawowy

  for( v = 0; v < n; v++ )
  {
    for( p = A [ v ]; p; p = p->next ) // Przeglądamy sąsiadów
    {
      S.push ( v );
      S.push ( p->v );       // Krawędź v-u na stos
    }
  }

  while( !S.empty( ) )
  {
    u = S.top( ); S.pop( );
    v = S.top( ); S.pop( );  // Pobieramy zapamiętane wierzchołki
    p = new slistEl;         // Do grafu dodajemy krawędź odwrotną
    p->v = v;
    p->next = A [ u ];
    A [ u ] = p;
  }

  // Badamy spójność grafu podstawowego

  vc = 0;                    // Zerujemy licznik wierzchołków

  S.push ( 0 );              // Wierzchołek startowy na stos
  visited [ 0 ] = true;      // Oznaczamy go jako odwiedzony

  while( !S.empty( ) )       // Wykonujemy przejście DFS
  {
    v = S.top( );            // Pobieramy wierzchołek ze stosu
    S.pop( );                // Pobrany wierzchołek usuwamy ze stosu
    vc++;                    // Zwiększamy licznik wierzchołków
    for( p = A [ v ]; p; p = p->next ) // Przeglądamy sąsiadów
    {
      u = p->v;
      if( !visited [ u ] )    // Szukamy wierzchołków nieodwiedzonych
      {
        visited [ u ] = true; // Oznaczamy wierzchołek jako odwiedzony
        S.push ( u );         // i umieszczamy go na stosie
      }
    }
  }

  // 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 [ ] visited;

  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 slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  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
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push ( ByVal v As Integer )
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop( )
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

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

Dim As Integer n, m       ' Liczba wierzchołków i krawędzi
Dim As slistEl Ptr Ptr A  ' Tablica list sąsiedztwa grafu
Dim As Byte Ptr visited   ' Tablica odwiedzin
Dim As stack S            ' Stos
Dim As Integer i, v, u, vc
Dim As slistEl Ptr p, r

Open Cons For Input As #1

Input #1, n, m            ' Odczytujemy liczbę wierzchołków i krawędzi

A = New slistEl Ptr [ n ] ' Tworzymy tablice dynamiczne
visited = New Byte [ n ] 

' Inicjujemy tablice

For i = 0 To n - 1
  A [ i ] = 0
  visited [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1, v, u         ' Wierzchołki tworzące krawędź
  p = New slistEl        ' Tworzymy nowy element
  p->v = u               ' Numerujemy go jako w
  p->next = A [ v ]      ' Dodajemy go na początek listy A [ v ] 
  A [ v ] = p
Next

Close #1

' Tworzymy graf podstawowy

For v = 0 To n - 1
  p = A [ v ] 
  While p                ' Przeglądamy sąsiadów
    S.push ( v )
    S.push ( p->v )      ' Krawędź v-u na stos
    p = p->Next          ' Następny sąsiad
  Wend
Next

While S.empty( ) = 0
  u = S.top( ): S.pop( )
  v = S.top( ): S.pop( ) ' Pobieramy zapamiętane wierzchołki
  p = new slistEl        ' Do grafu dodajemy krawędź odwrotną
  p->v = v
  p->next = A [ u ] 
  A [ u ] = p
Wend

' Badamy spójność grafu podstawowego

vc = 0                   ' Zerujemy licznik wierzchołków

S.push ( 0 )             ' Wierzchołek startowy na stos
visited [ 0 ] = 1        ' Oznaczamy go jako odwiedzony

While S.empty( ) = 0     ' Wykonujemy przejście DFS
  v = S.top( )           ' Pobieramy wierzchołek ze stosu
  S.pop( )               ' Pobrany wierzchołek usuwamy ze stosu
  vc += 1                ' Zwiększamy licznik wierzchołków
  p = A [ v ] 
  While p                ' Przeglądamy sąsiadów
    u = p->v
    If visited [ u ] = 0 Then ' Szukamy wierzchołków nieodwiedzonych
      visited [ u ] = 1  ' Oznaczamy wierzchołek jako odwiedzony
      S.push ( u )       ' i umieszczamy go na stosie
    End If
    p = p->Next
  Wend
Wend

' Wyświetlamy wyniki

Print

If vc = n Then Print "CONNECTED GRAPH": Else Print "DISCONNECTED GRAPH"

' 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 [ ] visited

End
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.