默写图DFS算法

========================

所谓默写，就是合上书本，不依靠浏览器、编译器、记事本等外物，仅凭记忆去写下所要求的知识、文字等。本不必如此麻烦，我也不想如此，不过他们太卷了，那就来吧。

int visit[maxSize];//全局数组，记录结点是否被访问，maxSize为事先定义的数组上限。
void DFS(AGraph *G, int v){ // 图G，顶点v
    ArcNode *p; //定义边
    visit[v] = 1; //记录顶点被访问
    Visit(v); //事先定义好的访问顶点的函数
    p = G->adjlist[v].firstArc; //将p指向图的第一条边
    while(p!=NULL){
        if(visit[p->adjvex] == 0) {//如果顶点未被访问
            DFS(G, p->adjvex);//递归访问
        }
        p=p->nextArc;//p指向v的下一条边
    }
}

默写结果

完全正确

总结

DFS属于核心且简单的内容，而且也很多变，所以还是需要领悟其真正的奥义才能灵活运用。另外，图的DFS遍历与二叉树的先序遍历类似，可以理理二者之间的相似与不同之处。
上述算法主要针对连通图，针对非连通图可以写一个循环，遍历未被访问的顶点，然后对该点进行上述的DFS算法,相当于是将非连通图拆成若干个连通图，然后一一进行DFS算法。

void dfs(Agraph *g) {
    for(int i=1;i<g->n;i++){
        if(visit[i] == 0){
            DFS(g, i);
        }
    }
}