Bagaimana untuk mewakili graf menggunakan matriks korelasi di Jawa?

Untuk mewakili graf dalam Java menggunakan matriks perkaitan, struktur data mesti dibina yang mengandungi perhubungan antara bucu dan tepi. Matriks perkaitan ialah tatasusunan dua dimensi di mana baris dan lajur masing-masing mewakili bucu dan tepi, dan entri mewakili sambungan antara mereka. Jika terdapat "1" pada kedudukan (i, j), maka bucu i bersilang tepi j. Walaupun lebih banyak memori mungkin diperlukan untuk graf yang besar, pendekatan ini membolehkan operasi graf yang cekap seperti memasukkan atau memadamkan tepi. Dengan mencipta struktur data ini dalam Java, pengaturcara boleh membina dan memanipulasi struktur graf dengan cekap untuk menyelesaikan banyak masalah dalam sains komputer dan bidang berkaitan.

Matriks Korelasi

Dalam teori graf, hubungan antara bucu dan tepi dalam graf secara matematik diwakili oleh matriks persatuan. Matriks korelasi ialah matriks binari dua dimensi di mana lajur mewakili tepi dan baris mewakili bucu. Catatan pada kedudukan (i, j) ialah '1' jika bucu i bersebelahan dengan tepi j jika tidak ia adalah '0'. Matriks ini mewakili struktur graf dengan berkesan, menjadikannya lebih mudah untuk melaksanakan operasi seperti menambah dan mengalih keluar tepi. Ia merupakan konsep penting dalam sains komputer dan disiplin lain yang melibatkan rangkaian kompleks kerana ia menyediakan alat utama untuk menganalisis dan menyelesaikan masalah berasaskan graf.

Kaedah penggunaan

• Matriks bersebelahan

• Senarai Bersebelahan

• Senarai Tepi

Matriks bersebelahan

Matriks bersebelahan ialah tatasusunan dua dimensi yang digunakan untuk mewakili sambungan antara bucu semasa membuat graf dalam Java. Jika terdapat tepi yang menghubungkan bucu i dan bucu j, anda boleh melihatnya dalam sel (i, j) matriks. "1" dalam sel bermakna terdapat tepi, manakala "0" bermaksud tiada tepi. Matriks ini sering digunakan dalam graf padat kerana ia membantu untuk melintasi dan mengkaji graf dengan cepat. Walau bagaimanapun, disebabkan bentuk segi empat sama, ia boleh menjadi intensif memori untuk plot besar. Pengaturcara boleh memodelkan, menganalisis dan memanipulasi topologi graf dengan berkesan untuk pelbagai aplikasi dengan menggunakan matriks bersebelahan dalam Java.

Algoritma

Tentukan bilangan bucu graf dalam langkah pertama

• Bina tatasusunan (matriks) dua dimensi bagi [bilangan bucu] x [bilangan bucu].

• Mulakan matriks dengan menetapkan semua entri kepada 0, bermakna tiada tepi pada mulanya.

• Dalam graf, tetapkan sel matriks korelasi setiap tepi (i, j) kepada 1 untuk mewakili sambungan antara bucu i dan j.

• Simetri matriks dipastikan dalam graf tidak terarah kerana tepi (i,j) dan (j,i) adalah sama.

• Termasuk rutin untuk menguji kehadiran kelebihan, mencari jiran bucu dan menambah/mengalihkan tepi.

• Untuk mengesahkan ketepatan dan kefungsian pelaksanaan, sila uji menggunakan gambar rajah contoh.

Contoh

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
   int V;
   vector<vector<int>> adjMatrix;

public:
   Graph(int vertices) : V(vertices) {
      adjMatrix.resize(V, vector<int>(V, 0));
   }

   void addEdge(int u, int v) {
      adjMatrix[u][v] = 1;
      adjMatrix[v][u] = 1;
   }

   void printAdjMatrix() {
      for (int i = 0; i < V; ++i) {
         for (int j = 0; j < V; ++j) {
            cout << adjMatrix[i][j] << " ";
         }
         cout << endl;
      }
   }
};

int main() {
   int numVertices = 5;
   Graph graph(numVertices);

   graph.addEdge(0, 1);
   graph.addEdge(0, 4);
   graph.addEdge(1, 2);
   graph.addEdge(1, 3);
   graph.addEdge(1, 4);
   graph.addEdge(2, 3);
   graph.addEdge(3, 4);

   cout << "Adjacency Matrix:\n";
   graph.printAdjMatrix();

   return 0;
}

Output

Adjacency Matrix:
0 1 0 0 1 
1 0 1 1 1 
0 1 0 1 0 
0 1 1 0 1 
1 1 0 1 0 

Senarai bersebelahan

Senarai bersebelahan ialah struktur data Java yang menyimpan sambungan dengan cekap. Apabila mewakili graf, senarai bersebelahan ialah struktur data Java yang digunakan untuk menyimpan perhubungan antara bucu dan bucu bersebelahan dengan cekap. Setiap senarai terpaut atau tatasusunan yang membentuk struktur ini sepadan dengan bucu dan mengandungi jiran bucu. Pendekatan ini berfungsi dengan baik untuk graf jarang kerana ia menjimatkan memori dengan mengekalkan hanya pautan yang sebenarnya wujud. Pengaturcara boleh melakukan traversal graf, penambahan nod dan operasi pemadaman dengan cepat dengan mencipta senarai bersebelahan dalam Java, menjadikannya pilihan popular untuk banyak algoritma dan aplikasi berkaitan graf.

Algoritma

• Adalah disyorkan untuk menyimpan senarai bersebelahan dalam struktur data. Ini boleh menjadi satu set senarai terpaut atau ArrayList, di mana setiap elemen mewakili bucu dan menyimpan maklumat tentang bucu bersebelahan.

• Mulakan senarai bersebelahan dengan menambah senarai kosong atau ArrayList untuk setiap bucu dalam graf

• Untuk menambah tepi antara bucu, anda perlu menyediakan kaedah yang sepadan dalam kelas graf. Teknik ini mengemas kini senarai bersebelahan dengan menambah bucu yang diperlukan pada senarai bersebelahan satu sama lain.

• Tambah kaedah penyingkiran tepi atau bucu untuk menukar senarai bersebelahan jika perlu.

• Gunakan senarai bersebelahan dengan teknik rentas graf seperti carian mendalam-dahulu atau carian luas-dahulu untuk meneroka semua bucu dalam graf dengan cepat.

• Untuk menyelesaikan banyak masalah dan teknik berkaitan rangkaian, gunakan perwakilan grafik dan senarai bersebelahan dalam program Java.

Contoh

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
   int numVertices;
   vector<vector<int>> adjList;

public:
   Graph(int vertices) : numVertices(vertices), adjList(vertices) {}

   void addEdge(int src, int dest) {
      adjList[src].push_back(dest);
      adjList[dest].push_back(src);
   }

   void printGraph() {
      for (int i = 0; i < numVertices; ++i) {
         cout << "Vertex " << i << " is connected to: ";
         for (int neighbor : adjList[i]) {
            cout << neighbor << " ";
         }
         cout << endl;
      }
   }
};

int main() {
   int numVertices = 5;
   Graph graph(numVertices);

   graph.addEdge(0, 1);
   graph.addEdge(0, 4);
   graph.addEdge(1, 2);
   graph.addEdge(1, 3);
   graph.addEdge(1, 4);
   graph.addEdge(2, 3);
   graph.addEdge(3, 4);

   graph.printGraph();

   return 0;
}

Output

Vertex 0 is connected to: 1 4 
Vertex 1 is connected to: 0 2 3 4 
Vertex 2 is connected to: 1 3 
Vertex 3 is connected to: 1 2 4 
Vertex 4 is connected to: 0 1 3 

Kesimpulan

Untuk memodelkan, menganalisis dan memanipulasi struktur rangkaian dengan berkesan, Java menyediakan fungsi penting dengan menggunakan matriks persatuan atau senarai bersebelahan untuk mewakili graf. Walaupun lebih intensif memori, matriks korelasi sesuai untuk graf tebal kerana ia menjadikan penambahan dan pengalihan tepi mudah. Senarai bersebelahan, sebaliknya, adalah cekap memori dan sangat sesuai untuk graf yang jarang, menjadikannya lebih mudah untuk melintasi graf dan melakukan operasi lain. Dalam sains komputer dan bidang lain, kedua-dua perwakilan digunakan sebagai struktur data asas untuk menyelesaikan masalah berkaitan graf. Pengaturcara boleh menggunakan strategi ini untuk mencipta algoritma dan aplikasi yang boleh dipercayai yang mengendalikan rangkaian kompleks dan data yang saling berkaitan.

Atas ialah kandungan terperinci Bagaimana untuk mewakili graf menggunakan matriks korelasi di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!