图是严蔚敏书上P168的图，
图的邻接表存储，DFS可以看以前写的文章：http://www.cnblogs.com/youxin/archive/2012/07/28/2613362.html
bool visited[];
void (*visitFunc)(VextexType v); void visit(VextexType v)
{
cout<<v<<ends;
} void BFSTraverse(Graph G,void (*Visit)(VextexType v))
{
visitFunc=Visit;
for(int i=;i<G.vexnum;i++) visited[i]=false;
queue<int> q; for(int i=;i<G.vexnum;i++) //对于连通图为1即可。
{
if(!visited[i])
{
visited[i]=true;//i尚未访问
visitFunc(G.vertices[i].data); q.push(i); while(!q.empty())
{
int front=q.front(); q.pop(); ArcNode *p=G.vertices[front].firstarc;
while(p!=NULL)
{
int w=p->adjvex;
if(!visited[w])
{
visited[w]=true;visitFunc(G.vertices[w].data); q.push(w);
}
p=p->nextarc;
}
}
}//end if
}//end for
}
首先v1 访问v1 ，v1下一个邻接点为v3，访问v3,v3入队列，访问v2,v2入队列。最终队列变成
v3 v2
会pop v3，访问v3，把v3的所有没有访问的邻接点入队列，即：v7 v6，由于顶点v1访问了，不入queue。
queue变成：
v2 v7 v6
接着pop v2，把v2所有邻接点入queue，v5,v4,,。队列 变成
v7 v6 v5 v4
接着pop v7，把v7邻接点入queue，即:v6和v3已经访问了，不入),队列变成
v6 v5 v4
接着popv6,把v6邻接点入queue，由于v3已经访问了，队列变成了.
v5 v4
接着popv5,把v5邻接点v8入queue，变成
v4,,v8
接着popv4，把入queue，队列变成
v8
注意：每个顶点至多入一次队列（我们在进入对了之前会进行判断是否访问，如没有访问，访问它，进入队列，也就是说
在进入队列之前visit已经为true了）。遍历图的过程实质是通过边或弧找邻接点的过程，因此，DFS和BFS遍历图的时间复杂度相同。
我们为了求最短路径，还要设置2个数组，
一个是
int d[50];d[v]记录从s到v的路径长度。d[0]为0，源顶点到自身为0.
int parent[50] ;parent[i]表示顶点i的parent。
按照算法导论上面说的：
对上面的代码稍作修改：
void BFSTraverse(Graph G,void (*Visit)(VextexType v))
{
visitFunc=Visit;
for(int i=;i<G.vexnum;i++) visited[i]=false;
queue<int> q;
//我们这里第0个顶点为原点s
for(int i=;i<G.vexnum;i++)
{
d[i]=INT_MAX;//这里不设置也没问题，只要设置d[0]为0就ok了。
parent[i]=-;
}
d[0]=0;
parent[0]=-1;//第0个顶点没有parent。 for(int i=;i<G.vexnum;i++) //对于连通图为1即可。
{
if(!visited[i])
{ visited[i]=true;
visitFunc(G.vertices[i].data); q.push(i); while(!q.empty())
{
int front=q.front(); q.pop(); ArcNode *p=G.vertices[front].firstarc;
while(p!=NULL)
{
int w=p->adjvex;
if(!visited[w])
{
d[w]=d[front]+1,parent[w]=front; visited[w]=true;visitFunc(G.vertices[w].data); q.push(w);
}
p=p->nextarc;
}
}
}//end if
}//end for
}
//输出从s到v的最短路径上的所有顶点
void printPath(Graph G,int s,int v)
{
if(s==v)
cout<<s<<ends; else if(parent[v]==-)
cout<<"no path from s to v exists"<<endl;
else
{
printPath(G,s,parent[v]);
cout<<v<<ends;
} }
基本上就只多了画红线的部分，printPath打印从原顶点到v的所有路径，如：
printPath(G,0,7);
输出：0 1 4 7.