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:

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    S : PSLel;  // 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 : 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
  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      : PSLel;

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 SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    SLel * 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)
{
  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()
{
  int n, m;       // Liczba wierzchołków i krawędzi
  SLel ** A;   // Tablica list sąsiedztwa grafu
  bool * visited; // Tablica odwiedzin
  Stack S;        // Stos
  int i, v, u, vc;
  SLel *p, *r;

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

  A = new SLel * [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 SLel;    // 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 SLel;    // 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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    S As SLel 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 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 ***
' **********************

Dim As Integer n, m       ' Liczba wierzchołków i krawędzi
Dim As SLel 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 SLel Ptr p, r

Open Cons For Input As #1

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

A = New SLel 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 SLel       ' 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 SLel       ' 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.

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

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: 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    S : PSLel;  // 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 : 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
  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      : PSLel;

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 SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    SLel * 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)
{
  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()
{
  int n, m;       // Liczba wierzchołków i krawędzi
  SLel ** A;   // Tablica list sąsiedztwa grafu
  bool * visited; // Tablica odwiedzin
  Stack S;        // Stos
  int i, v, u, vc;
  SLel *p, *r;

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

  A = new SLel * [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 SLel;         // 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 SLel;         // 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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    S As SLel 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 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 ***
' **********************

Dim As Integer n, m       ' Liczba wierzchołków i krawędzi
Dim As SLel 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 SLel Ptr p, r

Open Cons For Input As #1

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

A = New SLel 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 SLel        ' 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 SLel        ' 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:

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