图的遍历-深度优先遍历

图的遍历跟树的遍历一样,从图中一点出发遍历图中其余顶点,且使每一个顶点仅被访问一次 叫 Traversing Graph

depth first search  DFS  深度优先遍历  深度优先搜索     类似与Tree中 前序遍历

具体算法表述如下:

  1. 访问初始结点v,并标记结点v为已访问。

  2. 查找结点v的第一个邻接结点w。

  3. 若w存在,则继续执行4,否则算法结束。

  4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。

  5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7

图的遍历-深度优先遍历

bool visited[MAX];//初始化全为false

邻接矩阵 深度优化递归 因为边存在1才能访问
// 递归法
void DFS(MGraph G, int i)//从第i个开始遍历
{
	visited[i] = true;
	cout<<G.VexArr[i];
	for(int j=0;j<G.numV;j++)
	{
		if(G.arc[i][j] == 1 && ! visited[j])
		{
			DFS(G,j);
		}
	}
}
void DFSTraverse(MGraph G) //邻接矩阵深度遍历操作
{
	for(int i=0;i<G.numV;j++)
	{
		visited[i] = false;
	}
	for(int i=0;i<G.numV;i++)
	{
		if(! visited[i])//对未访问过的顶点调用DFS, 如果是连通图则上面的for循环只执行一次就
		{
			DFS(G,i);
		}
	}
}

邻接表

bool visited[MAX];//初始化全为false

邻接表 深度优化递归 
// 递归法
void DFS(GraphList G, int i)//从第i个开始遍历
{
	visited[i] = true;
	EdgeNode *p = NULL;
	cout << G.adjlist[i].data;//输出 刚刚遍历的那个节点
	p = G->adjlist[i].firstedge;//p指向 邻接表的首地址
	while(p)
	{
		if(!visited[p->adjvex])
		{
			DFS(G, p->adjvex);
		}
		p = p->next;
	}
}
void DFSTraverse(GraphList G) //邻接矩阵深度遍历操作
{
	for(int i=0;i<G.numV;j++)
	{
		visited[i] = false;
	}
	for(int i=0;i<G.numV;i++)
	{
		if(! visited[i])//对未访问过的顶点调用DFS, 如果是连通图则上面的for循环只执行一次就
		{
			DFS(G,i);
		}
	}
}
http://blog.csdn.net/todd911/article/details/9191481
对于n个顶点e个边的图来说  邻接矩阵遍历时间复杂度为O(n^2);  而邻接表复杂度为O(n+e);  对于有向图而言只是在对通道存在可行或者不可行,基本算法上差别不太大

上一篇:【算法设计与分析】桥


下一篇:图(Graph)深度优先搜索