DFS
使用数组 visited[] 用于记录一个节点是否被访问。
public void DFS(i){
visited[i]=true;
for(i 节点的 相邻节点 j){
if(visited[j]!=true){
DFS(j);
}
}
}
#时间复杂度
设边为E条，顶点N个
对于邻接矩阵而言：O(N+E) (其实有2E条边，但是为什么说是N+E，而不是N+2E？)
对于非连接矩阵而言：O(N*N)
BFS
visited[] 用于记录节点是否被访问过
p 用于存放将要被遍历的节点 的 链表
enqueue(i,p) 就是将所有的i 的相邻节点放入到 p中。
public void BFS(i){
visited[i]= true;
enQueue(i,p);
while(!IsEmpty(p)){
j=deQueue(p);//将头元素拿出来
if(!visited[j]){
visited[j]=true;
enqueue(j,p);
}
}
}
时间的复杂度和DFS一样
而这两种方法都是要求，图是联通的，如果图不连通的话，那么就无法完全遍历成功了。
public void traverse(G){
for(V in G){
if(!visited[V]);
DFS(V);//BFS(V);
}
}
code
/* 邻接表存储的图 – DFS（C语言实现） */
/* Visited[]为全局变量，已经初始化为FALSE */
void DFS( ALGraph *G, int i )
{ /* 以Vi为出发点对邻接表存储的图G进行DFS搜索 */
EdgeNode *W;
printf( "visit vertex: %c\n", G->adjlist[i].Vertex );
/* 相当于访问顶点Vi */
Visited[i] = TRUE; /* 标记Vi已访问 */
for( W = G->adjlist[i].FirstEdge; W; W = W->Next )
if ( !Visited[ W->AdjV ] )
DFS( G, W->AdjV );
}
/* 邻接矩阵存储的图 – BFS（C语言实现） */
void BFS ( MGraph G )
{ /* 按广度优先遍历图G。使用辅助队列Q和访问标志数组Visited */
Queue *Q;
VertexType U, V, W;
for ( U = 0; U < G.n; ++U )
Visited[U] = FALSE;
Q = CreatQueue( MaxSize ); /* 创建空队列Q */
for ( U = 0; U<G.n; ++U )
if ( !Visited[U] ) { /* 若U尚未访问 */
Visited[U] = TRUE;
printf( "visit vertex: %c\n", G.Vertices[U] );
/* 相当于访问顶点U */
AddQ (Q, U); /* U入队列 */
while ( ! IsEmptyQ(Q) ) {
V = DeleteQ( Q ); /* 队头元素出队并置为V */
for( W = FirstAdjV(G, V); W; W = NextAdjV(G, V, W) )
if ( !Visited[W] ) {
Visited[W] = TRUE;
printf( "visit vertex: %c\n", G.Vertices[W] );
/* 相当于访问顶点W */
AddQ (Q, W);
}
} /* while结束*/
} /* 结束从U开始的BFS */
}
/* FirstAdjV(G, V)和NextAdjV(G, V, W)请自己练习实现。*/
实例
#拯救007
黑点：表示007可以跳的位置：
红点：表示初始位置
007 有个跳跃半径
拯救007
* G(V)
* 007的位置设为 V7
* visited[]用于记录节点是否被访问过
* radius :007 可以跳跃的半径
public void save007(G){
for(V in G){
if(!visited[V] && distance(V7,V) < radius){
if(DFS(V)){
print “save Sucesss”；
break;
}
}
}
print "save fail"
}
public boolean DFS(V){
if(distanceFromSide(V) < radius){
return true;
}else{
for(W in G ){
if(!visited[W]&& distance(V,W)<radius){
if(DFS(W)) return true;
}
}
return false;
}
}
#六度空间
你和任何一个陌生人所间隔的人都不会超过6个。
题目：
给定的社交网络图中，对计算满足6度空间理论的节点占总节点的百分比
Vcount 是 总结点数
public int S6(){
sum=0;
for(V in G){
count = BFS(V)
if(count ==Vcount){
sum++;
}
}
return sum;
}
Node{
V
int level;
}
BFS(V){
Node NV = Node(V,6)
count=0;
Enqueue(NV,Q);
while(!IsEmpty(Q)){
NV =Dequeue(Q);
level = NV.level-1;
for(W in V)//V可以到达的点{
if(!visited[W] && level>=0){
visited[W]=true;
count++;
Enquence(Node(W,level),Q);
}
}
}
return count;
}
记录最后一个。
Paste_Image.png
