形成一个三角形所需添加的最小边数

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

int minimumMissingEdges(std::vector<std::vector<int>>& graph) {
    int minMissing = 3; // Variable to store the least number of lost edges

    // Iterate over each hub in the graph
    for (int hub = 0; hub < graph.size(); ++hub) {
        std::vector<bool> visited(graph.size(), false); // Mark nodes as unvisited
        int lostEdges = 0; // Number of lost edges to form a triangle

        // Begin chart traversal from the current hub utilizing Breadth-First Search (BFS)
        std::queue<int> q;
        q.push(hub);
        visited[hub] = true;

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

            // Check neighbors of the current hub
            for (int neighbor : graph[currentHub]) {
                // Check if there's an edge between the current hub and its neighbor
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                    // If there's no edge between the current hub and its neighbor, increment lostEdges
                    if (!graph[currentHub][neighbor]) {
                        lostEdges++;
                    }
                }
            }
        }

        // Update minMissing with the least of the current lost edges and minMissing
        minMissing = std::min(minMissing, lostEdges);
    }

    return minMissing;
}

int main() {
    // Example usage
    std::vector<std::vector<int>> graph = {
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };

    int minMissingEdges = minimumMissingEdges(graph);
    std::cout << "Minimum number of edges to form a triangle: " << minMissingEdges << std::endl;

    return 0;
}

Minimum number of edges to form a triangle: 0