使用简单的数据结构在Bash脚本中进行深度优先搜索 [英] depth first search in Bash script using simple data structures

问题描述

我正在尝试如上所述.我设计了相对容易的广度优先搜索.

I'm trying to do as stated above. I have designed a breadth first search with relative ease.

该脚本的目标是创建用户输入的具有一定深度和广度的目录结构.我正在尝试更改我的广度优先实现以支持深度优先搜索.这是我得到的地方:

The goal of the script is to create a directory structure of a certain depth and breadth input by the user. I'm trying to alter my breadth first implementation to support depth first search. This is where I got:

depthsearch(){

  local open=("seed")
  local tmpopen=()
  local closed=()
  local x="seed"

  for((j=0;j<$depth;j++)); do    

    for x in "${open[@]}" ; do

      for ((i=0;i<$breadth;i++)); do
        tmpopen=("${tmpopen[@]}" "$x/$i")
        mkdir echo "$x/$i"
      done

      open=("${tmpopen[@]}" "${open[@]:1}")

      tmpopen=()
      closed=("${closed[@]}" "$x")

    done

    tmpopen=()

  done

}

好的，所以我简化了我的问题.显然问题是我没有按索引进行迭代，因此在进行迭代时无法更新我的循环.但是，我无法弄清楚如何通过索引进行迭代并更新数组，因此我可以先构造目录深度.任何示例将不胜感激.

Okay, so I trimmed down my question a bit. Apparently the problem was that I wasn't iterating by index, so I couldn't update my loop while it was iterating. However, I can't figure out how to iterate by index and update my array so I can construct my directories depth first. Any example would be appreciated.

推荐答案

如果不是严格必须使用数据结构，则可以通过简单的操作来做到这一点:

If it is not strictly necessary to use data structures, you can do it with a simple recusion:

#!/bin/bash
depth=4
breadth=3
node_id=0 #for testing, increments +1 each time a folder is created.

# args: level( [0,depth) ), childNo ( [0,breadth) ) 
generateTreeDFS(){
declare -i level=$1
declare -i childNo=$2
declare -i i=0
    if (( $level < $depth ));then
        mkdir "n_$childNo-$node_id"
        cd "n_$childNo-$node_id"
        let node_id++
        let level++

        while [ $i -lt $breadth ]
        do
            generateTreeDFS $level $i
            let i++
        done
        cd ..
    fi
}

如果我们打电话

generateTreeDFS 0 0

目录结构如下:

$ tree .

.
├── depthsearch.sh
└── n_0-0
    ├── n_0-1
    │   ├── n_0-2
    │   │   ├── n_0-3
    │   │   ├── n_1-4
    │   │   └── n_2-5
    │   ├── n_1-6
    │   │   ├── n_0-7
    │   │   ├── n_1-8
    │   │   └── n_2-9
    │   └── n_2-10
    │       ├── n_0-11
    │       ├── n_1-12
    │       └── n_2-13
    ├── n_1-14
    │   ├── n_0-15
    │   │   ├── n_0-16
    │   │   ├── n_1-17
    │   │   └── n_2-18
    │   ├── n_1-19
    │   │   ├── n_0-20
    │   │   ├── n_1-21
    │   │   └── n_2-22
    │   └── n_2-23
    │       ├── n_0-24
    │       ├── n_1-25
    │       └── n_2-26
    └── n_2-27
        ├── n_0-28
        │   ├── n_0-29
        │   ├── n_1-30
        │   └── n_2-31
        ├── n_1-32
        │   ├── n_0-33
        │   ├── n_1-34
        │   └── n_2-35
        └── n_2-36
            ├── n_0-37
            ├── n_1-38
            └── n_2-39

这篇关于使用简单的数据结构在Bash脚本中进行深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！