4011-基于邻接表的深度优先遍历（C++，取巧做法）

本文主要是介绍4011-基于邻接表的深度优先遍历（C++，取巧做法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

一个连通图采用邻接表作为存储结构。设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

输入

多组数据，每组m+2数据行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k，代表边依附的两个顶点。第m+2行有一个整数d，代表从d开始遍历。当n和m都等于0时，输入结束。

输出

每组数据输出一行，为深度优先搜索的遍历结果。每两个数字之间用空格隔开。

输入样例 1 

3 2
1 2
1 3
1
2 1
1 2
2
0 0

输出样例 1

1 2 3
2 1

思路：

这个题的取巧做法是看输出来决定做题方法，可以不用考虑“深度优先搜索”这个算法。

输出是顺序遍历，但是倒序输出，就是说是先走过的路最后输出，是“后进先出”的思想，所以可以采用一个栈来存储走过的路，最后再依次输出栈顶元素即可。

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

typedef struct LNode
{
	int data;
	struct LNode* next;
}*linklist, LNode;
typedef struct
{
	int vexnum;
	int arcnum;
	linklist VList;
}ALGraph;
void Create(ALGraph& alg, int n, int m)
{
	alg.arcnum = m;
	alg.vexnum = n;
	alg.VList = new LNode[n + 1];
	for (int i = 1; i <= n; i++)
	{
		alg.VList[i].data = i;
		alg.VList[i].next = NULL;
	}
	int h, k;
	for (int i = 0; i < m; i++)
	{
		cin >> h >> k;
		linklist p = new LNode, q = new LNode;
		p->data = h;
		p->next = alg.VList[k].next;
		alg.VList[k].next = p;

		q->data = k;
		q->next = alg.VList[h].next;
		alg.VList[h].next = q;
	}
}
void Show(ALGraph alg)
{
	int p;
	cin >> p;
	cout << p << ' ';
	int i = 0;
	linklist q = &alg.VList[p];
	stack<int> s;
	while (q->next)
	{
		s.push(q->next->data);
		q = q->next;
		i++;
	}
	while (!s.empty())
	{
		cout << s.top();
		if (i != 1)
			cout << ' ';
		s.pop();
		i--;
	}
	cout << endl;
}
int main()
{
	int m, n;
	while (cin >> n >> m && m != 0 && n != 0)
	{
		ALGraph a;
		Create(a, n, m);
		Show(a);
	}
	return 0;
}

这篇关于4011-基于邻接表的深度优先遍历（C++，取巧做法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！