четверг, 28 июля 2011 г.

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

#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))

Комментариев нет:

Отправить комментарий