当前位置: 首页 > 知识库问答 >
问题:

在图中找到一个简单的循环并将其打印出来的算法

步兴德
2023-03-14

设G=(V, E)是一个简单的无向图。建议一种算法,在图中找到一些简单的循环并打印它(组成它的节点序列)。如果没有这样的循环,算法就不会打印任何东西。

算法:

  1. 启动一个大小为n的数组,并为每个顶点创建一个父变量。
  2. 在随机顶点上启动DFS,对于每个访问的顶点,在数组中标记“1”,并分配其父节点。
  3. 如果在DFS运行中,下一个顶点是已标记的顶点,而不是其父顶点-图形中有一个循环,并使用其父变量向后打印所有节点

算法正确吗?还是我需要改变什么?

谢谢!

共有1个答案

姜振濂
2023-03-14

根据图论,我们知道:

  1. 如果图的顶点数量大于边的数量,那么循环(闭合轮廓)就不存在。
  2. 如果一个图的顶点数量等于边的数量,那么一个图只有一个循环。
  3. 如果一个图的顶点数量小于边的数量,那么一个图有不止一个闭合轮廓。

我提供了深度优先搜索算法,该算法在图中找到一个简单的循环并打印它们:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maximumSize=40;
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<int> graph[maximumSize], closedContour, temporary;
int vertices, edges;
set<vector<int>> contours;
void showContentSetVector(set<vector<int>> input)
{
    for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
    {
        for(auto item : *iterator)
        {
            cout<<item<<", ";
        }
        cout<<endl;
    }
    return;
}
bool compare(int i,int j)
{
    return (i<j);
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int initial, int current, int previous)
{
    if(visited[initial][current]==1)
    {
        for(int i=0; i<temporary.size(); ++i)
        {
            if(temporary[i]==current)
            {
                for(int j=i; j<temporary.size(); ++j)
                {
                    closedContour.push_back(temporary[j]);
                }
            }
        }
        sort(closedContour.begin(), closedContour.end(), compare);
        contours.insert(closedContour);
        closedContour.clear();
        return;
    }
    visited[initial][current]=1;
    temporary.push_back(current);
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        depthFirstSearch(initial, next, current);
    }
    temporary.pop_back();
    return;
}
void solve()
{
    createGraph();
    for(int vertex=1; vertex<=vertices; ++vertex)
    {
        temporary.clear();
        depthFirstSearch(vertex, vertex, -1);
    }
    cout<<"contours <- ";
    showContentSetVector(contours);
    return;
}
int main()
{
    solve();
    return 0;
}

结果如下:

contours <- 
1, 2, 3, 4, 
6, 7, 8, 
 类似资料:
  • 我有一个文件看起来是这样的: “葛底堡演说 亚伯拉罕·林肯

  • 目前正在学习编程基础课程,我在完成代码时遇到了一些问题。我知道这太草率了,但我花了很多时间想弄清楚。除了最后的println语句之外,其他一切都正常。我无法在正确的时间打印出来。即使找到值,它也始终打印。我知道问题出在最后的if语句中,但我真的不知道该放什么进去。谢谢你的帮助。

  • 我有一个无向图,它被加载为邻接矩阵。我有一个使用BFS算法检测图中循环的方法。我试图实现的是打印所有的边缘,以一种方式,他们表明一个循环,已经找到。 我可以打印一个图形中的所有边,但我不能只打印那些创建循环的边。我怎么让它工作? 边缘: 图表: 节点: 当前错误输出:显示一个周期的部分边沿,但不是全部边沿 预期输出:打印创建循环的所有边,如上面的示例所示, 我想显示:一条边的结束顶点是循环中另一条

  • 在我的代码中,我从控制台读取了四个整数,并将添加到每个整数中。如果我输入数字四次,应输出四次。 但是,我得到了以下输出:

  • 我们可以用这里所述的算法求有向图中的圈数。我需要理解算法。 (1)最后那句话到底有什么用处?对algo的工作原理进行简短的描述会很有帮助。由于算法基本上是统计从一个节点返回到同一节点的周期数,所以我们可以使用另一个数组,称之为v,并做以下技巧: (2)我不能实现我刚才写的算法。这是主要的问题,但我认为我需要理解上面的(1)来理解打印所有循环的代码。 我了解到互联网上有算法,我正在尝试使用这个算法。

  • 问题内容: 我想在Python 3.5中打印以下模式(我是编码新手): 但是我只知道如何使用下面的代码打印以下内容,但不确定如何将其反转以使其成为完整的菱形: 任何帮助,将不胜感激! 问题答案: 由于中排和最大排的星星有9颗星,因此您应该使之等于9。您可以打印出一半的菱形,但是现在您必须尝试制作一个可以打印特定数量的空格的函数,然后具体数量的星星。因此,请尝试开发一种模式,使每行中的空格和星星数量