图的遍历
标签（空格分隔）： DS 图
深度优先遍历（DFS）
思路：
1.定义一个bool型数组记录已被访问过的顶点，并初始化为0，表示都还没访问过
2.从其中一个未被访问过的顶点出发深度优先遍历
2.1如果是连通图，则此操作只执行一回，即只从一个顶点出发
2.2如果不连通，则有几个联通分量就执行几回
3.深度优先时，对遍历到的顶点记录，并打印，再查看此顶点的第一个邻接点是否访问过，若访问过，就查看次邻接点，直到未被访问过，或者全被访问过
3.1如果找到一个邻接点没被访问，就重复3，即递归
3.2如果次顶点的邻接点都被访问过，就结束这个层次的递归，返回上一层次，即返回上一个被访问过的顶点继续找上一个顶点的未被访问过的邻接点，若也无，则再退一层次，直到回到第一层次，即遍历的第一个顶点，若第一个顶点的邻接点也都访问过，则代表次联通图（分量）的顶点全部访问过
邻接矩阵
typedef int Boolean;
Boolean visited[MAX];//记录已被访问过的顶点
/*邻接矩阵的深度优先递归*/
void DFS(MGraph G, int i)
{
//i为顶点表中此被访问顶点的下标，对应visited表
visited[i]=TRUE;//记录被访问的结点
printf("%c",G->vexs[i]);//对被访问的顶点的操作
//从第一个邻接点开始，查看是否访问过，若未访问，就递归，相当于先序遍历
for(int j=0;j<G->numVexs;j++)
if(G->arc[i][j]==1&&!visited[j])
DFS(G,j);
}
void DFSTraverse(MGraph G)
{
int i;
//初始化visited[MAX]
for(i=0;i<G->numVexs;i++)
visited[i]=FALSE;//初始所有顶点都未被访问过
//对未被访问过的顶点DFS
for(i=0;i<G->numVexs;i++)
if(!visited[i])
DFS(G,i);//如果是连通图，则只执行一次
}
邻接表
typedef int Boolean;
Boolean visited[MAX];//记录已被访问过的顶点
/*邻接表的深度优先递归*/
void DFS(Gptr G, int i)
{
//i为顶点表中此被访问顶点的下标，对应visited表
visited[i]=TRUE;//记录被访问的结点
printf("%c",G->adjList[i].data);//对被访问的顶点的操作
EdgePtr p=G->adjList[i].firstadge;
//p指向被访问顶点的第一个邻接点、
//从第一个邻接点开始，查看是否访问过，若未访问，就递归，相当于先序遍历
while(p)
{
//如果此邻接点未被访问过，访问递归
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(GPtr G)
{
int i;
//初始化visited[MAX]
for(i=0;i<G->numVexs;i++)
visited[i]=FALSE;//初始所有顶点都未被访问过
//对未被访问过的顶点DFS
for(i=0;i<G->numVexs;i++)
if(!visited[i])
DFS(G,i);//如果是连通图，则只执行一次
}
广度优先遍历（BFS）
思路：层次遍历
1.先初始化visited[MAX]表为0，表示都未访问过
2.定义一个辅助队列并初始化
3.从一个未被访问过的顶点开始广度优先遍历
3.1将未被访问过的此顶点记录，打印并入栈
3.2将栈内顶点出栈一个并访问所有其未被访问的邻接点（3.1）
3.3重复3.2（队列先进先出）直到栈空，说明此联通图（分量）遍历完
4.遍历顶点表，找到新的未被访问的顶点，即另一个联通分量的顶点，重复3，直到遍历完顶点表，则结束
邻接矩阵
void BFS(MGraph G)
{
int i,j;
//初始化
for(i=0;i<G.numVexs;i++)
visited[i]=FALSE;
Queue Q;//辅助队列
InitQueue(&Q);//初始化
for(i=0;i<G->numVexs;i++)//有几个联通分量，执行几次以下操作
{
if(!visited[i])//如果没访问过
{
visited[i]=TRUE;//记录
printf("%c",G->vexs[i]);//对遍历到的顶点操作
EnQueue(&Q,i);//入队
while(!QueueEmpty(Q))//当队伍不空
{
DeQueue(&Q,&i);//出队并赋值给i
for(j=0;j<G->numVexs;j++)//访问被出栈顶点所有未被访问过的邻接点
{
if(G->arc[i][j]==1&&!visited[j])//邻接点没被访问过
{
visited[j]=TRUE;//记录
printf("%c",G->vexs[j]);//操作
EnQueue(&Q,j);//入队
}
}
}//while
}
}
邻接表
void BFS(MGraph G)
{
int i;
//初始化
for(i=0;i<G.numVexs;i++)
visited[i]=FALSE;
Queue Q;//辅助队列
InitQueue(&Q);//初始化
EdgePtr p;//指向邻接点
for(i=0;i<G->numVexs;i++)//有几个联通分量，执行几次以下操作
{
if(!visited[i])//如果没访问过
{
visited[i]=TRUE;//记录
printf("%c",G->adjList[i].data);//对遍历到的顶点操作
EnQueue(&Q,i);//入队
while(!QueueEmpty(Q))//当队伍不空
{
DeQueue(&Q,&i);//出队并赋值给i
/*访问被出栈顶点所有未被访问过的邻接点*/
p=G->adjList[i].first;//指向邻接点
while(p)
{
if(!visited[p->adjvex])//邻接点没被访问过
{
visited[p->adjvex]=TRUE;//记录
printf("%c",G->adjList[p->adjvex].data);//操作
EnQueue(&Q,p->adjvex);//入队
}
}//while
}//while
}
}