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

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

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 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:

–

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

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:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla grafu skierowanego

Algorytm budowania grafu podstawowego z grafu nieskierowanego

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm budowania grafu podstawowego w grafie nieskierowanym

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy