图的深度优先搜索

    深度优先搜索的过程是：先选取一个顶点v,从顶点v出发，访问它的邻接顶点w,再从顶点w出发，访问w的邻接顶点，直到把所有相通的顶点访问完。如果图中还有顶点没有访问，则选取一个未访问的顶点，继续执行深度优先搜索。

如果将顶点v的前驱节点记为u,深度优先搜索的前驱子图可能由多棵树组成，因为搜索可以从多个源结点重复进行，深度优先搜索的前驱子图形成的是由多颗深度优先树组成的深度优先森林。

假设有图如下：

它的深度优先搜索过程是：

ABDE  C

或

ABC  DE

深度优先搜索的程序为：

(1)     邻接矩阵表示  深度优先搜索

# include <iostream>
using namespace std;
# include <stdlib.h>
# include <queue>
# define NUM 10
# define ARG 10
int visited[NUM];// 表示结点是否被访问过
queue <int> q;
struct graph{
	int num;
	int arc;
	int a[NUM][NUM];
	char name[NUM];
};
int main()
{   
	//int a[NUM][NUM];
	void create(graph &g);
	void print(graph &g);
	void dfs(graph &g,int i);
	void dfsgra(graph &g);
	graph g;
	create(g);
	print(g);
	dfsgra(g);
	system("pause");
return 0;
}
int locate(graph &g,char a)  //查找结点的位置
{
int i=0;
for(i=0;i<g.num;i++)
	if (g.name[i]==a)
		return i;
return -1;
}

void create(graph &g)      //创建图的邻接矩阵存储
{
int i,j;
cout<<"input num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
for(i=0;i<g.num;i++)
cin>>g.name[i];
for(i=0;i<NUM;i++)
	for(j=0;j<NUM;j++)
		g.a[i][j]=-1;
for(i=0;i<g.arc;i++)
{
	char a,b;
	int i,j,w;
cout<<"input name of nodes"<<endl;
cin>>a>>b>>w;
i=locate(g,a);
j=locate(g,b);
g.a[i][j]=w;
g.a[j][i]=w;    //无向图的邻接矩阵为对称矩阵
}
}

void print(graph &g)
{
int i,j;
for(i=0;i<g.num;i++){
	for(j=0;j<g.num;j++)
		cout<<g.a[i][j]<<"\t";
	cout<<endl;
}
}

void dfs(graph g,int i)  //深度优先遍历i结点
{
	int j;
	visited[i]=1;
	printf("%d\n",g.name[i]);
	for (j=0;j<g.num;j++)
	{
		if(g.a[i][j]&&!visited[j])
		dfs(g,j);
	}
}

void dfsgra(graph &g)   //深度优先遍历图
{
int i=0;
for(i=0;i<g.num;i++)
{
visited[i]=0;
}
for(i=0;i<g.num;i++)
{
if(!visited[i])
dfs(g,i);
}
}                                                                                                                                 

(2) 邻接链表表示  深度优先遍历

# include <iostream>
using namespace std;
# include <stdlib.h>
# include <queue>
# include <stack>
# define NUM 10
int visited[NUM];
struct anode{
int data;
anode *next;
};
struct bnode{
char name;
anode *next;
};
struct graph{
int num;
int arc;
bnode arr[NUM];
};
int main()
{
void print(graph &g);
void create(graph &g);
void dfsgra(graph &g);
void dfs(graph &g,int i);
graph g;
create(g);
dfsgra(g);
system("pause");
return 0;
}
int locate(graph &g,char a)  //查找结点位置
{
int i=0;
for(;i<g.num;i++)
{
	if (g.arr[i].name==a)
		return i;
}
return -1;
}
void create(graph &g)       //创建图的邻接链表表示
{
cout<<"input the num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
int i=0;
for(;i<g.num;i++)
{
cout<<"input the names of node"<<endl;
cin>>g.arr[i].name;
g.arr[i].next=NULL;
}
for(i=0;i<g.arc;i++)
{
	char a,b;
cout<<"input node a and node b"<<endl;
cin>>a>>b;
int i=locate(g,a);
int j=locate(g,b);
anode *p=new anode;
p->data=j;
p->next=g.arr[i].next;
g.arr[i].next=p;
}
}
void dfs(graph &g,int i)    //深度优先搜索i结点
{
	anode *p=0;
	visited[i]=1;
	printf("%d\n",g.arr[i].name);
	p=g.arr[i].next;
    while(p)
	{
		if(!visited[p->data])
		dfs(g,p->data);
		p=p->next;
	}
	
}
void dfsgra(graph &g)   //深度优先搜索图
{
int i=0;
for(i=0;i<g.num;i++)
{
visited[i]=0;
}
for(i=0;i<g.num;i++)
{
if(!visited[i])
dfs(g,i);
}
}

图的深度优先搜索,布布扣,bubuko.com

图的深度优先搜索

原文：http://blog.csdn.net/u011608357/article/details/21319927