原文链接
#include<stdio.h>
#include<stack>
#define MAX 100
using namespace std;
typedef struct
{
int e[MAX][MAX];
int ves;
int edge;
int book[MAX];//标志判断是否有被访问过
}MGraph;
void createMGraph(MGraph *G)
{
int i;
int j;
int start;
int end;
printf("please input the ves and edge:\n");
scanf("%d %d",&G->ves,&G->edge);
//初始化
for(i = 0; i < G->ves; i++)
{
for(j = 0; j < G->ves; j++)
G->e[i][j] = 0;
G->book[i] = 0;//没被访问过的结点置为0
}
//创建邻接矩阵
printf("please input the (vi,vj)\n");
for(i = 0; i < G->edge; i++)
{
scanf("%d %d",&start,&end);
G->e[start][end] = 1;
}
}
void dfs(MGraph* G,int ves)
{
stack<int> s;//创建一个栈
printf("%d ", ves);
G->book[ves] = 1;//已经访问过结点ves了
s.push(ves);//入栈
while(!s.empty())
{
int data, i;
data = s.top();//取top的顶点
for(i = 0; i < G->ves; i++)
{
if(G->e[data][i] != 0 && G->book[i] != 1)
{
printf("%d ", i);
G->book[i] = 1;
s.push(i);
break;// 开始遍历下一个点的邻接矩阵表
}
}
if(i == G->ves)//data相邻的结点都访问结束了,就弹出data
{
s.pop();
}
}
}
int main()
{
MGraph G;
createMGraph(&G);
dfs(&G,0);
return 0;
}
/*
输入样例:
8 18
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 1
3 7
4 1
4 7
5 2
5 6
6 2
6 5
7 3
7 4
*/