4013-基于深度优先搜索的两顶点路径存在与否的判断（C++，附详细思路）_随笔

4013-基于深度优先搜索的两顶点路径存在与否的判断（C++，附详细思路）

描述

设计一个算法，试基于深度优先搜索判断以邻接表方式存储的有向图中是否存在由顶点vi

输入

多组数据，每组m+3数据行。第一行有两个数字n和m，代表有n个顶点和m条边。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h和k，代表边依附的两个顶点。第m+3行有两个字符vi和vj，代表需要判断的两个顶点。当n和m都等于0时，输入结束。

输出

每组数据输出一行。若存在路径输出“YES”，反之输出“NO”。

输入样例 1

3 2
abc
ab
bc
ac
4 2
bcsw
bs
sw
cs
0 0

输出样例 1

YES
NO

思路：

采用了unordered_map，假设DFS的思想你已经大致了解了（就是知道那个意思，但是自己不能完整地实现出来，那个意思），如果不清楚DFS的话直接看这个视频就行了！DFS深搜解决迷宫问题(原理分析+代码实现）_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1bK4y1C7W2

全局变量

unordered_map mp;用来存储每个节点对应的序号，不用map的原因是map会根据key值自动排序，而我们不能让它自动排序，所以用unordered_map
int visit[30];访问数组

创建邻接表的时候把它的每个字母及其出现顺序存进mp里，方便以后邻接表表头数组按顺序使用——>写一个GetPos函数来获得某个字母所对应的位置：迭代器从头迭代，返回指向的second就行了，这个不是重点，略过；

注意：这个题是有向图！！！创建的时候方向别写多了！！邻接表初始化别忘了把next置为NULL！

DFS函数是重点，我们出发的点是from，要去的点是to，那么出口就是from==to，因为是从from出发去找to，所以他俩相等的时候说明找到了，

如果不相等，那么就从当前的from对应的位置开始寻路，GetPos函数获取当前from对应的位置，visit先标记这个点为1（已访问），若p->next存在，说明有路，那么把p->next->data作为from传进去，继续调用DFS（这就是递归），此时from从一开始的点走到了它能走到的下一个位置，相当于模拟了“寻路”。

那么按照这个思路，如果有路，不会到DFS的下一条语句就已经找到输出YES了，YES方向结束。

递归调用的下一条是visit[当前节点的序号值]=0，刚才标记是1是因为这个点已访问，上一段说道若输出YES则不会立刻执行这句，那么这句对应的就是“没路”的情况，也就是p->next=NULL的情况，那么你想：在不回头的情况下（有向图），如果走到死胡同了，那还可能到目的地吗？不可能，所以直接输出NO。

个人感觉DFS算法的精髓在于先标记，再DFS，再取消标记，这三步是核心，你写的时候如果有这三句，那么一般也差不多了，注意参数调用就没什么问题了~

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef struct LNode
{
	char data;
	struct LNode* next;
}*linklist, LNode;
typedef struct
{
	linklist VList;
	int vnum;
	int anum;
}ALGraph;
unordered_map mp;
int visit[30];
int GetPos(char c,unordered_mapmp)
{
	unordered_map::iterator it = mp.begin();
	while (it != mp.end())
	{
		if (it->first == c)
			return it->second;
		it++;
	}
	return 0;
}
void Create(ALGraph& alg, int n, int m)
{
	alg.anum = m;
	alg.vnum = n;
	alg.VList = new LNode[alg.vnum + 1];
	string s;
	cin >> s;
	for (int i = 1; i <= n; i++)
	{
		alg.VList[i].data = s[i];
		alg.VList[i].next = NULL;
		mp.insert(make_pair(s[i-1], i));
	}
	for (int i = 0; i < m; i++)
	{
		cin >> s;
		int pos = GetPos(s[0],mp);
		linklist p = &alg.VList[pos], q = new LNode;
		q->data = s[1];
		q->next = p->next;
		p->next = q;
	}
}
void DFS(ALGraph alg,char from,char to)
{
	if (from == to)
	{
		cout << "YES" << endl;
		return;
	}
	int pos = GetPos(from, mp);
	linklist p = &alg.VList[pos];
	visit[pos] = 1;
	if (p->next)
	{
		DFS(alg, p->next->data, to);
		visit[pos] = 0;
	}
	else
	{
		cout << "NO" << endl;
		return;
	}
}
int main()
{
	int n, m;
	while (cin >> n >> m && n != 0 && m != 0)
	{
		ALGraph a;
		Create(a, n, m);
		string s;
		cin >> s;
		char from = s[0], to = s[1];
		DFS(a, from, to);
		mp.clear();
	}
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5650366.html

4013-基于深度优先搜索的两顶点路径存在与否的判断（C++，附详细思路）

发表评论

评论列表（0条）