Çizgelerin Bilgisayarda Gösterilmesi

Çeşitli düğüm ve bu düğümleri birbirlerine bağlayan kenarlardan oluşan yapılara çizge denir. Çizgeler, çeşitli durumları ve durumlar arasındaki bağlantıyı göstermek için kullanılabilir.

Örnek bir çizge. Bu çizgede düğümler kişileri, kenarlar ise arkadaşlık ilişkilerini temsil ediyor.

Çizgeleri bilgisayara aktarırken depolanması gereken iki veri vardır. Düğümler ve düğümler arasındaki kenarlar. Çizge teorisinde düğümlerin yeri önemli olmadığından bunun saklanmasına gerek yoktur. Bu verileri depolamak için kullanılabilecek olan ilk yöntem, n düğüm sayısı olacak şekilde bütün düğümleri 0’dan (n-1)’e kadar numaralandırmak, ardından verileri n’e n büyüklüğünde bir iki boyutlu a dizisinde depolamaktır. Bu dizide a[i][j], i düğümünden j düğümüne giden kenarı göstermektir. Eğer bu çizgede kenarların herhangi bir ağırlığı yoksa a[i][j] kenar var anlamında 1, ya da kenar yok anlamında 0 olacaktır. Eğer kenarların ağırlıkları var ise, a[i][j]’nin değeri kenarın ağırlığına eşit olur. Çizgedeki kenarların 2 yönlü olduğu durumlarda ise her zaman a[i][j] == a[j][i] olur.

#include <bits/stdc++.h>
#define MAXEDGE 100
using namespace std;

int a[MAXEDGE][MAXEDGE];
//Çizgemizde olabilecek maksimum düğüm sayısı 
//büyüklüğünde bir iki boyutlu dizi tanımlanır.

int d, k;
//d çizgedeki düğüm, k ise kenar sayısın gösterir.

int main(){
    cin >> d >> k;
    int i, j, w;
    while(k--){
        cin >> i >> j >> w;
        //Burada i ile j kenarın bağladığı düğümlere,
        //w ise kenarın ağırlığına eşittir.
        //Eğer çizgede kenarların ağırlıkları yoksa 
        //w değişkenine ihtiyaç yoktur.
        
        a[i][j] = w;
        //Kenar ağırlıklıysa w, değilse 1 değerine eşitlenir.

        a[j][i] = a[i][j];
        //Eğer kenarlar iki yönlüyse a[j][i], a[i][j]'ye eşitlenir.
        //Kenarların tek yönlü olduğu durumda bu koda gerek yoktur. 
    } 
}

Bu yöntem koda dökülmesi çok kolay olduğundan bazı durumlarda avantajlı olabilir, ama çok büyük sıkıntıları vardır. İlk olarak, d düğümlü bir çizge için hafızada \textrm{d}^2 yer kullanılır. Aynı zamanda bir düğüme bağlı olan kenarları bulabilmek için d tane işlem yapılması gerekir. Şimdi gösterebileğimiz yöntem bu iki soruna çözüm getirir.

Çizgemizi iki boyutlu bir dizide tutmak yerine, her düğüme karşılık gelecek bir vektör bulunduracak bir dizide tutalım. Vektörler, c++ kodlama dilinde bulunana ve boyutu içinde bulundurduğu değişken sayısına göre değişen dizilerdir. O zaman vektörlerden oluşturduğumuz g adında bir dizi tanımlayalım. Burada g[i], i ile bir kenar bağlantısı olan düğümleri bulunduran bir vektör olacak. Mesela 3 numaralı düğümün 0, 2 ve 7 numaralı düğümlerle kenar bağlantısı var ise g[3] = {0, 2, 7} olacaktır.

#include <bits/stdc++.h>
#define MAXEDGE 100
using namespace std;

vector<int> g[MAXEDGE];
//Çizgemizde olabilecek maksimum düğüm sayısı 
//büyüklüğünde bir vektör dizisi tanımlanır.

int d, k;
//d çizgedeki düğüm, k ise kenar sayısın gösterir.

int main(){
    cin >> d >> k;
    int i, j;
    while(k--){
        cin >> i >> j;
        //Burada i ile j kenarın bağladığı düğümlerdir.
        
        g[i].push_back(j);
        //i düğümünün vektörüne j düğümü eklenir.
        //Bu, i'den j'ye kenar bağlantısı olduğunu
        //gösterir.

        g[j].push_back(i);
        //Eğer kenarlar iki yönlüyse aynı işlem j için
        //de yapılır. 
    } 
}

Peki kenarlarımızın ağırlıkları varsa? Bu durumda herhangi g[i] vektörü integer değerleri değil de iki integerden oluşan çiftler tutar. Bu çiftlerde birinci eleman kenarın bağladığı ikinci düğümü, ikinci eleman ise kenarın ağırlığını verir.

#include <bits/stdc++.h>
#define MAXEDGE 100
using namespace std;

vector<pair<int, int>> g[MAXEDGE];
//Çizgemizde olabilecek maksimum düğüm sayısı 
//büyüklüğünde bir vektör dizisi tanımlanır.
//Burada vektörler integer değil de pair 
//değerleri taşır

int d, k;
//d çizgedeki düğüm, k ise kenar sayısın gösterir.

int main(){
    cin >> d >> k;
    int i, j, w;
    while(k--){
        cin >> i >> j >> w;
        //Burada i ile j kenarın bağladığı düğümler,
        //w ise kenarın ağırlığıdır.
        
        g[i].push_back(make_pair(j, w));
        //i düğümünün vektörüne j-w çifti eklenir.
        //Bu, i'den j'ye w ağırlıklı bir kenar
        //olduğunu gösterir.

        g[j].push_back(make_pair(i, w));
        //Eğer kenarlar iki yönlüyse aynı işlem j için
        //de yapılır. 
    } 
}
One Comment

Add a Comment

Your email address will not be published. Required fields are marked *