图-遍历

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