C++ 图的应用、优势和劣势

图在不同的学科中被使用。它们被用于生物学中表示基因相互作用，用于交通运输中进行路径优化，以及用于社交网络中的用户连接分析。图的可视化表示复杂关系和观察模式和趋势的能力是图的两个优势。然而，处理大型数据集可能会使图变得臃肿和难以理解。此外，创建图需要时间和专业知识。尽管存在这些缺点，图仍然是跨学科数据分析和决策制定的有效工具。

使用的方法

集合表示
连接表示
顺序表示

集合表示

在图的集合表示中，图中的每个顶点与一个包含其周围顶点的集合相关联。在这种方法中，图的边缘被存储在包含集合的邻接集或哈希表中。每个顶点的集合确保没有重复的相邻顶点，并且能有效地管理稀疏图。与其他表示相比，添加和删除边更容易，内存利用率更低。当处理具有不同连接度的网络时，这种技术非常有帮助，因为它可以有效地执行诸如检查边缘和迭代邻近顶点等操作。

邻接集：在图的集合表示中，邻接集使用集合来记录每个顶点的相邻顶点，防止重复并促进对边的有效处理。
哈希表：哈希表在图的集合表示上使用，将每个顶点与包含其相邻顶点的集合链接起来。

步骤

图的顶点应该由一个类或数据结构表示。每个顶点对象需要有一个集合来包含其相邻顶点以及一个ID或标签。
创建一个空的存储空间来保存图的顶点（例如数组、向量或哈希表）。
对于图中的每个顶点：

为图中的每个顶点创建一个具有指定ID或标签的新顶点对象。

将与其相邻的顶点添加到邻接集中。

使用以下技术在顶点之间添加边：

获取源顶点和目标顶点的顶点对象。

将目标顶点包含在源顶点的邻接集中。

实现以下边缘删除技术：

获取源顶点和目标顶点的顶点对象。

将目标顶点从源顶点的邻接集中删除。

实现图操作所需的其他技术，例如确定边缘是否存在和获取顶点的相邻顶点。

示例

#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;
}

输出

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

链式表示法

图的链式表示法中，每个顶点在链表中表示为一个节点。这些节点构成了图的结构，通过指针或引用连接在一起，并保存有关顶点的数据。每个节点还有一个链表或其他动态数据结构，用于存储边的相邻顶点。这种方法能有效地描绘具有不同连通性水平的稀疏图。它支持动态图结构，允许简单地添加和删除边。然而，与其他表示法相比，它可能会有稍微更大的内存负担。当内存的灵活性和效率是最重要的考虑因素时，使用链式表示法是有优势的。

步骤

在树中定位与顶点1对应的图节点。
如果无法找到节点，则为顶点1创建一个新的节点并将其添加到图中。
在图中定位与顶点2对应的节点。
如果无法找到节点，则为顶点2创建一个新的节点并将其添加到图中。
将顶点2添加到与顶点1对应的节点的链表中，以表示边。
在无向图中，在链表中将顶点1链接到顶点2。

示例

#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;
}

输出

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

应用

图表用于模拟社交媒体平台上用户之间的连接，可用于研究社交互动和识别社区。
图表在路径优化、最短路径计算和有效交通网络设计中非常有用。
图表表示网络的拓扑结构，对网络设计、分析和故障排查有帮助。
图表模拟代谢途径、蛋白质相互作用和基因连接，以助于研究生物系统。
图表在推荐引擎中使用，根据用户偏好和物品关系进行商品、电影或其他材料的推荐。
通过结构化和连接信息，它们可以实现智能搜索和问答系统。
图表用于欺诈检测、风险评估和投资组合优化。
图表技术用于解决包括链接预测、分类和分组在内的问题。
图表使得理解物联网设备和数据流之间的链接更加容易，有助于物联网应用中的分析。
通过图表来支持药物相互作用、患者监测和疾病建模的医学研究能提高医疗洞察。

优势

图表提供了一种简单而易于理解的数据可视化表示方式，使复杂的链接和关系更易理解。
图表使得模式识别、趋势分析和异常检测成为可能，提高了决策和问题解决的能力。
为了高效地处理和解释数据，图表描绘了各种数据结构，准确模拟复杂的现实世界情况。
在与数据库中的相互连接数据工作时，基于图表的拓扑结构使数据检索和遍历成为可能。
图表经常用于社交网络分析，以理解社交互动并找出突出的节点或用户。
图表在交通和物流中确定最快或最有效的路线非常有用。
图表驱动推荐引擎，根据用户行为和偏好推荐商品、服务或信息。
图表可以以层次方式表示知识和信息，有助于人工智能和语义网络应用。
在结构化数据中，使用基于图表的机器学习技术进行聚类、分类和链接预测等任务。
发现最佳匹配或有效安排工作等许多挑战，都可以借助图算法来解决。

劣势

当处理庞大的数据集或存在大量节点和边时，图形变得难以管理和复杂。由于这种复杂性，会难以充分分析和理解数据。
存储图形可能会消耗大量内存，尤其是对于具有大量节点和边的稠密图形。随着图形的增大，内存使用可能成为一个问题。
搜索巨大图形中的最短路径可能是一项耗时且计算密集的任务。这可能导致性能问题，特别是在实时应用中。
图形可以具有各种结构，某些节点的连接明显多于其他节点。由于这种不均匀性，使用常见技术或从数据中推导出有用的推断可能会困难。
在处理高维图形时，将复杂的图形可视化可能是一项具有挑战性的任务，可能无法清晰地表示底层数据。
缺失或错误的数据可能导致图形中出现不一致，这可能会损害分析的质量和可靠性。

综述

图形在生物学、交通运输和社交网络等各个学科中是灵活且经常使用的。它们是数据分析的有用工具，因为它们可以可视化复杂的关系并找到模式。然而，处理大型数据集可能变得复杂，并且需要更多的内存。此外，创建图形需要时间和知识。尽管存在这些缺点，图形仍然是解决问题和做出决策的有用工具。通过使用适当的表示（如集合和链接表示）并实施高效的算法，图形可以在各个学科的各种应用中继续提供有价值的见解和支持。