Aplikasi, kebaikan dan keburukan carta

Gambar rajah digunakan dalam subjek yang berbeza. Ia digunakan dalam biologi untuk mewakili interaksi gen, untuk pengoptimuman laluan dalam pengangkutan, dan untuk analisis sambungan pengguna dalam rangkaian sosial. Perwakilan visual carta tentang hubungan kompleks dan keupayaannya untuk memerhati corak dan arah aliran adalah dua daripada kekuatannya. Walau bagaimanapun, bekerja dengan set data yang besar boleh menjadikan carta sukar digunakan dan sukar difahami. Selain itu, mencipta carta boleh mengambil masa dan pengetahuan. Walaupun terdapat kekurangan ini, graf kekal sebagai alat yang berkesan untuk analisis data antara disiplin dan membuat keputusan.

Kaedah penggunaan

• Sediakan perwakilan

• Perwakilan pautan

• Ekspresi berurutan

Sediakan perwakilan

Setiap bucu dalam graf dikaitkan dengan set bucu sekelilingnya, yang mewakili graf. Dalam pendekatan ini, tepi graf disimpan dalam set bersebelahan atau jadual cincang yang mengandungi set. Set setiap bucu memastikan tiada bucu bersebelahan pendua, dan ia menguruskan graf jarang dengan cekap. Menambah dan mengeluarkan tepi adalah lebih mudah dan penggunaan memori dikurangkan berbanding kaedah perwakilan lain. Teknik ini sangat membantu apabila berurusan dengan rangkaian dengan tahap ketersambungan yang berbeza-beza, kerana ia boleh melaksanakan operasi dengan cekap seperti memeriksa tepi dan mengulang bucu berdekatan.

• Set bersebelahan: Dalam set perwakilan graf, set bersebelahan menggunakan set untuk merekodkan jiran setiap bucu, menghalang pertindihan dan memudahkan pemprosesan tepi yang cekap.

• Jadual cincang: Jadual cincang digunakan dalam konteks set perwakilan graf, menghubungkan setiap bucu dengan set yang mengandungi bucu jirannya.

Algoritma

• Bucu graf hendaklah diwakili oleh kelas atau struktur data. Setiap objek bucu perlu mempunyai koleksi yang mengandungi bucu bersebelahan dan ia juga perlu mempunyai ID atau label.

• Buat ruang storan kosong untuk menyimpan bucu graf (seperti tatasusunan, vektor atau jadual cincang).

• Untuk setiap bucu dalam graf:

  Mencipta objek bucu baharu dengan ID atau label yang ditentukan untuk setiap bucu dalam graf.

  Tambah bucu bersebelahan dengannya pada set bersebelahan.

• Tambah tepi antara bucu menggunakan teknik berikut:

  Kumpul objek bucu untuk bucu sumber dan destinasi.

  Sertakan bucu sasaran dalam set bersebelahan bucu sumber.

• Melaksanakan teknik penyingkiran tepi berikut:

  Kumpul objek bucu untuk bucu sumber dan sasaran.

  Alih keluar bucu sasaran daripada set bersebelahan bucu sumber.

• Laksanakan teknik lain yang diperlukan untuk operasi graf, seperti menentukan sama ada kelebihan wujud dan mendapatkan jiran bucu.

Contoh

#include <iostream>
#include <unordered_map>
#include <unordered_set>

class Graph {
private:
    std::unordered_map<int, std::unordered_set<int>> adjacencySets;

public:
    void addEdge(int source, int destination) {
        adjacencySets[source].insert(destination);
        adjacencySets[destination].insert(source); // If the graph is undirected, add both edges
    }

    void removeEdge(int source, int destination) {
        adjacencySets[source].erase(destination);
        adjacencySets[destination].erase(source); // If the graph is undirected, remove both edges
    }

    void printNeighbors(int vertex) {
        std::cout << "Neighbors of vertex " << vertex << ": ";
        for (int neighbor : adjacencySets[vertex]) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    Graph graph;

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

    graph.printNeighbors(1);
    graph.printNeighbors(3);

    graph.removeEdge(2, 3);

    graph.printNeighbors(1);
    graph.printNeighbors(3);

    return 0;
}

Output

Neighbors of vertex 1: 3 2 
Neighbors of vertex 3: 4 2 1 
Neighbors of vertex 1: 3 2 
Neighbors of vertex 3: 4 1

Perwakilan senarai terpaut

Setiap bucu dalam perwakilan terpaut graf diwakili sebagai nod dalam senarai terpaut. Struktur graf dibentuk oleh nod ini, yang disambungkan antara satu sama lain melalui penunjuk atau rujukan dan menyimpan data tentang bucu. Setiap nod juga mempunyai senarai terpaut atau struktur data dinamik lain yang menyimpan bucu bersebelahan tepi. Pendekatan ini secara berkesan menggambarkan graf jarang dengan tahap ketersambungan yang berbeza. Ia menyokong seni bina graf dinamik dan membenarkan penambahan dan penyingkiran tepi yang mudah. Walau bagaimanapun, ia mungkin mempunyai beban ingatan yang lebih besar sedikit daripada perwakilan lain. Terdapat kelebihan untuk menggunakan perwakilan terpaut apabila fleksibiliti dan kecekapan memori adalah pertimbangan utama.

Algoritma

• Cari nod graf yang sepadan dengan bucu 1 dalam pokok.

• Jika nod tidak ditemui, buat nod baharu untuk vertex1 dan tambahkannya pada graf.

• Dalam graf, cari nod yang sepadan dengan bucu 2.

• Jika nod tidak ditemui, buat nod baharu untuk vertex2 dan tambahkannya pada graf.

• Untuk mewakili tepi, tambah bucu2 pada senarai terpaut nod yang sepadan dengan bucu1.

• Dalam graf tidak terarah, pautkan bucu1 ke senarai bucu2 yang dipautkan.

Contoh

#include <iostream>
#include <unordered_map>
#include <list>

void AddEdge(std::unordered_map<int, std::list<int>>& graph, int vertex1, int vertex2) {
    graph[vertex1].push_back(vertex2);
    graph[vertex2].push_back(vertex1);
}

int main() {
    std::unordered_map<int, std::list<int>> graph;

    AddEdge(graph, 1, 2);
    AddEdge(graph, 1, 3);
    AddEdge(graph, 2, 3);

    for (const auto& entry : graph) {
        std::cout << "Vertex " << entry.first << " is connected to: ";
        for (int neighbor : entry.second) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Output

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

Apl

• Carta digunakan untuk mensimulasikan sambungan pengguna pada platform media sosial, membolehkan anda mengkaji interaksi sosial dan mengenal pasti komuniti.

• Carta sangat berguna dalam pengoptimuman laluan, pengiraan laluan terpendek dan mereka bentuk rangkaian pengangkutan yang cekap.

• Topologi rangkaian diwakili secara grafik, yang sangat membantu untuk reka bentuk rangkaian, analisis dan penyelesaian masalah.

• Diagram mensimulasikan laluan metabolik, interaksi protein dan sambungan gen untuk membantu dalam mengkaji sistem biologi.

• Graf digunakan dalam enjin pengesyoran untuk memberikan pengesyoran untuk produk, filem atau bahan lain berdasarkan pilihan pengguna dan perhubungan item.

• Mereka membolehkan sistem carian dan soal jawab pintar dengan menstruktur dan menghubungkan maklumat.

• Pengesanan penipuan, penilaian risiko dan pengoptimuman portfolio semuanya menggunakan grafik.

• Teknik berasaskan graf digunakan untuk masalah termasuk ramalan pautan, pengelasan dan pengelompokan.

• Rajah menjadikannya lebih mudah untuk memahami pautan antara peranti IoT dan aliran data, dengan itu memudahkan analisis dalam aplikasi IoT.

• Tingkatkan cerapan perubatan dengan carta yang menyokong penyelidikan perubatan tentang interaksi ubat, pemantauan pesakit dan pemodelan penyakit.

Kelebihan

• Carta menyediakan perwakilan visual data yang ringkas dan mudah difahami, menjadikan perkaitan dan perhubungan yang kompleks lebih mudah difahami.

• Melalui carta, pengecaman corak, analisis aliran dan pengesanan anomali boleh dicapai, dengan itu meningkatkan kebolehan membuat keputusan dan menyelesaikan masalah.

• Untuk memproses dan mentafsir data dengan cekap, carta memaparkan pelbagai struktur data untuk mensimulasikan situasi dunia sebenar yang kompleks dengan tepat.

• Apabila bekerja dengan data yang saling berkait dalam pangkalan data, topologi berasaskan graf membolehkan pengambilan dan traversal data mungkin.

• Carta sering digunakan dalam analisis rangkaian sosial untuk memahami interaksi sosial dan mengenal pasti nod atau pengguna yang menonjol.

• Carta amat berguna dalam menentukan laluan terpantas atau paling cekap dalam pengangkutan dan logistik.

• Enjin pengesyoran dipacu graf menyediakan pengesyoran untuk barangan, perkhidmatan atau maklumat berdasarkan gelagat dan pilihan pengguna.

• Gambar rajah boleh mewakili pengetahuan dan maklumat dalam cara hierarki, yang menjadikannya sangat berguna dalam aplikasi kecerdasan buatan dan rangkaian semantik.

• Gunakan teknik pembelajaran mesin berasaskan graf untuk melaksanakan tugas seperti pengelompokan, pengelasan dan ramalan pautan pada data berstruktur.

• Mencari padanan terbaik atau kerja penjadualan yang cekap hanyalah dua contoh banyak cabaran yang boleh diselesaikan oleh algoritma graf.

Keburukan

• Apabila berurusan dengan set data yang besar atau kehadiran sejumlah besar nod dan tepi, graf boleh menjadi tidak terurus dan kompleks. Oleh kerana kerumitan ini, mungkin sukar untuk menganalisis dan memahami data sepenuhnya.

• Menyimpan graf boleh menggunakan banyak memori, terutamanya untuk graf padat dengan banyak nod dan tepi. Apabila grafik semakin besar, penggunaan memori boleh menjadi isu.

• Mencari laluan terpendek dalam graf besar, sebagai contoh, boleh menjadi tugas yang memakan masa dan intensif dari segi pengiraan. Ini boleh menyebabkan masalah prestasi, terutamanya dalam aplikasi masa nyata.

• Graf boleh mempunyai pelbagai struktur, dengan sesetengah nod jauh lebih bersambung berbanding yang lain. Oleh kerana ketidakhomogenan ini, mungkin sukar untuk menggunakan teknik biasa atau membuat inferens berguna daripada data.

• Apabila berurusan dengan graf berdimensi tinggi, memvisualisasikan graf kompleks boleh menjadi mencabar dan data asas mungkin tidak diwakili dengan jelas.

• Data yang tiada atau salah boleh menyebabkan ketidakkonsistenan dalam carta, menjejaskan kualiti dan kebolehpercayaan analisis anda.

KESIMPULAN

Gambar rajah adalah alat yang fleksibel dan kerap digunakan dalam pelbagai disiplin, seperti biologi, pengangkutan dan rangkaian sosial. Ia adalah alat yang berguna untuk analisis data kerana mereka boleh menggambarkan hubungan yang kompleks dan mencari corak. Walau bagaimanapun, pemprosesan set data yang besar boleh menjadi rumit dan memerlukan lebih banyak memori. Selain itu, mencipta carta memerlukan masa dan pengetahuan. Walaupun terdapat kekurangan ini, gambar rajah masih merupakan alat yang berguna untuk menyelesaikan masalah dan membuat keputusan. Dengan menggunakan perwakilan yang sesuai (seperti set dan perwakilan pautan) dan melaksanakan algoritma yang cekap, rajah boleh terus memberikan cerapan dan sokongan yang berguna dalam pelbagai aplikasi merentas pelbagai disiplin.

Atas ialah kandungan terperinci Aplikasi, kebaikan dan keburukan carta. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!