C++ 程序构建具有特定条件的图

2025 年 3 月 24 日 | 4 分钟阅读

在本文中，我们将讨论一个 C++ 程序，用于构建满足特定条件的图。

图是基本的数据结构，用于显示实体之间的关系。在许多应用程序中，构建符合特定约束或要求的图至关重要。这些规范可能包括边权重、结构限制或连通性要求。这个 C++ 程序的目标是构建一个满足指定条件的图。这些规范可能与顶点的数量、特定边的存在或无环性或连通性等属性有关。根据约束和要求，程序可能会采用邻接矩阵和邻接表等图表示技术。

假设我们有两个数字 N 和 K。考虑一个包含 N 个元素的无向图。N 个顶点满足以下条件。它有以下条件：

该图是简单且连通的。
顶点的编号范围从 1 到 N。
设 M 为图中边的数量。对于边，编号从 1 到 M，即边的长度。此外，边 i 连接顶点 V[i] 和 顶点 U[i]。
对于每 K 对顶点 (i, j)，其中 i < j，它们的最短距离为 2。

示例 1

让我们举一个例子来说明如何在 C++ 中构建满足特定条件的图。

#include <bits/stdc++.h>
using namespace std;

void generateGraph(int numVertices, int numEdges){
   if (numEdges > (numVertices - 1) * (numVertices - 2) / 2){
      cout << "Cannot generate graph with " << numEdges << " edges for " << numVertices << " vertices." << endl;
      return;
   }
   cout << "Number of edges: " << (numVertices - 1) * (numVertices - 2) / 2 - numEdges + numVertices - 1 << '\n';
   for (int i = 1; i < numVertices; i++){
      cout << "Edge: 1 -> " << i + 1 << '\n';
   }
   int count = (numVertices - 1) * (numVertices - 2) / 2 - numEdges;
   for (int i = 2; i <= numVertices; i++){
      for (int j = i + 1; j <= numVertices; j++){
         if (count <= 0){
            return;
         }
         cout << "Edge: " << i << " -> " << j << '\n';
         count--;
      }
   }
}

int main(){
   int numVertices = 7;
   int numEdges = 10;
   generateGraph(numVertices, numEdges);
   return 0;
}

输出

Number of edges: 11
Edge: 1 -> 2
Edge: 1 -> 3
Edge: 1 -> 4
Edge: 1 -> 5
Edge: 1 -> 6
Edge: 1 -> 7
Edge: 2 -> 3
Edge: 2 -> 4
Edge: 2 -> 5
Edge: 2 -> 6
Edge: 2 -> 7

示例 2

让我们再举一个例子来说明如何在 C++ 中构建满足特定条件的图。

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

using namespace std;

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

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int src, int dest) {
        adj[src].push_back(dest);
        adj[dest].push_back(src); // for undirected graph
    }

    bool isConnected() {
        vector<bool> visited(V, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int i = 0; i < adj[current].size(); ++i) {
                int adjacentVertex = adj[current][i];
                if (!visited[adjacentVertex]) {
                    visited[adjacentVertex] = true;
                    q.push(adjacentVertex);
                }
            }
        }

        for (int i = 0; i < V; ++i) {
            if (!visited[i])
                return false; // Graph is not connected
        }
        return true; // Graph is connected
    }

    void printGraph() {
        cout << "Generated Graph:" << endl;
        for (int i = 0; i < V; ++i) {
            cout << "Vertex " << i << " -> ";
            for (int j = 0; j < adj[i].size(); ++j)
                cout << adj[i][j] << " ";
            cout << endl;
        }
    }
};

int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;

    Graph g(V);

    // Constructing a connected graph
    for (int i = 0; i < E; ++i) {
        int src, dest;
        cout << "Enter edge " << i+1 << " (source destination): ";
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    if (g.isConnected()) {
        cout << "Graph is connected." << endl;
        g.printGraph();
    } else {
        cout << "Cannot construct a connected graph with the given inputs." << endl;
    }

    return 0;
}

输出

Enter number of vertices: 4
Enter number of edges: 3
Enter edge 1 (source destination): 0 1
Enter edge 2 (source destination): 1 2
Enter edge 3 (source destination): 2 3
Graph is connected.
Generated Graph:
Vertex 0 -> 1 
Vertex 1 -> 0 2 
Vertex 2 -> 1 3 
Vertex 3 -> 2

下一主题Std-common-type-t1-t2-type-function-in-cpp

C++ 程序构建具有特定条件的图

示例 1

示例 2

联系信息

关注我们

教程

面试题

在线编译器

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++ 程序构建具有特定条件的图

示例 1

示例 2

相关帖子

C++ 中如何计算二维数组中数字的方差

C++ 中的拟完美数

C++ 翻转矩阵前传

C++ std::cyl_neumann

什么是引用变量

C++ std::this_thread::sleep_until() 函数

C++ 中二进制兼容性与源代码兼容性的区别

C++ 中的非斜边数

C++ 基于范围的 for 循环

C++ 模板特化与重载的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器