Mewakili Graf

Mewakili graf adalah untuk menyimpan bucu dan tepinya dalam atur cara. Struktur data untuk menyimpan graf ialah tatasusunan atau senarai. Untuk menulis atur cara yang memproses dan memanipulasi graf, anda perlu menyimpan atau mewakili data bagi graf dalam komputer.

Mewakili Bucu

Bucu boleh disimpan dalam tatasusunan atau senarai. Sebagai contoh, anda boleh menyimpan semua nama bandar dalam graf dalam Rajah di bawah menggunakan tatasusunan berikut:

Rentetan[] bucu = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", " Miami", "Dallas", "Houston"};

Bucu boleh menjadi objek dalam apa jua jenis. Contohnya, anda boleh menganggap bandar sebagai objek yang mengandungi maklumat seperti namanya, penduduk dan datuk bandar. Oleh itu, anda boleh mentakrifkan bucu seperti berikut:

City city0 = new City("Seattle", 608660, "Mike McGinn");
...
City city11 = new City("Houston", 2099451, "Annise Parker");
City[] bucu = {city0, city1, ... , city11};

Bandar kelas awam {
Nama bandar String peribadi;
populasi int persendirian;
Datuk Bandar String persendirian;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

Bucu boleh dilabelkan dengan mudah menggunakan nombor asli 0, 1, 2, ..., n - 1, untuk graf bagi n bucu. Oleh itu, bucu[0] mewakili "Seattle", bucu[1] mewakili "San Francisco" dan seterusnya, sebagai ditunjukkan dalam Rajah di bawah.

Anda boleh merujuk bucu dengan namanya atau indeksnya, yang mana lebih mudah. Jelas sekali, adalah mudah untuk mengakses puncak melalui indeksnya dalam program.

Mewakili Tepi: Tatasusunan Tepi

Tepi boleh diwakili menggunakan tatasusunan dua dimensi. Sebagai contoh, anda boleh menyimpan semua tepi dalam graf dalam Rajah 28.1 menggunakan tatasusunan berikut:

int[][] tepi = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

Perwakilan ini dikenali sebagai tatasusunan tepi. Bucu dan tepi dalam Rajah di bawah (a) boleh diwakili seperti berikut:

String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
int[][] tepi = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

Mewakili Tepi: Objek Tepi

Cara lain untuk mewakili tepi ialah dengan mentakrifkan tepi sebagai objek dan menyimpan tepi dalam java.util.ArrayList. Kelas Edge boleh ditakrifkan seperti berikut:

kelas awam Edge {
int u;
int v;
public Edge(int u, int v) {
ini.u = u;
ini.v = v;
}
boolean awam sama dengan(Objek o) {
kembalikan u == ((Tepi)o).u && v == ((Tepi)o).v;
}
}

Sebagai contoh, anda boleh menyimpan semua tepi dalam graf dalam Rajah di bawah menggunakan senarai berikut:

java.util.ArrayList list = new java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Menyimpan objek Edge dalam ArrayList berguna jika anda tidak mengetahui tepinya terlebih dahulu.

Semasa mewakili tepi menggunakan tatasusunan tepi atau objek Tepi di bahagian sebelumnya (Mewakili Tepi: Tatasusunan Tepi) dan lebih awal dalam bahagian ini mungkin intuitif untuk input, ia tidak cekap untuk pemprosesan dalaman. Dua bahagian seterusnya memperkenalkan perwakilan graf menggunakan matriks bersebelahan dan senarai bersebelahan. Kedua-dua struktur data ini cekap untuk memproses graf.

Mewakili Tepi: Matriks Bersebelahan

Anggap bahawa graf mempunyai n bucu. Anda boleh menggunakan matriks n * n dua dimensi, katakan adjacencyMatrix, untuk mewakili tepi. Setiap elemen dalam tatasusunan ialah 0 atau 1. adjacencyMatrix[i][j] ialah 1 jika terdapat tepi dari bucu i ke bucu j; jika tidak, adjacencyMatrix[i][j] ialah 0. Jika graf tidak terarah, matriks adalah simetri, kerana AdjacencyMatrix[i][j] adalah sama dengan adjacencyMatrix[j][i]. Contohnya, tepi dalam graf dalam Rajah di bawah boleh diwakili menggunakan matriks bersebelahan seperti berikut:

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};

Memandangkan matriks adalah simetri untuk graf tidak terarah, untuk menjimatkan storan anda boleh menggunakan tatasusunan compang-camping.

Matriks bersebelahan untuk graf terarah dalam Rajah di bawah (a) boleh diwakili seperti berikut:

int[][] a = {{0, 0, 1, 0, 0}, // Peter
{0, 0, 1, 0, 0}, // Jane
{0, 0, 0, 0, 1}, // Tandakan
{0, 0, 0, 0, 1}, // Cindy
{0, 0, 0, 0, 0} // Wendy
};

Mewakili Tepi: Senarai Bersebelahan

Anda boleh mewakili tepi menggunakan senarai bucu bersebelahan atau senarai tepi bersebelahan. Senarai bucu bersebelahan untuk bucu i mengandungi bucu yang bersebelahan dengan i dan senarai tepi bersebelahan untuk bucu i mengandungi tepi yang bersebelahan dengan i. Anda boleh menentukan tatasusunan senarai. Yang
tatasusunan mempunyai n entri, dan setiap entri ialah senarai. Senarai bucu bersebelahan untuk bucu i mengandungi semua bucu j supaya terdapat tepi dari bucu i ke bucu j. Contohnya, untuk mewakili tepi dalam graf dalam Rajah di bawah, anda boleh membuat tatasusunan senarai seperti berikut:

java.util.List[] jiran = java.util.List baharu[12];

jiran[0] mengandungi semua bucu bersebelahan dengan bucu 0 (iaitu, Seattle), jiran[1] mengandungi semua bucu bersebelahan bucu 1 (iaitu, San Francisco), dan seterusnya, seperti yang ditunjukkan dalam Rajah di bawah.

Untuk mewakili senarai tepi bersebelahan bagi graf dalam Rajah di bawah, anda boleh membuat tatasusunan senarai seperti berikut:

java.util.List[] jiran = java.util.List baharu[12];

jiran[0] mengandungi semua tepi bersebelahan dengan bucu 0 (iaitu, Seattle), jiran[1] mengandungi semua tepi bersebelahan dengan bucu 1 (iaitu, San Francisco), dan seterusnya, seperti yang ditunjukkan dalam Rajah di bawah.

Anda boleh mewakili graf menggunakan matriks bersebelahan atau senarai bersebelahan. Mana satu lebih baik? Jika graf adalah padat (iaitu, terdapat banyak tepi), menggunakan matriks bersebelahan adalah diutamakan. Jika graf adalah sangat jarang (iaitu, sangat sedikit tepi), menggunakan senarai bersebelahan adalah lebih baik, kerana menggunakan matriks bersebelahan akan membazirkan banyak ruang.

Kedua-dua matriks bersebelahan dan senarai bersebelahan boleh digunakan dalam atur cara untuk menjadikan algoritma lebih cekap. Sebagai contoh, diperlukan masa tetap O(1) untuk memeriksa sama ada dua bucu disambungkan menggunakan matriks bersebelahan, dan masa linear O(m) diperlukan untuk mencetak semua tepi dalam graf menggunakan senarai bersebelahan, dengan m ialah bilangan tepi. .

Senarai bucu bersebelahan adalah lebih mudah untuk mewakili graf tidak berwajaran. Walau bagaimanapun, senarai tepi bersebelahan adalah lebih fleksibel untuk pelbagai aplikasi graf. Mudah untuk menambah kekangan tambahan pada tepi menggunakan senarai tepi bersebelahan. Atas sebab ini, buku ini akan menggunakan senarai tepi bersebelahan untuk mewakili graf.

Anda boleh menggunakan tatasusunan, senarai tatasusunan atau senarai terpaut untuk menyimpan senarai bersebelahan. Kami akan menggunakan senarai dan bukannya tatasusunan, kerana senarai itu mudah dikembangkan untuk membolehkan anda menambah bucu baharu. Selanjutnya kami akan menggunakan senarai tatasusunan dan bukannya senarai terpaut, kerana algoritma kami hanya memerlukan mencari bucu bersebelahan dalam senarai. Menggunakan senarai tatasusunan adalah lebih cekap untuk algoritma kami. Menggunakan senarai tatasusunan, senarai tepi bersebelahan dalam Rajah di bawah boleh dibina seperti berikut:

Senaraikan> jiran = ArrayList baharu<>();
neighbors.add(new ArrayList());
neighbors.get(0).add(new Edge(0, 1));
neighbors.get(0).add(new Edge(0, 3));
neighbors.get(0).add(new Edge(0, 5));
neighbors.add(new ArrayList());
neighbors.get(1).add(new Edge(1, 0));
neighbors.get(1).add(new Edge(1, 2));
neighbors.get(1).add(new Edge(1, 3));
...
...
neighbors.get(11).add(new Edge(11, 8));
neighbors.get(11).add(new Edge(11, 9));
neighbors.get(11).add(new Edge(11, 10));

Atas ialah kandungan terperinci Mewakili Graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!