为了确定在图表中形成三角形所需的最少边数，我们分析了中心之间的网络。在三个轮毂专门关联或通过边缘以迂回方式关联的情况下，可以形成三角形。所需的最小边数等于三个集线器之间现有连接中丢失的边数。通过查看图表并区分不相关的中心，我们可以计算形成三角形所需的额外边的数量。这种方法有所不同，因为它需要最少的调整来在图表中的中心之间建立三角关系。
使用的方法
-
图遍历方法
图遍历方法
用于查找创建三角形所需的最少边数的图遍历方法涉及使用深度优先查找 (DFS) 或广度优先查找 (BFS) 等遍历计算来研究图表。从图表中的每个中心开始，我们导航其相邻的中心并检查相邻中心的任何匹配之间是否存在长度为 2 的路径。如果找到了这样的方法，我们就找到了一个三角形。通过对所有中心重新进行这一准备工作，我们将决定在图表中形成至少一个三角形所需的最少额外边数。这种方法有效地研究了图表结构，以区分三角形并最大限度地减少包含的边数。
算法
-
制作图表的传染性列表或网格表示。
-
初始化变量 minMissing 以存储最少数量的丢失边。
-
迭代图表中的每个中心：
-
利用深度优先查找 (DFS) 或广度优先查找 (BFS) 从当前中心开始图表遍历。
-
对于当前枢纽的每个相邻枢纽 j，导航其邻居 k 并检查 j 和 k 之间是否存在边缘。
-
如果 j 和 k 之间没有边，则通过从 3 中减去现有边的数量来计算创建三角形时丢失的边的数量。
-
使用当前丢失边缘最少的 minMissing 和 minMissing 来升级 minMissing。
-
对所有中心进行重复操作后，minMissing 的值将表示创建三角形所需的最少边数。
-
返回minMissing的尊重。
示例
#include
#include
#include
int minimumMissingEdges(std::vector& 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 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 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 graph = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
int minMissingEdges = minimumMissingEdges(graph);
std::cout
