从图的某一个顶点出发访问遍图中其余所有顶点，并且使每个顶点只被访问一次，这个过程称为图的遍历。
在图的遍历过程中，为了避免某个顶点被多次访问，一般使用一个辅助数组vistied【n】，他的初始值是false，对应的顶点访问过一会值为true。图的遍历算法有：深度优先搜索和广度优先搜索，对无向图和有向图都适用。
以该图a为描述实例
1 深度优先搜索 （Depth_First_Search）
深度优先搜索类似于树的先根遍历，深度优先搜索从图中某个顶点v出发，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历图，直至和v有路径相同的顶点都被访问过；若此时图中尚有顶点未被访问，则另选图中一个未成被访问的顶点做起始点，重复上述过程
如图a所示，深度优先搜索假设从v1开始，则访问顺序为：v1->v2->v4->v8->v5->v3->v6->v7。
------存储结构--前面是深度优先算法和 广度优先算法都适用的全局变量----------
Boolean visted[max] ;//是否访问过的数组标示
Status (*visitFunc(int v));//函数变量
void DFSTraverse(Graph G , status(*vist)(int v))//对图G做深度搜索，适用全局变量visitfunc，使DFS不必设置函数指针参数
{
visitFunc = visit;
for(v = 0 ; v <G.vexnum;++v) visited[v] = FALSE;//初始化 访问数组为false
for(v = 0 ;v < G.vexnum ; ++v)
{
if ( !visited[v]) DFS(G,v);//如果图G中的顶点v没有被访问，调用dfs访问函数
}
}
void DFS(Graph G,int v)//顶点的访问函数，递归调用；从顶点v开始递归的深度优先遍历图G
{
visited[v] = TRUE; visitFunc(v);//访问函数，并且设置访问标示数组为true；
for(w = firstAdjVex(G,v); w>=0; w= NextAdjVex(G,v,w) )
if(!visited[w]) DFS(G,w);//如果没有对v访问，则递归调用DFS。
}
firstAdjVex(G,v);//在图中访问与v节点相连的第一个结点。
w = nextAdjVex(G,v,w);//与v的结点连接的下一个结点赋值给w。
这个时候进入下一次的递归调用，这个是原来的v参数已经变成了w。就变成找w直接邻接的结点，如此递归下去。过程实质就是对每个顶点查找直接其邻接点过程。
2.广度优先搜索
广度优先算法类似树的按层次遍历的过程。
假设从图中顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点（与v直接相邻接的所有顶点），然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”，直至图中所有已经被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问过。
一般来说，广度优先算法的过程是以v为起始点，由近及远，依次访问和v有路径相通而且路径长度为1，2，n。。。的订单。
图a的访问顺序为：v1 - v2 - v3 - v4 - v5 - v6 - v7 -v8
----------代码------------
void BFSTraverse(Graph G,Status (* visit)(int v))
//按广度优先非递归遍历图G，使用辅助队列和访问标示数组visited【max】
{
for ( v= 0 ; v < G.vexnum ; ++v ) visited[v] = FALSE;//访问数组初始化
InitQueue(Q);//置空的队列Q
for(v = 0 ; v < G.vexnum ; ++v)
{
if( !visited[v])
{
visited[v] = TRUE; visit(v);//访问函数，并置对应的数组为true；
EnQueue(Q,v);//v入队列
while(!QueueEmpte(Q))
{
DeQueue(Q,u);
for( w = firstAdjVex(G,u); w >= 0 ; w= nextAdjVex(G,u,w))
{
if(!visited[w])
{
visited[w] = TURE; visit(v);//访问函数
EnQueue(Q,w);
}
}
}
}
}
}
//与深度优先的比较
//firstAdjVex(G,u);查找顶点u在图G中第一个相连的邻接点。
nextAdjVex(G,u,w);//查找顶点u在图G中的下一个邻接点，置为w。注意在这个地方，变量u一直没有变化，一直是u，直到与u相邻接的节点全部访问过。但是在深度优先搜索中这个u变量再第一次访问过以后，就变成了w，开始了下一次递归运算。
在图的遍历过程中，为了避免某个顶点被多次访问，一般使用一个辅助数组vistied【n】，他的初始值是false，对应的顶点访问过一会值为true。图的遍历算法有：深度优先搜索和广度优先搜索，对无向图和有向图都适用。
以该图a为描述实例
1 深度优先搜索 （Depth_First_Search）
深度优先搜索类似于树的先根遍历，深度优先搜索从图中某个顶点v出发，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历图，直至和v有路径相同的顶点都被访问过；若此时图中尚有顶点未被访问，则另选图中一个未成被访问的顶点做起始点，重复上述过程
如图a所示，深度优先搜索假设从v1开始，则访问顺序为：v1->v2->v4->v8->v5->v3->v6->v7。
------存储结构--前面是深度优先算法和 广度优先算法都适用的全局变量----------
Boolean visted[max] ;//是否访问过的数组标示
Status (*visitFunc(int v));//函数变量
void DFSTraverse(Graph G , status(*vist)(int v))//对图G做深度搜索，适用全局变量visitfunc，使DFS不必设置函数指针参数
{
visitFunc = visit;
for(v = 0 ; v <G.vexnum;++v) visited[v] = FALSE;//初始化 访问数组为false
for(v = 0 ;v < G.vexnum ; ++v)
{
if ( !visited[v]) DFS(G,v);//如果图G中的顶点v没有被访问，调用dfs访问函数
}
}
void DFS(Graph G,int v)//顶点的访问函数，递归调用；从顶点v开始递归的深度优先遍历图G
{
visited[v] = TRUE; visitFunc(v);//访问函数，并且设置访问标示数组为true；
for(w = firstAdjVex(G,v); w>=0; w= NextAdjVex(G,v,w) )
if(!visited[w]) DFS(G,w);//如果没有对v访问，则递归调用DFS。
}
firstAdjVex(G,v);//在图中访问与v节点相连的第一个结点。
w = nextAdjVex(G,v,w);//与v的结点连接的下一个结点赋值给w。
这个时候进入下一次的递归调用，这个是原来的v参数已经变成了w。就变成找w直接邻接的结点，如此递归下去。过程实质就是对每个顶点查找直接其邻接点过程。
2.广度优先搜索
广度优先算法类似树的按层次遍历的过程。
假设从图中顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点（与v直接相邻接的所有顶点），然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”，直至图中所有已经被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问过。
一般来说，广度优先算法的过程是以v为起始点，由近及远，依次访问和v有路径相通而且路径长度为1，2，n。。。的订单。
图a的访问顺序为：v1 - v2 - v3 - v4 - v5 - v6 - v7 -v8
----------代码------------
void BFSTraverse(Graph G,Status (* visit)(int v))
//按广度优先非递归遍历图G，使用辅助队列和访问标示数组visited【max】
{
for ( v= 0 ; v < G.vexnum ; ++v ) visited[v] = FALSE;//访问数组初始化
InitQueue(Q);//置空的队列Q
for(v = 0 ; v < G.vexnum ; ++v)
{
if( !visited[v])
{
visited[v] = TRUE; visit(v);//访问函数，并置对应的数组为true；
EnQueue(Q,v);//v入队列
while(!QueueEmpte(Q))
{
DeQueue(Q,u);
for( w = firstAdjVex(G,u); w >= 0 ; w= nextAdjVex(G,u,w))
{
if(!visited[w])
{
visited[w] = TURE; visit(v);//访问函数
EnQueue(Q,w);
}
}
}
}
}
}
//与深度优先的比较
//firstAdjVex(G,u);查找顶点u在图G中第一个相连的邻接点。
nextAdjVex(G,u,w);//查找顶点u在图G中的下一个邻接点，置为w。注意在这个地方，变量u一直没有变化，一直是u，直到与u相邻接的节点全部访问过。但是在深度优先搜索中这个u变量再第一次访问过以后，就变成了w，开始了下一次递归运算。
本文使用Blog_Backup未注册版本导出，请到soft.pt42.com注册。