图论——读书笔记 (深度优先搜索)

深度优先搜索是这样的，对最近才发现的结点v的所有出发边进行探索，

直到该结点的所有出发边都被发现为止。

例如上面的图，如果是按照以S点为源结点进行深度优先 遍历的话，

相应的访问顺序是：

（根据具体的应用不同，假定是以左访问优先，

而所谓的左优先指的具体是：如上图，当访问到Z结点的时候，

左优先，继续深入访问Y，而把W结点进行暂存起来）

S->Z（W相对于Z靠右,Z被压栈）

Z->Y

Y->X

X结点没有出发边，（所谓出发边指的是从当前结点出发指向其他结点的有向边）

故回溯到Y，Y除了访问过的X同样没有出发边；

回溯到Z，Z还有除了Y没被访问过的出发边指向被压进栈的W

故W从栈中弹出，访问W。

W没有出发边，故回溯到Z,Z再回溯到S。

以上描述就是对图从结点S深度优先遍历一次的大致过程。

在树中为了更形象的对这个算法进行描述，免不了多加了一些属性在其中。

其中u是图中的一个节点：

u.color：这个是用来描述当前结点u是什么颜色的，WHITE代表的是，u结点没有被访问。

BLACK代表的是，以结点u为前驱的所有结点都已经被访问到了。

而GRAY代表的是，位于二者{WHITE，BLACK}之间，即u被访问过了，但u的子结点并未被全部访问到。

u.father: 这个其实在本篇文章中意义不大，是用于标记结点u的前驱结点在图G 的Adj[]数组中的位序的，

同时也是用于标识G在跑完DFS算法的时候生成的深度优先树的。

u.startTime：结点的这个属性是用来给每个结点盖上时间戳的，

这个属性记载的是u结点第一次被发现的时间（涂上灰色的时候）

u.endTime：同上，不过这个属性记载的是在搜索完成对u结点的邻接链表扫描结束之后的时间，

该时间同样也是，访问从u出发的所有的结点之后，也是u结点被涂成黑色之后的时间。

u.name： 这个是用来记录结点的名称的；

u.firstedge：这个是邻接链表用于指向该结点后面的第一个邻接结点的指针，

通过它可以找到图中与u结点相连接的其他结点。

下面的深度优先搜索算法的伪代码将其发现结点u的时刻记录在属性u.d中，

将其完成对结点u的处理的时刻记录在u.f这一属性中。

因为|V|个结点中只能有一个发现事件和一个完成事件，

所以这些时间戳都是位于[1， 2*|V|]之间的整数。

很显然对于每个结点都有u.d < u.f

结点u在时间u.d之前为WHITE，在介于[u.d, u.f]之间为GRAY

在u.f之后为BLACK。

下面的伪代码给出的是基本的深度优先搜索算法。输入图G既可以是有向图

当然也可以是无向图，而变量为一个全局变量，用它来计算对每一个访问结点的时间戳。

DFS(G)
    for each vertex u attibute G.V
           u.color = WHITE
           u.father = NIL
     time = 0
     
    for each vertec u attribute to G.V
            if u.color  ==  WHITE
                     DFS-VISIT(G,u)

//code above is the main DFS that the cycle will check
//each node in Graph G, if the node is unvisited whose color is white
// DFS will call method:DFS-VISIT and take that node as the source node

DFS-VISIT(G,u)
time = time+1

u.d = time

u.color = GRAY

for each v attribute to G:Adj[u]
  if v.color == WHITE
      v.f = u
      DFS-VISIT(G, v)  //continue to run

u.color = BLACK
//blacken the node u after its subnodes all visited

time = time +1

u.f = time

 下面是使用C++代码实现上述的伪代码：

 在这里说明一下，LZ将color属性单独提出来作为Color数组，这个Color数组

其实质上与平时进行图遍历的visited数组所起到的作用是一样的，只不过，在《算法导论 第三版》

中将结点划分为访问与未访问之间，又多出了一个状态：GRAY，就是一个结点虽然被访问，

但是与它相连接的结点还没有全部被访问，这种情况下，将该结点的颜色属性置为GRAY。

#include<stdio.h>
#include<stdlib.h>

#define MaxVertexNum 50


typedef struct node
{
    int adjvex;
    struct node* next;
}EdgeNode;


typedef struct vnode
{
    char name;
    int father;
    int startTime;
    int endTime;
        
    EdgeNode *firstedge;

}VertexNode, AdjList[MaxVertexNum];


typedef struct
{
    AdjList Adj;
    int edgeNum, vertexNum;
}Graph;


typedef enum {WHITE, GRAY, BLACK} color;


color  Color[MaxVertexNum];

int time;


void InitGraph(Graph *G)
{
    int i, j, k;
    
    EdgeNode *s;
        
    printf("Input VertexNum  and EdgeNum :  ");
    scanf("%d %d", &G->vertexNum, &G->edgeNum);
    getchar();

    for(i = 0 ; i < G->vertexNum; i++)
    {
            

            scanf("%c", &G->Adj[i].name);
            getchar();
            

            G->Adj[i].firstedge = NULL;
            
            G->Adj[i].father = -1;
            
            Color[i] = WHITE;

    }

    printf("input edges, Create Adjacency List :
");
        
    for(k = 0 ; k < G->edgeNum; k++)
    {
        scanf("%d  %d", &i, &j);
        
        s = (EdgeNode*)malloc(sizeof(EdgeNode));
        
        s->adjvex = j;

        s->next = G->Adj[i].firstedge;

        G->Adj[i].firstedge  = s;



    /*   if the graph is undirected graph,
         release the following codes
        
        s = (EdgeNode *) malloc(sizeof(EdgeNode));

        s->adjvex = i;

        s->next = G->Adj[j].firstedge;

        G->Adj[j].firstedge = s;
    */
     }
}





void DFS_VISIT(Graph *G, int i)
{
    EdgeNode *p;
        
    time = time+1;

    G->Adj[i].startTime = time;

    Color[i] = GRAY;

     p = G->Adj[i].firstedge;

     while(p)
     {
         if(Color[p->adjvex]==WHITE)
         {
             G->Adj[p->adjvex].father = i;
             DFS_VISIT(G, p->adjvex);
         }
         p = p->next;
     }

     Color[i] = BLACK;
     time++;

     G->Adj[i].endTime = time;
}

void DFS(Graph *G)
{
    int i ;

    time = 0;
    for(i = 0; i < G->vertexNum; i++)
        if(Color[i] == WHITE)
            DFS_VISIT(G,i);
}


void PrintVisit(Graph *G, int source)
{
    EdgeNode *p;

    p = G->Adj[source].firstedge;

    printf("current node name : %c
", G->Adj[source].name);
    printf("current node connect to :
");

    while(p)
    {
        printf("node:%c   ", G->Adj[p->adjvex].name);
        p = p->next;
    }

    printf("

");

}


void PrintGraph(Graph *G)
{
    int i;
    for(i = 0 ; i < G->vertexNum ; i++)
        PrintVisit(G , i );

}




 int main()
 {
     Graph G;

     InitGraph(&G);

     PrintGraph(&G);

     DFS(&G);

         return 0;

 }

根据上面所化的图进行数据的输入是这样的

边：

S Z Y W X T V U 

 点：（0,1） （0,3）  （1,2）  （1,3）  （2,4） （3,4）  （4,1）

（6，0）  （6,3） （5,6） （5,7） （7,6） （7,5）

对于点的输入是这样的，

对应的是相应的点在G->Adj数组中的序号。

在控制台输入的时候是不需要添加括号和中间逗号的，

一组两个数，以空格分隔，回车换行接着输入下一条边。

例如第一个输入的是S符号，则说明S在Adj中的位序为0

而W是第四个输入的，在Adj中的位序3

如果想表示S->W 这条有向边的话，则在边输入的时候，输入0(空格)3

所以边的输入是要根据具体的点在Adj数组中的位序而定的。 

深度搜索在本文中是以递归实现的，

如果不适用递归的话，同样亦可以通过不断地压栈，

然后不断地弹栈来实现针对某一个结点的不断深入地搜索。

当 当前结点有三个子结点需要访问的时候，

如果默认是左优先，则把靠右边的两个结点全部压栈。

然后继续访问左结点的子结点，如此下去。

一旦当某一个结点再也找不到子结点的时候，

则弹栈，继续从弹出栈的结点进行深入访问，如此继续下去。

直到所有的结点都被访问后结束。