алгоритм топологической сортировки

#topology sorting

$m = @(
    @(0    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0),
    @(1    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0),
    @(0    ,    1    ,    0    ,    1    ,    0    ,    0    ,    1    ,    0),
    @(0    ,    0    ,    0    ,    0    ,    1    ,    0    ,    0    ,    0),
    @(0    ,    0    ,    0    ,    0    ,    0    ,    1    ,    0    ,    0),
    @(0    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0    ,    0),
    @(0    ,    0    ,    0    ,    0    ,    1    ,    0    ,    0    ,    0),
    @(0    ,    0    ,    1    ,    0    ,    0    ,    0    ,    0    ,    0)
)

$a = @(
   
)

function matrixprint($matrix){
    for($i = 0; $i -lt $matrix.Length; $i++){
        $str = [System.String]::Join(",", $matrix[$i])
       
        Write-Host $str
    }
}

function topsorting($matrix){
    $vect = @()
    $points = 0..$($matrix.Length - 1)
   
    $p = $points | where {$_ -ge 0}
   
    while ($p.Length -ne 0){
        for ($i = 0; $i -lt $p.Length; $i++){
            $sum = 0
            for ($j = 0; $j -lt $matrix.Length; $j++){
                $sum += $matrix[$j][$p[$i]]
                if ($sum -gt 0){
                    break
                }
            }
            if ($sum -eq 0) {
                for ($k = 0; $k -lt $matrix.Length; $k++){
                    $matrix[$p[$i]][$k] = 0
                }
                $vect += $p[$i]
                $points[$p[$i]] = -1
                break
            }
        }
        $p = @()
        for($i = 0; $i -lt $points.Length; $i++){
            if ($points[$i] -ge 0){
                $p += $points[$i]
            }
           
        }
    }
    return $vect
}

cls

#matrixprint $m
[System.String]::Join("-", (topsorting $m))

Алгоритм поиска минимального остовного дерева

cls

$m = @(
    @(0,  13, 3,  9,  9),
    @(13, 0,  11, 11, 13),
    @(3,  11, 0,  9,  7),
    @(9,  11, 9,  0,  2),
    @(9,  13, 7,  2,  0)
)

$a = @(
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0)
)

$atemp = @(
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0),
    @(0,  0,  0,  0,  0)
)

function copyarr($source, $dest){
    for($i=0; $i -lt $source.Length; $i++){
        for($j=0; $j -lt $source[$i].Length; $j++){
            $dest[$i][$j] = $source[$i][$j]   
        }
    }
}

function matrixdost($matrix){
    #алгоритм уоршела, для вычисления матрицы достижимости
    for ($k = 0; $k -lt $matrix.Length; $k++){
        for ($i = 0; $i -lt $matrix.Length; $i++){
            for ($j = 0; $j -lt $matrix.Length; $j++){
                $matrix[$i][$j] = $matrix[$i][$j] -or ($matrix[$i][$k] -and $matrix[$k][$j])
            }
        }
    }
}

function matrixsv($matrix){
    $v = @()
    $a = @()
    [object[]]$all = @()
    for($i = 0; $i -lt $matrix.Length; $i++){
        $v += 1
    }
   
    #компоненты связанности
    for($i = 0; $i -lt $v.Length; $i++){
        $a = @()
        if ($v[$i] -eq 0){
            continue
        }
        for($j = 0; $j -lt $v.Length; $j++){
            if ($matrix[$i][$j]){
                $a += $j
                $v[$j] = 0
            }
        }
        if ($a.Length -ne 0){
            $all += [object]$a
            $all += "-"
        }
    }
   
    for ($i=0; $i -lt $v.Length; $i++){
        if ($v[$i] -eq 1){
            $all += $i
            $all += "-"
        }
    }
   
    return $all
}

function numedges($matrix, $points){
    $num = 0
    for($i = 0; $i -lt $points.Length - 1; $i++){
        for($j = $i + 1 ; $j -lt $points.Length; $j++){
            if ($matrix[$points[$i]][$points[$j]] -ne 0){
                $matrix[$points[$j]][$points[$i]] = 0
                $num++
            }
        }
    }
    return $num
}

function iscycle($matrix){
    copyarr $matrix $atemp
    matrixdost $atemp
    $sv = matrixsv $atemp
    $points = @()
   
    for($i = 0; $i -lt $sv.Length; $i++){
        if ($sv[$i] -eq "-"){
            copyarr $matrix $atemp
            if ($points.Length -gt 2){
                $num = numedges -matrix $atemp -points $points
                if ($num -ge $points.Length){
                    return $true
                }
            }
            $points = @()
        }
        else {
            $points += $sv[$i]
        }
    }
    return $false
}

function matrixminel($matrix){
    $min = @(0,0,0)
    for ($i = 1; $i -lt $matrix.Length; $i++){
        for($j = 0; $j -lt $i; $j++){
            if (($matrix[$i][$j] -ne 0 -and $min[0] -gt $matrix[$i][$j]) -or ($min[0] -eq 0)){
                $min[0] = $matrix[$i][$j]
                $min[1] = $i
                $min[2] = $j
            }
        }
    }
    return $min
}

function matrixprint($matrix){
    for($i = 0; $i -lt $matrix.Length; $i++){
        $str = [System.String]::Join(",", $matrix[$i])
        Write-Host $str
    }
}

matrixprint $m

$minel = matrixminel $m

while ($minel[0] -ne 0){
    $a[$minel[1]][$minel[2]] = $minel[0]
    $a[$minel[2]][$minel[1]] = $minel[0]
    $m[$minel[1]][$minel[2]] = 0
    $m[$minel[2]][$minel[1]] = 0
   
    if (iscycle $a){
        $a[$minel[1]][$minel[2]] = 0
        $a[$minel[2]][$minel[1]] = 0
    }
   
    $minel = matrixminel $m
}

"-----------------" | Out-Host
matrixprint $a

Алгоритм ближайшего соседа

#Алгоритм ближайшего соседа, для поиска наименьшего (субоптимального) гамильтонового цикла

cls

$m = @(
    @(0,  5,  6,  8),
    @(5,  0,  7,  10),
    @(6,  7,  0,  3),
    @(8,  10, 3,  0)
)

function minel($vect){
    $mini = 0
    $min = $vect[$mini]
   
    for ($i = 1; $i -lt $vect.Length; $i++){
        if (($min -gt $vect[$i] -and $vect[$i] -ne 0) -or $min -eq 0){
            $min = $vect[$i]
            $mini = $i
        }
    }
    return $mini
}

function clnei($matrix, $v){
    #Алгоритм ближайшего соседа, для поиска наименьшего (субоптимального) гамильтонового цикла
    $sum = 0
    $mini = $v
    $path = @($mini)
    for($i = 0; $i -lt ($matrix.Length - 1); $i++){
        $a = $mini
        $mini = minel -vect $matrix[$mini]
        $sum += $matrix[$a][$mini]
        $path += $mini
        $matrix[$a][$mini] = 0
        $matrix[$mini][$a] = 0
    }
    $path += $v
    $sum += $matrix[$mini][$v]
    $path
    $sum
}

$res = clnei -matrix $m -v 0
[System.String]::Join(",", $res)

Алгоритм связности

cls

function matrixdost($matrix){
    #алгоритм уоршела, для вычисления матрицы достижимости
    for ($k = 0; $k -lt $matrix.Length; $k++){
        for ($i = 0; $i -lt $matrix.Length; $i++){
            for ($j = 0; $j -lt $matrix.Length; $j++){
                $matrix[$i][$j] = $matrix[$i][$j] -bor ($matrix[$i][$k] -band $matrix[$k][$j])
            }
        }
    }
}

function matrixprint($matrix){
    for($i = 0; $i -lt $matrix.Length; $i++){
        $str = [System.String]::Join(",", $matrix[$i])
        Write-Host $str
    }
}

function matrixsv($matrix){
    $v = @()
    $a = @()
    [object[]]$all = @()
    for($i = 0; $i -lt $matrix.Length; $i++){
        $v += 1
    }
  
    #компоненты связанности
    for($i = 0; $i -lt $v.Length; $i++){
        $a = @()
        if ($v[$i] -eq 0){
            continue
        }
        for($j = 0; $j -lt $v.Length; $j++){
            if ($matrix[$i][$j] -eq 1){
                $a += $j
                $v[$j] = 0
            }
        }
        if ($a.Length -ne 0){
            $all += [object]$a
            $all += "-"
        }
    }
  
    for ($i=0; $i -lt $v.Length; $i++){
        if ($v[$i] -eq 1){
            $all += $i
            $all += "-"
        }
    }
  
    return $all
}

$m = @(
    @(0, 0, 0, 0, 0, 1, 0, 1),
    @(0, 0, 0, 0, 1, 0, 0, 0),
    @(0, 0, 0, 0, 0, 1, 0, 1),
    @(0, 0, 0, 0, 1, 0, 0, 0),
    @(0, 1, 0, 1, 0, 0, 0, 0),
    @(1, 0, 1, 0, 0, 0, 0, 0),
    @(0, 0, 0, 0, 0, 0, 0, 0),
    @(1, 0, 1, 0, 0, 0, 0, 0)
)

matrixprint $m
matrixdost $m

"-------------"
matrixprint $m

$svcomp = matrixsv $m
$str = [System.String]::Join(",", $svcomp)

Write-Host $str

алгоритм Уоршелла

cls

function matrixdost($matrix){
    #алгоритм уоршела, для вычисления матрицы достижимости
    for ($k = 0; $k -lt $matrix.Length; $k++){
        for ($i = 0; $i -lt $matrix.Length; $i++){
            for ($j = 0; $j -lt $matrix.Length; $j++){
                $matrix[$i][$j] = $matrix[$i][$j] -bor ($matrix[$i][$k] -band $matrix[$k][$j])
            }
        }
    }
}

function matrixprint($matrix){
    for($i = 0; $i -lt $matrix.Length; $i++){
        $str = [System.String]::Join(",", $matrix[$i])
        Write-Host $str
    }
}



$m = @(
    @(0, 1, 0, 0),
    @(0, 0, 0, 0),
    @(0, 1, 0, 0),
    @(0, 0, 0, 0)
)

matrixprint $m
matrixdost $m
"-------------"
matrixprint $m