Spójność grafu


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie dla grafu nieskierowanego
Rozwiązanie dla grafu skierowanego

Problem

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
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 K08...K14 ; przechodzimy przez graf
K08:     vS.top() ; pobieramy wierzchołek ze stosu
K09:     S.pop() ; pobrany wierzchołek usuwamy ze stosu
K10:     vcvc + 1 ; zwiększamy licznik odwiedzonych wierzchołków
K11:     Dla każdego sąsiada u wierzchołka v, wykonuj 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

 

Program

Ważne:

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

Przykładowe dane

Graf spójny

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

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

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
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 K04...K06 ; przechodzimy przez kolejne wierzchołki grafu
K04:     Dla każdego sąsiada u wierzchołka v wykonuj 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 K02...K03 ; przechodzimy przez wierzchołki grafu od pierwszego do przedostatniego
K02:     Dla każdego sąsiada u wierzchołka v wykonuj 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 K05...K07  
K05:     uS.top();   S.pop() ; pobieramy ze stosu krawędź
K06:     vS.top();   S.pop()  
K07:     Dodaj krawędź u-v do grafu  
K08: Zakończ  

 

Program

Ważne:

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

Przykładowe dane

Skierowany graf spójny

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

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.