C++ 稠密图

2025年3月17日 | 阅读 12 分钟

引言

图属于计算机科学和数学中的基本元素，它们表示由节点连接的网络。在图论中，图被进一步细分为连接较少和连接较多的图，以帮助确定要使用的正确算法和数据结构。本文重点介绍稠密图、它们的特性、挑战以及在 C++ 中的应用。

什么是稠密图？

稠密图 是一种图，其边的数量接近图中的最大可能数量。在简单的无向图中，最大边数由公式给出

其中 V 是顶点的数量。如果边的数量 E 是 O(V^2) 的数量级，则该图是稠密的。例如，完全图被认为是基本的稠密图，其中每对不同的顶点都由一条边连接。

问题陈述

对于稠密图，由于边数显着增多，表示和算法非常重要。问题是如何快速且以内存和处理时间有效的方式进行边添加、删除和遍历等操作。本文涵盖了 C++ 中稠密图的实际实现，重点关注理论方面和实际编码技术。

邻接矩阵

在稠密图的情况下，邻接矩阵起着非常重要的作用，因为

快速查找边： 在 O(1) 时间内确定两个顶点之间是否存在边非常简单。
边添加和删除： 这两项操作也可以在 O(1) 时间内完成。

尽管如此，邻接矩阵会消耗 O(V^2) 的内存，这在大型图的情况下尤其显着。

C++ 中的示例实现

程序 1

下面是使用邻接矩阵在 C++ 中实现稠密图的简单示例。

 
#include <iostream>
#include <vector>

class DenseGraph {
public:
    // Constructor


    DenseGraph(int vertices) : V(vertices), adjMatrix(vertices, std::vector<bool>(vertices, false)) {}

    // Add an edge
    void addEdge(int u, int v) {
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjMatrix[u][v] = true;
            adjMatrix[v][u] = true; // For undirected graph
        }
    }

    // Remove an edge
    void removeEdge(int u, int v) {
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjMatrix[u][v] = false;
            adjMatrix[v][u] = false; // For undirected graph
        }
    }

    // Check if there is an edge
    bool hasEdge(int u, int v) const {
        return u >= 0 && u < V && v >= 0 && v < V && adjMatrix[u][v];
    }

    // Print the adjacency matrix
    void printGraph() const {
        for (const auto& row : adjMatrix) {
            for (bool cell : row) {
                std::cout << cell << " ";
            }
            std::cout << std::endl;
        }
    }

private:
    int V; // Number of vertices
    std::vector<std::vector<bool>> adjMatrix; // Adjacency matrix
};

int main() {
    DenseGraph g(5); // Create a graph with 5 vertices

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

    std::cout << "Adjacency Matrix:" << std::endl;
    g.printGraph();

    std::cout << "Edge between 0 and 1: " << (g.hasEdge(0, 1) ? "Yes" : "No") << std::endl;

    return 0;
}   

输出

 
Adjacency Matrix:
0 1 1 0 0 
1 0 1 0 0 
1 1 0 0 0 
0 0 0 0 1 
0 0 0 1 0 
Edge between 0 and 1: Yes

说明

构造函数： 它创建一个具有 ? 个顶点的图。邻接矩阵的维度为 ?×?，所有位置都填充为 false，表示没有边。
添加边： 它通过将邻接矩阵中的相应位置更改为 true 来在顶点 u 和 v 之间创建一条无向边。
删除边： 它通过将邻接矩阵中的相应位置更改为 false 来删除连接顶点 u 和 v 的边。
是否包含边： 它通过访问邻接矩阵中的相应位置来确定顶点 u 和 v 之间是否存在一个连接的边。
打印图： 它显示了邻接矩阵，其中包含到顶点的边的确定，其中 1（true）表示存在边，0（false）表示不存在边。
在 main 函数中，它构建了一个具有 5 个顶点的 DenseGraph，添加了边，显示了图，并验证了顶点 0 和 1 之间是否存在边。

时间和空间复杂度

时间复杂度： O(V^2)
空间复杂度： O(V^2)

程序 2

如上所示，使用邻接矩阵可以构建和处理高密度图，同时确保图实现的简单性。

 
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>

class DenseGraph {
public:
    // Constructor
    DenseGraph(int vertices) : V(vertices), adjMatrix(vertices, std::vector<int>(vertices, -1)) {}

    // Destructor
    ~DenseGraph() = default;

    // Add an edge with weight
    void addEdge(int u, int v, int weight = 1) {
        if (isValidVertex(u) && isValidVertex(v)) {
            adjMatrix[u][v] = weight;
            adjMatrix[v][u] = weight; // For undirected graph
        }
    }

    // Remove an edge
    void removeEdge(int u, int v) {
        if (isValidVertex(u) && isValidVertex(v)) {
            adjMatrix[u][v] = -1;
            adjMatrix[v][u] = -1; // For undirected graph
        }
    }

    // Check if there is an edge
    bool hasEdge(int u, int v) const {
        return isValidVertex(u) && isValidVertex(v) && adjMatrix[u][v] != -1;
    }

    // Get weight of an edge
    int getEdgeWeight(int u, int v) const {
        if (isValidVertex(u) && isValidVertex(v)) {
            return adjMatrix[u][v];
        }
        return -1;
    }

    // Print the adjacency matrix
    void printGraph() const {
        for (const auto& row : adjMatrix) {
            for (int weight : row) {
                if (weight == -1) {
                    std::cout << "INF ";
                } else {
                    std::cout << weight << " ";
                }
            }
            std::cout << std::endl;
        }
    }

    // Depth-First Search (DFS)
    void DFS(int start) const {
        if (!isValidVertex(start)) return;

        std::vector<bool> visited(V, false);
        std::stack<int> stack;
        stack.push(start);

        while (!stack.empty()) {
            int vertex = stack.top();
            stack.pop();

            if (!visited[vertex]) {
                visited[vertex] = true;
                std::cout << vertex << " ";

                // Push all unvisited adjacent vertices
                for (int i = 0; i < V; ++i) {
                    if (adjMatrix[vertex][i] != -1 && !visited[i]) {
                        stack.push(i);
                    }
                }
            }
        }
        std::cout << std::endl;
    }

    // Breadth-First Search (BFS)
    void BFS(int start) const {
        if (!isValidVertex(start)) return;

        std::vector<bool> visited(V, false);
        std::queue<int> queue;
        queue.push(start);
        visited[start] = true;

        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            std::cout << vertex << " ";

            // Queue all unvisited adjacent vertices
            for (int i = 0; i < V; ++i) {
                if (adjMatrix[vertex][i] != -1 && !visited[i]) {
                    queue.push(i);
                    visited[i] = true;
                }
            }
        }
        std::cout << std::endl;
    }

    // Resize the graph
    void resize(int newSize) {
        if (newSize <= V) {
            std::cerr << "New size must be greater than the current size!" << std::endl;
            return;
        }

        // Resize the matrix
        adjMatrix.resize(newSize);
        for (auto& row : adjMatrix) {
            row.resize(newSize, -1);
        }

        // Initialize new edges to -1 (infinity or no connection)
        for (int i = 0; i < V; ++i) {
            adjMatrix[i].resize(newSize, -1);
        }

        V = newSize;
    }

private:
    int V; // Number of vertices
    std::vector<std::vector<int>> adjMatrix; // Adjacency matrix with weights

    // Check if vertex is valid
    bool isValidVertex(int vertex) const {
        return vertex >= 0 && vertex < V;
    }
};

int main() {
    DenseGraph g(5); // Create a graph with 5 vertices

    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 20);
    g.addEdge(1, 2, 30);
    g.addEdge(3, 4, 40);

    std::cout << "Adjacency Matrix:" << std::endl;
    g.printGraph();

    std::cout << "DFS starting from vertex 0:" << std::endl;
    g.DFS(0);

    std::cout << "BFS starting from vertex 0:" << std::endl;
    g.BFS(0);

    std::cout << "Resizing the graph to 7 vertices." << std::endl;
    g.resize(7);

    std::cout << "Adjacency Matrix after resizing:" << std::endl;
    g.printGraph();

    return 0;
}   

输出

 
Adjacency Matrix:
INF 10 20 INF INF 
10 INF 30 INF INF 
20 30 INF INF INF 
INF INF INF INF 40 
INF INF INF 40 INF 
DFS starting from vertex 0:
0 2 1 
BFS starting from vertex 0:
0 1 2 
Resizing the graph to 7 vertices.
Adjacency Matrix after resizing:
INF 10 20 INF INF INF INF 
10 INF 30 INF INF INF INF 
20 30 INF INF INF INF INF 
INF INF INF INF 40 INF INF 
INF INF INF 40 INF INF INF 
INF INF INF INF INF INF INF 
INF INF INF INF INF INF INF

说明

带权邻接矩阵： 在图中，添加了带有权重的边，其权重由整数表示。初始权重 -1 表示没有边。
深度优先搜索和广度优先搜索算法： 这两种算法都用于探索图结构，直到列出所有顶点，并按照它们被访问的顺序进行。DFS 使用栈，而 BFS 使用队列。
图重 sizing： 当新边被分配权重 -1 时，resize 函数可以增加图的当前大小。这在各种图情况下特别有益，尤其是动态图。
错误处理和验证： 包含对边的一些基本检查，特别是 resizing、添加和删除边，以确保执行的操作在某些合理限制内。

时间和空间复杂度

时间复杂度： 大多数操作，如添加、删除和检查边，都是 O(1)。大多数遍历算法，即 DFS、BFS 和图打印算法，复杂度为 O(V^2)，图 resizing 也为 O(V^2)。
空间复杂度： 邻接矩阵占用的空间部分大小为 O(V^2)。对于深度优先搜索和广度优先搜索，Auxiliary 结构（如栈、队列和已访问向量）使用 O(V) 空间。

程序 3

 
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

class DirectedDenseGraph {
public:
    // Constructor
    DirectedDenseGraph(int vertices) : V(vertices), adjMatrix(vertices, std::vector<int>(vertices, INF)) {}

    // Destructor
    ~DirectedDenseGraph() = default;

    // Add an edge with weight
    void addEdge(int u, int v, int weight) {
        if (isValidVertex(u) && isValidVertex(v)) {
            adjMatrix[u][v] = weight;
        }
    }

    // Remove an edge
    void removeEdge(int u, int v) {
        if (isValidVertex(u) && isValidVertex(v)) {
            adjMatrix[u][v] = INF;
        }
    }

    // Check if there is an edge
    bool hasEdge(int u, int v) const {
        return isValidVertex(u) && isValidVertex(v) && adjMatrix[u][v] != INF;
    }

    // Get weight of an edge
    int getEdgeWeight(int u, int v) const {
        if (isValidVertex(u) && isValidVertex(v)) {
            return adjMatrix[u][v];
        }
        return INF;
    }

    // Print the adjacency matrix
    void printGraph() const {
        for (const auto& row : adjMatrix) {
            for (int weight : row) {
                if (weight == INF) {
                    std::cout << "INF ";
                } else {
                    std::cout << weight << " ";
                }
            }
            std::cout << std::endl;
        }
    }

    // Dijkstra's Algorithm to find shortest paths from a given source
    void dijkstra(int start) const {
        if (!isValidVertex(start)) return;

        std::vector<int> dist(V, INF);
        std::vector<bool> visited(V, false);
        dist[start] = 0;

        using Pair = std::pair<int, int>;
        // Specify the type for std::greater
        std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            if (visited[u]) continue;
            visited[u] = true;

            for (int v = 0; v < V; ++v) {
                if (adjMatrix[u][v] != INF && !visited[v]) {
                    int newDist = dist[u] + adjMatrix[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.push({dist[v], v});
                    }
                }
            }
        }

        // Output shortest distances from source
        std::cout << "Shortest distances from vertex " << start << ":" << std::endl;
        for (int i = 0; i < V; ++i) {
            if (dist[i] == INF) {
                std::cout << "Vertex " << i << ": INF" << std::endl;
            } else {
                std::cout << "Vertex " << i << ": " << dist[i] << std::endl;
            }
        }
    }

private:
    int V; // Number of vertices
    std::vector<std::vector<int>> adjMatrix; // Adjacency matrix with weights
    const int INF = std::numeric_limits<int>::max(); // Represents infinity

    // Check if vertex is valid
    bool isValidVertex(int vertex) const {
        return vertex >= 0 && vertex < V;
    }
};

int main() {
    DirectedDenseGraph g(5); // Create a graph with 5 vertices

    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 1, 4);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 4, 2);
    g.addEdge(3, 4, 7);
    g.addEdge(4, 3, 9);

    std::cout << "Adjacency Matrix:" << std::endl;
    g.printGraph();

    std::cout << std::endl;
    g.dijkstra(0); // Run Dijkstra's algorithm from vertex 0

    return 0;
}   

输出

 
Adjacency Matrix:
4214880 10 3 4214880 4214880 
4214880 4214880 1 2 4214880 
4214880 4 4214880 8 2 
4214880 4214880 4214880 4214880 7 
4214880 4214880 4214880 9 4214880 

Shortest distances from vertex 0:
Vertex 0: 0
Vertex 1: 7
Vertex 2: 3
Vertex 3: 9
Vertex 4: 5

说明

图的表示
- 邻接矩阵： 我们使用二维向量表示矩阵，初始化为 INF（无穷大）以表示没有连接。对于有向图，矩阵不对称。
边操作
- 添加边： 设置从 u 到 v 的边的权重。
- 删除边： 将权重重置为 INF，表示没有连接。
- 检查边： 如果存在权重不等于 INF 的边，则返回 true。
最短路径算法
- Dijkstra 算法： 从源顶点到所有其他顶点的最短路径。我们使用优先队列（最小堆）来有效地获取具有最小距离的下一个顶点。
图输出和遍历
- 打印图： 显示邻接矩阵。
- Dijkstra 最短路径输出： 打印从源顶点的最短距离。

时间和空间复杂度

时间复杂度： 很容易看出，由于优先队列操作和图遍历，在稠密图中唯一耗时的活动是 Dijkstra 算法。因此，总体时间复杂度变为 O(V^2 log V)。
空间复杂度： 从邻接矩阵计算，加上 Dijkstra 算法中距离向量、已访问向量和优先队列等其他附加内存所需的 O(V) 空间，使空间复杂度为 O(V^2)。

稠密图的优点

高连接性
- 健壮的网络： 稠密图连接性好，边连接了大部分顶点对。这种高连接性可以创建更可靠、更健壮的网络，因为节点有多种相互连接的方式。
- 冗余： 高连接性允许冗余，这在通信网络中尤其有利，因为其他路由将提高网络的抗故障能力。
某些问题的有效算法
- Floyd-Warshall 算法： 对于稠密图，像 Floyd-Warshall 这样的算法用于查找所有顶点对之间的最短路径，效率很高，因为邻接矩阵表示非常适合此类算法。
- 矩阵运算： 稠密图可以利用基于矩阵的运算进行各种计算，包括谱图理论和网络流问题。
图遍历算法性能更好
- 广度优先搜索 (BFS) 和深度优先搜索 (DFS)： 对于稠密图，由于边密度高，遍历算法可能更直接，有时更快，这减少了复杂边查找的需要。
表示和实现简单
- 打印邻接矩阵： 稠密图的邻接矩阵表示通常适用的情况，由于结构复杂性较低且易于访问边进行存在性查询，因此提高了实现各种算法的效率。
- 易于实现： 稠密图配置方便，有多个链接，减少了对复杂数据结构的需求，并避免了稀疏连接图的问题。

稠密图的应用

提高需要边检查的应用的效率
- 更快的边查询： 经常需要完全访问边并进行边存在性检查的应用程序，可以使用邻接矩阵很好地服务，该矩阵允许在恒定时间内查找边，尤其是在稠密图中，其中大多数边都可能是存在的。
处理近乎完整或完整的图
- 完整图： 像完全图这样的稠密图，其中图中任何两个顶点都通过一条边连接，在需要保证完全连接图的情况下得到利用。这些类型的网络也用于网络优化和各种理论问题。
某些网络中的用例可能包括以下用途
- 社交网络： 在社交网络的背景下，稠密图用于对具有许多连接（边）的聚集的参与者（顶点）进行建模。
- 生物网络： 高密度图还可以表示生物网络中的复杂系统，例如蛋白质-蛋白质相互作用网络，其中许多蛋白质在与其他蛋白质连接之前会相互连接。
强大的图属性
- 强连通性： 这也意味着稠密图通常是强连通的，即从一个顶点到另一个顶点有不止一种方式，这提高了图的整体结构的强度。
- 聚类： 通常，稠密图的聚类系数会很高，因为某些顶点的邻居很可能成为彼此的邻居，这在社区检测和聚类等领域很有用。

结论

总之，边相对于顶点数量很多的稠密图既有优点也有挑战。稠密图可以使用邻接矩阵充分表示，这可以确保快速的边操作，但会增加内存需求。在 C++ 中采用稠密图表示需要能够理解这些因素并加以缓解的高效包装器。随着图的规模和应用的增加，优化内存和性能总是至关重要的。

下一个主题C++ 中的享元模式

← 上一个下一个 →

C++ 稠密图

引言

什么是稠密图？

问题陈述

邻接矩阵

C++ 中的示例实现

程序 1

说明

时间和空间复杂度

程序 2

说明

时间和空间复杂度

程序 3

说明

时间和空间复杂度

稠密图的优点

稠密图的应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 稠密图

引言

什么是稠密图？

问题陈述

邻接矩阵

C++ 中的示例实现

程序 1

说明

时间和空间复杂度

程序 2

说明

时间和空间复杂度

程序 3

说明

时间和空间复杂度

稠密图的优点

稠密图的应用

结论

相关帖子

C++ 与 Haskell 的区别

C++ std::knuth_b

C++ wcspbrk() 函数