Tworzenie macierzy sąsiedztwa i listy sąsiedztwa
Programy uruchomiono w środowisku Bloodshed Dev-C++ 4.9.9.2

       Programy

Poniżej przedstawiamy przykładowe programy odczytujące ze standardowego wejścia graf i umieszczające go w macierzy i liście sąsiedztwa. Graf zadany jest w następującej postaci:

W pierwszym wierszu liczba całkowita n określa ilość krawędzi w grafie. W n kolejnych wierszach występują pary liczb oznaczające wierzchołki grafu połączone krawędzią. Kolejność tych par jest zupełnie dowolna. Oto dane wejściowe dla przykładowego grafu:

obrazek

 

8
1 2
1 3
1 4
2 3
2 4
2 5
3 5
4 5


Program odczytuje ze standardowego wejścia definicje krawędzi grafu nieskierowanego i na ich podstawie tworzy macierz sąsiedztwa. Zwróć uwagę, iż w przypadku grafu nieskierowanego macierz sąsiedztwa jest macierzą symetryczną względem głównej przekątnej.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-01

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

main()
{
  int i,j,wmax,n,x,y;
  char A[MAX_N][MAX_N]; // macierz sąsiedztwa
  
  for(i = 0; i < MAX_N; i++)
    for(j = 0; j < MAX_N; j++) A[i][j] = 0;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    A[x-1][y-1] = 1;
    A[y-1][x-1] = 1;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    for(j = 0; j < wmax; j++) cout << (int)A[i][j] << " ";
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2
1 3
1 4
2 3
2 4
2 5
3 5
4 5

0 1 1 1 0
1 0 1 1 1
1 1 0 0 1
1 1 0 0 1
0 1 1 1 0

Program odczytuje ze standardowego wejścia definicje krawędzi grafu nieskierowanego i na ich podstawie tworzy listę sąsiedztwa.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-02

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

struct TNode
{
  int node;            // numer wierzchołka
  struct TNode * next; // następny element listy
};

main()
{
  int i,wmax,n,x,y;
  struct TNode *L[MAX_N],*p;
  
  for(i = 0; i < MAX_N; i++) L[i] = NULL;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    p = new TNode;
    p->next = L[x-1]; p->node = y; L[x-1] = p;
    p = new TNode;
    p->next = L[y-1]; p->node = x; L[y-1] = p;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    cout << i + 1 << ":";
    p = L[i];
    while(p)
    {
      cout << p->node << " ";
      p = p->next;
    }
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2
1 3
1 4
2 3
2 4
2 5
3 5
4 5

1:4 3 2
2:5 4 3 1
3:5 2 1
4:5 2 1
5:4 3 2

Dwa kolejne programy tworzą macierz sąsiedztwa oraz listę sąsiedztwa dla grafu skierowanego. Do testów można skorzystać z poniższego grafu:

obrazek

 

8
1 2
1 4
2 3
3 1
4 2
4 5
5 3
5 2


Program odczytuje ze standardowego wejścia definicje krawędzi grafu skierowanego i na ich podstawie tworzy macierz sąsiedztwa. Zwróć uwagę, iż dla grafu skierowanego macierz sąsiedztwa jest zwykle macierzą niesymetryczną.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-03

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

main()
{
  int i,j,wmax,n,x,y;
  char A[MAX_N][MAX_N]; // macierz sąsiedztwa
  
  for(i = 0; i < MAX_N; i++)
    for(j = 0; j < MAX_N; j++) A[i][j] = 0;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    A[x-1][y-1] = 1;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    for(j = 0; j < wmax; j++) cout << (int)A[i][j] << " ";
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2
1 4
2 3
3 1
4 2
4 5
5 3
5 2

0 1 0 1 0
0 0 1 0 0
1 0 0 0 0
0 1 0 0 1
0 1 1 0 0

Program odczytuje ze standardowego wejścia definicje krawędzi grafu skierowanego i na ich podstawie tworzy listę sąsiedztwa.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-04

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

struct TNode
{
  int node;            // numer wierzchołka
  struct TNode * next; // następny element listy
};

main()
{
  int i,wmax,n,x,y;
  struct TNode *L[MAX_N],*p;
  
  for(i = 0; i < MAX_N; i++) L[i] = NULL;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    p = new TNode;
    p->next = L[x-1]; p->node = y; L[x-1] = p;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    cout << i + 1 << ":";
    p = L[i];
    while(p)
    {
      cout << p->node << " ";
      p = p->next;
    }
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2
1 4
2 3
3 1
4 2
4 5
5 3
5 2

1:4 2
2:3
3:1
4:5 2
5:2 3

Dwa kolejne programy tworzą macierz sąsiedztwa oraz listę sąsiedztwa dla grafu skierowanego z wagami. Na wejściu pierwsza liczba n określa ilość krawędzi w grafie. Następne n wierszy zawierają definicję poszczególnych krawędzi. Definicja składa się z trzech liczb: dwie pierwsze oznaczają wierzchołki grafu połączone tą krawędzią, a trzecia liczba określa wagę krawędzi. Do testów można skorzystać z poniższego grafu:

obrazek

 

8
1 2 3
1 4 3
2 3 3
3 1 2
4 2 6
4 5 1
5 3 1
5 2 5


Program odczytuje ze standardowego wejścia definicje krawędzi grafu skierowanego i na ich podstawie tworzy macierz sąsiedztwa oraz macierz wag krawędzi. Wyświetlana jest macierz wag.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-05

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

main()
{
  int i,j,wmax,n,x,y,z;
  char A[MAX_N][MAX_N]; // macierz sąsiedztwa
  int  W[MAX_N][MAX_N]; // macierz wag
  
  for(i = 0; i < MAX_N; i++)
    for(j = 0; j < MAX_N; j++) W[i][j] = A[i][j] = 0;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y >> z; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    A[x-1][y-1] = 1;
    W[x-1][y-1] = z;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    for(j = 0; j < wmax; j++) cout << W[i][j] << " ";
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2 3
1 4 3
2 3 3
3 1 2
4 2 6
4 5 1
5 3 1
5 2 5

0 3 0 3 0
0 0 3 0 0
2 0 0 0 0
0 6 0 0 1
0 5 1 0 0

Program odczytuje ze standardowego wejścia definicje krawędzi grafu skierowanego i na ich podstawie tworzy listę sąsiedztwa. Elementy listy zapamiętują wagę krawędzi.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P011-06

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie

struct TNode
{
  int node;            // numer wierzchołka
  int weight;          // waga krawędzi
  struct TNode * next; // następny element listy
};

main()
{
  int i,wmax,n,x,y,z;
  struct TNode *L[MAX_N],*p;
  
  for(i = 0; i < MAX_N; i++) L[i] = NULL;
  wmax = 0;
  cin >> n; // odczytujemy ilość krawędzi
  for(i = 0; i < n; i++)
  {
    cin >> x >> y >> z; // odczytujemy krawędź
    wmax = (x > wmax) ? x : wmax;
    wmax = (y > wmax) ? y : wmax;
    p = new TNode;
    p->next = L[x-1]; p->node = y; p->weight = z; L[x-1] = p;
  }
  cout << endl;
  for(i = 0; i < wmax; i++)
  {
    cout << i + 1 << ":";
    p = L[i];
    while(p)
    {
      cout << p->node << "#" << p->weight << " ";
      p = p->next;
    }
    cout << endl;
  }
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
 
8
1 2 3
1 4 3
2 3 3
3 1 2
4 2 6
4 5 1
5 3 1
5 2 5

1:4#3 2#3
2:3#3
3:1#2
4:5#1 2#6
5:2#5 3#1

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe