图的遍历（c语言）

图的遍历

概念:图遍历是一种用于在图中搜索顶点的技术。图的遍历也用来决定在搜索过程中访问顶点的顺序。图的遍历可以在不创建循环的情况下找到要在搜索过程中使用的边。这意味着使用图遍历，我们访问图的所有顶点而不进入循环路径。

种类

目前，只有两种

1. DFS (Depth First Search) 中文：深度优先遍历
2. BFS (Breadth First Search) 中文:广度优先遍历

深度优先遍历

方法有很多种，我这里采用访问的时候定一个主方向访问的手法.当然逻辑都是一样的，都是采用像树的一样的访问形式……

算法实现

以免有新手不知道,下面出现的numVertexes是顶点数

//邻接矩阵的深度优先遍历
typedef int Boolean; //此行代码就直接相当于定义好了FALSE和TRUE的值了，这两个的值也是用来判断顶点数据是否又被访问过
Boolean visited[MAX]; //该数组为记录访问标识
void DFS(Graph G,int i)
{
	int j;
	visited[i]=TRUE;//立马改为已被访问状态
	printf("%c\t",G->vexs[i]);//打印顶点
	for(j=0; j<G.numVertexes; ++j)//判断该顶点与其余所有顶点之间是否存在关系
		if(G.arc[i][j])==1 && !visited[j])//满足条件一：两个顶点之间存在相互连接关系 条件二：还未被访问过
			DFS(G,j);//对未访问的邻接点进行递归调用
}

void DFSTraverse(MGraph G)
{
	int i;
	for(i=0; i<G.numVertexes; ++i)
		visited[i]=FALSE;//初始化所有的顶点范文标识为FALSE
	for(i=0; i<G.numVertexes; ++i)
		if(!visited[i])//经过上移代码的过程，开始进行寻找未被访问过的顶点
			DFS(G,i);
}

//邻接表的深度优先遍历
void DFS(GraphAdjList GL,int i)
{
	EdgeNode *p;
	visited[i]=TURE;//同上
	printf("%c\t",GL->adjList[i].data);
	p=GL->adjList[i].firstedge;//p指向头指针
	while(p)
	{
		f(!visited[p->adjvex])
			DFS(GL,p->adjvex);//如果还未访问过，就递归调用,将其输出
			p=p->next;//到了此行代码的话，说明发现了已经被访问过得，那就指向下一个
	}
	void DFSTraverse(GraphAdjList GL)
	{
		int i;
		for(i=0; i<GL->numVertexes; ++i)
			visited[i]=FALSE;//全部初始化为未访问状态
		for(i=0; i<GL->numVertexes; ++i)
			if(!visited[i])
				DFS(DL,i);//找到了访问的直接就进入DFS了
	}
}

其实如果细心的可能已经发现其实很像树的先序遍历

广度优先遍历

当我们发现图的深度优先遍历类似于树的先序遍历的时候，我们这时还会发现图的广度优先遍历也很像树的层次遍历.

思维：

第一步：以一边的任意一个顶点作为首顶点.
第二步：开始寻找于之有关的顶点.找到并记录下来
第三步：记录以后，将原本的那个顶点放弃，开始以第二步寻找到的顶点为头，寻找与之有关的顶点.
第四步：重复第二步和第三步的操作,直到没有顶点未访问

算法实现

//邻接矩阵的广度遍历
void BFSTravese(MGraph G)
{
	int i, j;
	Queue Q;//另外还借用了队列的知识
	for(i=0; i<G.numvertexes; ++i)
		visited[i]=FALSE;//将未访问过的顶点初始化
	InitQueue(&Q);//队列初始化
	for(i=0; i<G.numVertexes; ++i)
	{
		if(!visited[i])//未被访问过的条件
		{
			visited[i]=TRUE;//那么现在就是已被访问状态了
			printf("%c",G.vexs[i]);
			EnQueue(&Q,i);//入队列
			while(!QueueEmpty(Q))//队列不为空的话就进入
			{
				DeQueue(&Q,&i);//作用已实现，可以将其弄出队列了
				for(j=0; j<G.numVertexes; ++j)
				{
					if(G.arc[i][j]==1 && !visited[j]){
						visited[j]=TRUE;//访问了就把标识给改了
						printf("%c",G.vexs[j]);
						EnQueue(&Q,j);//找到了就将找打的顶点入队列，后序将会使用
					}
				}
			}
		}
	}
}

//邻接表的广度遍历
void BFSTraverse(GraphAdjList GL)
{
	int i;
	EdgeNode *p;
	Queue Q;
	for(i=0; i<GL->numVertexes; ++i)
		visited[i]=FALSE;
	InitQueue(&Q);//解析未做的原因是上面都做过了！！！
	for(i=0; i<G.numVertexes; ++i)
	{
		if(!visited[i])
		{
			visited[i]=TRUE;
			printf("%c",G->adjList[i].data);
			EnQueue(&Q,i);//入队列，后有大用
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q,&i);//开始使用它了，可以出了，用完就不需要了（没错，就是如此无情O~O）！
				p=GL->adjList[i].firstedge;
				while(p)
				{
					if(!visited[p->adjvex])
					{
						visited[p->adjvex]=TRUE;//将访问标识更改
						printf("%c",G-。adjList[p->adjvex].data);
						EnQueue(&Q,p->adjvex);//入队列,后有用
					}
					p=p->next;//一样，到了此步，说明也没发现未被访问的
				}
			}
		}
	}
}