数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学满足路径包含顶点 A 和 B 的顶点对数
本文介绍了计算图中满足路径包含指定顶点 A 和 B 的顶点对数的方法。它首先使用深度优先搜索 (DFS) 算法遍历图的网络，并统计满足条件的顶点对。该算法执行两次独立的 DFS 遍历。第一次遍历移除顶点 B，并计算从顶点 A 可到达的顶点数；第二次遍历移除顶点 A，并计算从顶点 B 可到达的顶点数。然后，将每次遍历中可到达的顶点数从图的总顶点数中减去，得到分别排除 A 和 B 后不可到达的顶点数。最后，将这两个计数相加，得到满足条件的顶点对总数。
使用的方法
深度优先搜索 (DFS)
广度优先搜索 (BFS)
深度优先搜索 (DFS)
给定的代码使用基于深度优先搜索的方法。首先，使用 DFS 查找满足路径包含两个给定顶点的顶点对数量。它使用 DFS 计算从特定顶点可达到的顶点数，同时排除另一个给定顶点。通过执行两次 DFS（一次移除顶点 B，一次移除顶点 A），代码计算在每种情况下无法到达的顶点数。最终结果是这两个计数的乘积。这种方法利用 DFS 遍历图的网络，并检查在移除所需顶点后无法到达的顶点数。然后，计算满足给定条件的顶点对总数。
算法
从给定的图开始，用邻接表表示。
将计数变量 (cnt) 初始化为 0。
初始化一个访问数组 (vis) 来跟踪已访问的顶点。将所有顶点标记为未访问。
从顶点 A 开始执行深度优先搜索 (DFS)。
将顶点 A 标记为已访问。
将 cnt 变量加 1。
对于 A 的每个相邻顶点 (neighbor)
如果邻居未访问且未到达顶点 B，则递归调用 DFS 函数处理邻居。
从顶点 A 开始的 DFS 完成后，将 cnt 的值存储在一个变量 (count1) 中。
重置访问数组 (vis) 和 cnt 为 0。
从顶点 B 开始执行另一个 DFS。
将顶点 B 标记为已访问。
将 cnt 变量加 1。
对于 B 的每个相邻顶点 (neighbor)
如果邻居未访问且未到达顶点 A，则递归调用 DFS 函数处理邻居。
从顶点 B 开始的 DFS 完成后，将 cnt 的值存储在另一个变量 (count2) 中。
计算结果：count1 乘以 count2。
输出结果，即满足路径包含顶点 A 和 B 的顶点对数。
示例
#include <iostream>
#include <vector>
using namespace std;
int num_vertices, num_edges, a, b;
// Function to perform DFS on the given graph
// starting from the vertex 'start'
int performDFS(int start, int target, vector<int> graph[], vector<bool>& visited)
{
visited[start] = true;
int count = 1;
// Perform DFS on the adjacent vertices
for (auto adjacent : graph[start]) {
if (!visited[adjacent] && adjacent != target)
count += performDFS(adjacent, target, graph, visited);
}
return count;
}
// Function to calculate the number of pairs
// such that the path between any two pairs
// contains the given two vertices A and B
int calculatePairs(vector<int> graph[])
{
vector<bool> visited(num_vertices + 1, false);
int count_a = performDFS(a, b, graph, visited);
visited.assign(num_vertices + 1, false);
int count_b = performDFS(b, a, graph, visited);
int ans1 = num_vertices - count_a - 1;
int ans2 = num_vertices - count_b - 1;
return ans1 * ans2;
}
int main()
{
num_vertices = 7, num_edges = 7, a = 3, b = 5;
int edges[][2] = { {1, 2},
{2, 3},
{3, 4},
{4, 5},
{5, 6},
{6, 7},
{7, 5} };
vector<int> graph[num_vertices + 1];
// Loop to create the graph
for (int i = 0; i < num_edges; i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
int result = calculatePairs(graph);
cout << "Number of pairs such that the path between each pair contains the vertices " << a << " and " << b << ": " << result << endl;
return 0;
}
输出
Number of pairs such that the path between each pair contains the vertices 3 and 5: 4
广度优先搜索 (BFS)
在广度优先搜索 (BFS) 方法中，我们以广度优先的方式遍历图。从给定的起始顶点开始，我们首先访问其所有邻居，然后移动到下一层邻居。我们使用队列来跟踪要访问的顶点。当我们访问每个顶点时，我们将其标记为已访问以避免重复访问。BFS 在查找两个顶点之间的最短路径方面非常有效，并且广泛用于图遍历和路径查找问题。它确保按与源的距离递增的顺序访问顶点。
算法
创建一个空队列和一个访问数组。
将源顶点入队并标记为已访问。
当队列不为空时，执行以下操作：
从队列的头部出队一个顶点。
处理出队的顶点（例如，打印它或执行所需的操作）。
将所有未访问的邻居入队并标记为已访问。
重复步骤 3 直到队列为空。
如果仍然有未访问的顶点，则返回步骤 2 并选择另一个未访问的顶点作为源。
当所有顶点都被访问后，终止算法。
示例
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void bfs(vector<vector<int>>& graph, int source) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int vertex = q.front();
q.pop();
cout << vertex << " "; // Process the visited vertex (e.g., print it)
for (int neighbor : graph[vertex]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
int numVertices = 6;
vector<vector<int>> adjacencyList(numVertices);
// Build the graph
adjacencyList[0] = {1, 2};
adjacencyList[1] = {3, 4};
adjacencyList[2] = {4, 5};
adjacencyList[3] = {5};
adjacencyList[4] = {};
adjacencyList[5] = {};
int source = 0;
bfs(adjacencyList, source);
return 0;
}
输出
0 1 2 3 4 5
结论
本文介绍了两种方法，深度优先搜索 (DFS) 和广度优先搜索 (BFS)，用于查找图中满足路径包含两个指定顶点 A 和 B 的顶点对数。DFS 方法执行两次独立的 DFS 遍历，分别移除顶点 A 或 B，以计算仍然可以到达的顶点数。BFS 方法以分层的方式遍历图，从给定的源顶点开始，以查找最短路径并访问所有可到达的顶点。这两种方法都提供了有效的分析图并根据给定条件计算所需顶点对的方法。
73 次浏览
