图论:8.2.图的遍历(深度优先、广度优先)

1.深度优先

DFS(v)

    num(v) = i++;

    for 所有与 v 邻接的节点 u

        if num(u)是0

            将edge(vu)连接到edges中;

            DFS(u);

 

depthFirstTraverse()

    for 所有向量 v

        num(v) = 0;

    edges = null;

    i = 1;

    while 有一个向量 v 使得 num(v) 是0

        DFS(v);

    输出edges;

 

2.广度优先

 

breadthFirstTraverse()

    for 所有顶点 u

        num(u) = 0;

    edges = null;

    i = 1;

    while 存在一个顶点 v 使得 num(v) 是0

        num(v) = i++;

        enqueue(v);

        while 队列非空

            v = dequeue();

            for 所有和 v 邻接的顶点 u

                if num(u) 是 0

                    num(u) = i++;

                    enqueue(u);

                    将edge(vu)连接到edges中;

    输出 edges;