欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有向图输出所有环,相同的环仅输出字典序最小的序列

程序员文章站 2023-12-27 08:07:03
...

注释超级详细。。不信你看不懂。。看不懂底下留言!!!!

 

数据输入

该有向图用链式图存储

a b;a c;b e;e b;c d;d a

有向图输出所有环,相同的环仅输出字典序最小的序列

 

运行结果

有向图输出所有环,相同的环仅输出字典序最小的序列

 

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

//有向图中找出所有的环,重复的环只保留字典序最小的序列:比如abcda,bcdab是同一个环,只保留abcda 

/*
set<char>s;是用来记录哪些元素构成环 (set具有不重复性) 
set<set<char> >set_circle_element;用来存储每个环的元素,
当有一个新环被发现,就被加入到里面。同时这保证了相同环的最小字典序.
比如发现有一个环是abcda,set_circle_element就记录了{a,b,c,d}。当发现bcdab这个环时,
因为set_circle_element中已经有 {a,b,c,d}了,就不考虑bcdab这个环了。同理cdbac...

 vector<vector<char> >CIRCLE;用来存储存储字典序最小的环 
*/ 
vector<char>expend;
vector<char>circle;//记录每次的序列,是最小字典序的环就加入到 vector<vector<char> >CIRCLE中 
vector<vector<char> >EXPAND;
vector<vector<char> >CIRCLE;
map<char,vector<char> >mp;//链式图 
set<char>s;
set<set<char> >set_circle_element;


//
/*
比较函数 
vector元素小的排前面
要是两个vector一样大,就选字典序小的排前面 
*/ 
int cmp(vector<char>a,vector<char>b)
{
	if(a.size()!=b.size())
		return a.size()<b.size();
	else
	{
		vector<char>::iterator it1,it2;
		for(it1=a.begin(),it2=b.begin();it1!=a.end();it1++,it2++)
			if((*it1)!=(*it2))
				return (*it1)<(*it2);
			else
				continue;
		return 1;
	}
} 

//打印序列 
void show()
{
	vector<char>::iterator it2;
	for(it2=circle.begin();it2!=circle.end();it2++)
    {
    		cout<<(*it2)<<" ";
	}
	cout<<endl;
}

void dfs(char start)
{
	
	//递归终点1 
	 //s发现有重复元素说明出现了环,并且判断这个新字符是否和circle序列第一个元素相等 
	if(s.find(start)!=s.end()&& start==*circle.begin())
	{
		circle.push_back(start);//circle加入新元素,此时circle是一个环 
		
		/*
		//判断s在set_circle_element中是否出现过,
		如果出现过,说明此时的circle不是最小字典序,就用添加了
		*/ 
		if(set_circle_element.find(s)==set_circle_element.end() ) 
		{
			set_circle_element.insert(s);//添加新的元素组合 
			CIRCLE.push_back(circle);//添加一个新的字典序最小的环 
		}
		return ;
	} 


	//递归终点2 
	/*
	如果这个新的元素start在circle中出现过说明此时start在circle的中间且不是第一个(因为递归终点1已经判断过了),
	要是再加入这个元素,会在circle序列中产生子环(abcdc),这是不允许的,所以return 
	*/ 
	vector<char>::iterator ret;
	ret=find(circle.begin(), circle.end(), start); 
	if(ret!=circle.end())
		return;
	
	//递归终点3 :序列的长度都大于结点个数了,必须return 
	if(circle.size()>mp.size())
		return;
	
	//这个start不符合上面三个递归终点,将其加入circle序列和s集合 
	s.insert(start);//s加入start 
	circle.push_back(start);//circle加入start 
	vector<char>::iterator it;
	char next;
	//用链式图(变量名为mp)索引为start的vector数组元素依次作为序列的下一个元素 
	for(it=mp[start].begin();it!=mp[start].end();it++)
	{
		
		next=(*it);
		dfs(next);
		
	}
	//这两条语句是为了恢复现场,恢复成没加入start的情形 
	circle.pop_back();
	s.erase(start);
}

int main()
{
	freopen("1.txt","r",stdin);
    char c1,c2;
    
    //构建链式图,此处因为每个人读入数据的格式不一样,需要自己修改 
    while(cin>>c1>>c2)
    {
        getchar();
        mp[c1].push_back(c2);
        //du[c2]++;
        s.insert(c2);
    }
    map<char,vector<char> >::iterator it;

    //输出链式图 
    cout<<"输出链式图"<<endl; 
    for(it=mp.begin();it!=mp.end();it++)
    {
    	char start=(*it).first;
    	
    	cout<<start<<":";
    	vector<char>::iterator it2;
    	for(it2=(*it).second.begin();it2!=(*it).second.end();it2++)
    	{
    		cout<<(*it2)<<" ";
		}
		cout<<endl;
		
	}
    
    
    /*
	遍历链式图的每个结点,并用每个结点连接的元素作为 
	*/ 
    s.clear();
    for(it=mp.begin();it!=mp.end();it++)//遍历链式图的每个结点 
    {
    	char start=(*it).first;//获取第一个结点 
    	
    	 vector<char>::iterator it2;
    	for(it2=(*it).second.begin();it2!=(*it).second.end();it2++)//并用每个结点连接的元素(vector)作为下一个元素 
    	{
    		//每次换新元素时都要重新把start加入,因为dfs之后会把s和circle清空 
		    circle.push_back(start);
    	    s.insert(start);
  
    		dfs(*it2);//(*it2就是vector数组中的每个元素)开始递归。。。 
    		
    		//恢复现场,为下一个vector中的元素充当circle序列中start之后的元素做准备 
    		s.clear();
    		circle.clear();
		}
		//恢复现场,感觉这两句多余,但是为了保险,还是清除一下吧 
		s.clear();
    	circle.clear();
	}
    
    
    
    cout<<"打印所有环"<<endl; 
    sort(CIRCLE.begin(),CIRCLE.end(),cmp);//给 CIRCLE排序 
    
    //打印 CIRCLE,每个人的打印方式不一样,自己修改 
    vector<vector<char> >::iterator it1;
    vector<char>::iterator it2;
    for(it1=CIRCLE.begin();it1!=CIRCLE.end();it1++)
    {
    	for(it2=(*it1).begin();it2!=(*it1).end();it2++)
    	{
    		cout<<(*it2)<<" ";
		}
		cout<<";";
	}
    
    return 0;
}

 

相关标签: dfs 图论

上一篇:

下一篇: