图的遍历: 指从图G的任意一个顶点v出发，访问图中所有结点且每个结点仅访问一次的过程。

注意只能是一次。

图遍历的方法：

深度优先搜索（类似于树的先序遍历）

宽度优先搜索（类似于树的按层次遍历）

当然上面也只是说说类似，他们还是有很多区别的。

图遍历与树遍历的差异

1、从图中任意一个顶点出发未必能到达其它所有顶点；

2、图中存在回路时，又可能多次经过同一个顶点。

       为了避免发生上述两种情况，可设置一个标志顶点是否被访问过的辅助数组visited [ ]，它的初始状态为false，在图的遍历过程中，一旦某一个顶点i被访问，就立即让 visited [i]为true，防止它被多次访问。搜索结束，如果还有未标记过的顶点，遍历算法应当从图中另选一个未标记的顶点出发，再次执行图的搜索。

实现的源代码（参考，后面我会详细的介绍图遍历的两种方式）：

#include <iostream>
using namespace std;
#define MAXNODE 64  // 图中顶点的最大个数 
typedef char vertype;
struct ArcNode  // 弧（边）结点：
{
int adjvex;            // 邻接点在顶点向量中的下标 
ArcNode *next;     // 指向下一邻接点的指针 
};
struct VerNode  // 顶点结点：
{ 
vertype  vertex;        // 顶点信息 
ArcNode  *firstarc;     // 指向第一个邻接点的指针 
};
struct AlGraph// 邻接表：
{
VerNode vertices[MAXNODE];        
int vernum; //顶点的数目
int arcnum;   // 边的数目 
}; 
struct Queue//队列
{
int elem;
Queue *next;
};
void QueueInit(Queue &Q)
{
Q.next=NULL;
}
void QueueIn(Queue &Q,int &v)
{
Queue *p=&Q;
while(p->next)
{
p=p->next;
}
Queue *temp=new Queue;
temp->elem=v;
temp->next=p->next;
p->next=temp;
}
bool QueueEmpty(Queue &Q)
{
if(Q.next)
return true;
else
return false;
}
void QueueOut(Queue &Q,int &v)
{
Queue *temp;
temp=Q.next;
v=temp->elem;
Q.next=temp->next;
delete temp;
}
int GraphLocateVertex(AlGraph &G,int v)
{
return v-1;
}
void CreateAdjList(AlGraph &G)//此图为有向图
{
int n;
cout<<"请输入顶点数目"<<endl;
cin>>n;
G.vernum=n;//顶点初始化为n
G.arcnum=0;//边数初始化为0
cout<<"请输入各个顶点的数据"<<endl;
for(int i=0;i<n;i++)
{
cin>>G.vertices[i].vertex;//输入顶点信息
G.vertices[i].firstarc=NULL;
}
cout<<"请输入有联系的两顶点:输入方式如：第一个点和第二个点输入成：1 2"<<endl;
int v1,v2;
cin>>v1>>v2;
int i,j;
ArcNode *p=NULL;
while(v1&&v2)//两顶点同时为0时结束
{
i=GraphLocateVertex(G,v1);
j=GraphLocateVertex(G,v2);
p=new ArcNode();
p->adjvex=j;
p->next=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
G.arcnum++;//边数加1
cin>>v1>>v2;
}
}
int visited[MAXNODE];//访问标志数组
void visit(AlGraph &G,int v)
{
cout<<G.vertices[v].vertex<<" ";
}

//以下为深度优先遍历DFS
int GraphFirstAdj(AlGraph &G,int v)
{
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
return -1;
}
int GraphNextAdj(AlGraph &G,int v,int w)
{
ArcNode *p=G.vertices[v].firstarc;
while(p->adjvex!=w)
{
p=p->next;
}
p=p->next;
if(p)
return p->adjvex;
else
return -1;
}
void DFS(AlGraph &G,int v)
{
//从第v个顶点出发递归地深度优先遍历图G
visited[v]=1; visit(G,v);//访问v顶点并将该顶点设为已访问
for(int w=GraphFirstAdj(G,v);w!=-1;w=GraphNextAdj(G,v,w))//-1退出
{
if(!visited[w])
DFS(G,w);//对v的上文访问的邻接顶点w递归调用
}
}
void DFSTraverse(AlGraph &G)
{
for(int v=0;v<G.vernum;v++)//访问数组初始化
visited[v]=0;
for(int v=0;v<G.vernum;v++)
{
if(!visited[v])
DFS(G,v);//对未访问的顶点调用DFS
}
}

//以下为广度优先遍历BFS
void BFSTraverse(AlGraph &G)
{
//广度优先遍历
for(int v=0;v<G.vernum;v++)
visited[v]=0;
Queue Q;
QueueInit(Q);//辅助队列Q
for(int v=0;v<G.vernum;v++)
if(!visited[v])
{
QueueIn(Q,v);
visited[v]=1;
visit(G,v);
int u;
while(!QueueEmpty(Q))
{
QueueOut(Q,u);//对头元素出队列并置为u
for(int w=GraphFirstAdj(G,u);w!=-1;w=GraphNextAdj(G,u,w))
{
if(!visited[w])
{
QueueIn(Q,w);//u的尚未访问的邻接顶点w入队列Q
visited[w]=1;
visit(G,w);
}
}
}
}
}
int main()
{
AlGraph G;
CreateAdjList(G);
DFSTraverse(G);
cout<<endl;
BFSTraverse(G);
cout<<endl;
cout<<G.vernum<<"  "<<G.arcnum<<endl;
cout<<endl;
return 0;
}