描述
一个连通图采用邻接表作为存储结构。设计一个算法,实现从顶点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;
}