shell - 使用awk遍历图

Question

考虑到以下表示循环图的文件，我正在寻找一个 shell 脚本来查找从图中任何节点开始的所有可达节点？

A.txt(每行的第一个元素是节点，其余是从它可达的相邻节点):

a3 a4
a2 a4 a5
a4 a5
a5 a6
a6 a7
a7 a8
a8 a9
a9 

所需的输出文件(B.txt 和 C.txt)必须是 DFS 或 BFS 的输出，并且包括从任何起始节点到其可达节点的深度(距离)。像这样的东西:

B.txt

a3 a4 a5 a6 a7 a8 a9
a2 a4 a5 a6 a7 a8 a9
a4 a5 a6 a7 a8 a9
a5 a6 a7 a8 a9
a6 a7 a8 a9
a7 a8 a9
a8 a9
a9 

C.txt

0 1 2 3 4 5 6
0 1 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4
0 1 2 3
0 1 2
0 1
0 

Awk 是首选，尽管任何类型的 shell 脚本都可以。

Answer 1

改编自https://stackoverflow.com/a/25085230/1745001 ，这是一个 awk 解决方案:

$ cat tst.awk
function calcMinDepth(parent,  childArray, childNr, child) {
    ++depth
    split(children[parent],childArray)
    for (childNr=1; childNr in childArray; childNr++) {
        child = childArray[childNr]
        if ( (minDepth[origin,child] > depth) ||
                (minDepth[origin,child] == 0) ) {
            minDepth[origin,child] = depth
            calcMinDepth(child)
        }
    }
    --depth
    return
}

function prtInfo(parent,  childArray, childNr, child) {
    split(children[parent],childArray)
    for (childNr=1; childNr in childArray; childNr++) {
        child = childArray[childNr]
        if (!seen[child]++) {
            printf " %s", child > "B.txt"
            printf " %d", minDepth[origin,child] > "C.txt"
            prtInfo(child)
        }
    }
    return
}

{
    parents[++numParents] = $1
    for (i=2; i<=NF; i++) {
        children[$1] = (i>2 ? children[$1] FS : "") $i
    }
}

END {
    for (parentNr=1; parentNr<=numParents; parentNr++) {
        origin = parents[parentNr]
        calcMinDepth(origin)
    }

    for (parentNr=1; parentNr<=numParents; parentNr++) {
        origin = parents[parentNr]
        printf "%s", origin > "B.txt"
        printf "%d", depth  > "C.txt"
        prtInfo(origin)
        print "" > "B.txt"
        print "" > "C.txt"
        delete seen     # or split("",seen) for non-gawk
    }
}

.

$ awk -f tst.awk file

$ cat B.txt
a3 a4 a5 a6 a7 a8 a9
a2 a4 a5 a6 a7 a8 a9
a4 a5 a6 a7 a8 a9
a5 a6 a7 a8 a9
a6 a7 a8 a9
a7 a8 a9
a8 a9
a9

$ cat C.txt
0 1 2 3 4 5 6
0 1 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4
0 1 2 3
0 1 2
0 1
0