2025年sicily1003. 有向图边的分类

科技前沿 • 2025-03-23 18:40 • 阅读 34

大家好，我是讯享网，很高兴认识大家。

有向图边的分类

上网查到，有向图边分四种，分别为：
我们在做dfs的时候，当访问到一个节点时，会出现四种情况：
1.此节点未被访问过，则此次的访问关系边（发起点——>接受点）称为树边（tree edge）；
2.此节点被访问过但此节点的子孙还没访问完，换句话说，此次的发起点的源头可以追溯到接收点，则此次访问关系边称为后向边（back edge）；
3.此节点被访问过且此节点的子孙已经访问完，而且发起点是搜索初始边，则称为前向边（down edge）；
4.此节点被访问过且此节点的子孙已经访问完，而且发起点不是搜索初始边，则称为横叉边（cross edge）。
其实这种分类只是相对的，也会随着dfs的改变而改变，比如搜索入口、搜索顺序等。

讯享网

直观理解

当访问到一个节点时，
令：
命题a为”节点被访问过”，
命题b为“此次的发起点的源头可以追溯到接收点”，
命题c为“发起点是搜索初始边”
上诉四种情况的关系可以这样简介地表达：
示意图
则

源代码

// source: http://soj.sysu.edu.cn/show_problem.php?pid=1003&cid=2387 #include <iostream> #include <cstring> #include <queue> #include <string> using namespace std; bool isVisited[101]; bool adjMatrix [101][101]; int edgeKind[101][101]; int verticeNum, edgeNum; // bool bfsFoundTarget; bool isAllSpringsVisited(int nodeToVisit); bool isSearchStartEdge(int u, int v) { 
  
    
  return 1 == u;} void dfs(int begin); int main() { cin >> verticeNum >> edgeNum; memset(edgeKind, -1, (verticeNum+1)*(verticeNum+1)*sizeof(int)); memset(adjMatrix, false, 101*101*sizeof(bool)); memset(isVisited, false, 101*sizeof(bool)); int a, b; for (int i = 0; i < edgeNum; i++) { cin >> a >> b; adjMatrix[a][b] = true; } isVisited[1] = true; dfs(1); int n; cin >> n; string str[4] = { 
  
    
  "Tree Edge", "Back Edge", "Down Edge", "Cross Edge"}; while(n--) { cin >> a >> b; cout << "edge (" << a << ',' << b << ") is " << str[edgeKind[a][b]] << endl; } return 0; } bool isAllSpringsVisited(int nodeToVisit) { for (int i = 1; i <= verticeNum; i++) { if (adjMatrix[nodeToVisit][i] && !isVisited[i]) { return false; } } return true; } void dfs(int begin) { for (int i = 1; i <= verticeNum; i++) { // edge exist if (adjMatrix[begin][i]) { // node not visited: tree edge & dfs  if (!isVisited[i]) { edgeKind[begin][i] = 0; isVisited[i] = true; dfs(i); } else { // node visited // not all spring visited : back edge  if (!isAllSpringsVisited(i)) { isVisited[i] = true; edgeKind[begin][i] = 1; } else { // all spring visited isVisited[i] = true; // the edge begin from the initial start node: down tree; if (isSearchStartEdge(begin, i)) { edgeKind[begin][i] = 2; } else { // the edge not begin from the initial start node: cross tree; edgeKind[begin][i] = 3; } isVisited[i] = true; } } } } }

讯享网

2025年sicily1003. 有向图边的分类

有向图边的分类

直观理解

源代码

相关推荐