Graf nieskierowany a macierz sąsiedztwa
Kod był wyświetlany 4266 razy.
    /*
  Name: Graf nieskierowany opisany za pomocą macierzą sąsiedztwa ver.1
  Copyright: GPL GNU
   Date: 31-10-11 19:10
  Description: 
  Grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połączonych za pomocą 
  krawędzi (oznaczonych przez E).Grafy dzielimy na grafy skierowane i nieskierowane. 
  W grafie nieskierowanym (ang. undirected graph) - po każdej krawędzi można przejść w obu kierunkach. 
  Jezeli przyjmiemy, że graf nieskierowany można potraktować jako graf skierowany, w którym mamty po dwie krawędzie skierowane 
  w odwrotnych kierunkach pomiędzy dwoma wierzchołkami.
  Dla opisania grafu za pomocą programu komputerowego tworzymy kwadratową macierz o rozmiarach V*V gdzie V oznacza liczbę wierzchołków
  w grafie Numery wierszy oraz kolumn tej macierzy odpowiadają numerom wierzchołków w grafie. Dane dwa wierzchołki są połączone krawędzią, 
  jeśli na przecięciu wiersza o numerze pierwszego wierzchołka i kolumny o numerze drugiego wierzchołka komórce macierzy znajdeuje się wartość 1. 
  W przypadku gdy wartośc komórki wynosi 0 dwa wierzchołki nie są połączone krawędzią.
  Przykład macierz sąsiedztwa grafu 

  	1	2	3	4	5
1	0	1	1	0	1
2	1	0	1	1	1
3	1	1	0	1	0
4	0	1	1	0	1
5	1	1	0	1	0
   
Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna. 
Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi. */

#include <iostream>
#include <iomanip>
using namespace std;

const int W = 25; // maksymalna liczba wierzchołków w grafie
main()
{
  
  int i,j,wmax,n,x,y;
  bool A[W][W]; // macierz sąsiedztwa
  
  for(i = 0; i <W; i++)        //zerowanie tablicy
    for(j = 0; j < W; j++)
    A[i][j] = 0;
  
  wmax = 0; //przypisujemy początkowy numer  wierzchołkowi wmax =0  
 
  cout<<"\n\n\tPodaj liczbe krawedzi:  ";
  cin >> n; // liczba krawedzi
  
 cout<<"\n\nWczytywanie krawedzi nr wierzchołkow nalezy rozdzielic spacja: \n\n";
/*Przykładowe dane dla grafu składajacego się z trzech wierzchołków i trzech krawędzi  
 1 2 (pary wierzchołków w grafie)
 2 3
 3 1 */
  for(i = 0; i < n; i++)
  {
    cin >> x >> y; // wczytujemy pary wierzchołków krawędzie i tworzymy macierz sąsiedztwa
    
    if(x > wmax)
    swap(x,wmax); 
    if(y > wmax)  
    swap(y,wmax);
    A[x-1][y-1] = 1; 
    A[y-1][x-1] = 1;
  }
  cout << endl;
  system("cls");
  
  cout<<"\t\tMacierz sasiedztwa";
  cout<<endl<<endl;
  
  for(i = 0; i < wmax; i++)
  {
    for(j = 0; j < wmax; j++) 
    cout<<setw(8) << A[i][j];
    cout<<endl;
  }
  cin.ignore();
  getchar();
  return 0;
}
    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT