dfs.cpp

深度优先算法

#include<iostream>
#include<stack>
#include<fstream>
using namespace std;


struct Node{
	int dest;
	Node *link;
};

struct Vertex{
	int name;
	Node *adj;	
};

int getfirst(int v,Vertex graph[])
{
	if(v!=-1)
	{
		Node *h=graph[v].adj;
		if(h!=NULL) return h->dest; 
	}
	return -1;
}

int getnext(int v,int w,Vertex graph[])
{
	if(v!=-1)
	{
		Node *h=graph[v].adj;
		while(h!=NULL&&h->dest!=w)
			h=h->link;
		if(h!=NULL&&h->link!=NULL)
			return h->link->dest;
	}
	return -1;

}
void DFS(Vertex *graph,int n)
{
	int i,v,w;
	bool *visited=new bool[n];
	for(i=0;i<=n;i++) visited[i]=false;
	stack<Vertex> B;
	B.push(graph[1]);
	visited[1]=true;
	cout<<graph[1].name<<"   ";
	w=getfirst(1,graph);
	do{
		while(w!=-1&&visited[w]==false)
		{
			visited[w]=true;
			cout<<graph[w].name<<"   ";
			B.push(graph[w]);
			w=getfirst(w,graph);
		}
		v=B.top().name;
		B.pop();
		while(visited[w]==true)
		{
			w=getnext(v,w,graph);
			while(w==-1){
				w=v;
				if(B.empty()) return;
				v=B.top().name;
				B.pop();
				w=getnext(v,w,graph);
			}	
		}
		 	
	}while(!B.empty()||w!=-1);
		

	
}

void main()
{
	int n,i,a;
	Node *p,*q;
	ifstream file("graph.txt");
	file>>n;
	Vertex graph[100];
	for(i=1;i<=n;i++)
	{
		file>>graph[i].name;
		file>>a;
		if(a!=-1)
		{
			p=new Node;
			p->dest=a;
			p->link=NULL;
			graph[i].adj=p;
			file>>a;
		}
		while(a!=-1)
		{
			q=new Node;
			q->dest=a;
			q->link=NULL;
			p->link=q;
			p=q;
			file>>a;
		}
	}
	DFS(graph,n);
}