Как определить, все ли объекты в массиве связаны в Swift - PullRequest
Новая
       50

Как определить, все ли объекты в массиве связаны в Swift

0 голосов
/ 26 февраля 2019

У меня есть массив (myArray) пользовательских объектов (MyObject).Каждый объект в массиве подключается как минимум к одному другому объекту в массиве (см. Код ниже). Я пытаюсь найти способ определить, все ли объекты в myArray связаны друг с другом. 

class MyObject {
    var id: Int = 0
    var connectedIds: [Int] = []
}

Если myArray содержит 5 элементов (A, B, C, D, E; A.id = 0, B.id = 1, ...), я хочу определить, все ли пять связаны каким-либо образом.Каждый объект имеет массив с именем connectedIds из id объектов, к которым он подключен (он не включает себя).

Например, это будет допустимо: 

print(A.connectedIds) // [1]
print(B.connectedIds) // [0, 2]
print(C.connectedIds) // [1, 4]
print(D.connectedIds) // [4]
print(E.connectedIds) // [2, 3]

... но это не так: 

print(A.connectedIds) // [1]
print(B.connectedIds) // [0]
print(C.connectedIds) // [3, 4]
print(D.connectedIds) // [2, 4]
print(E.connectedIds) // [2, 3]

Если смотреть графически (игнорировать красный кружок), это нормально: okay image

Но этоне: not okay image

Ответы [ 2 ]

0 голосов
/ 26 февраля 2019

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

    // Find route from an object to other object
    func findNewRoute(currentRoute: inout [Int], from: Int, to: Int) {
        currentRoute.append(from)
        let connectedObjects = (objects.filter { $0.id == from }.first!).connectedIds
        for index in connectedObjects {
            if !currentRoute.contains(index) {
                findNewRoute(currentRoute: &currentRoute, from: index, to: to)
            }
        }
    }

    // Check Validation
    func checkValid(group: [MyObject]) -> Bool {
        for object in objects {
            if !(objects.filter {
                element in
                var result:[Int] = []
                findNewRoute(currentRoute: &result, from: object.id, to: element.id)
                return !result.contains(element.id)
            }).isEmpty {
                return false
            }
        }
        return true
    }
0 голосов
/ 26 февраля 2019

Это проблема с графиком подключенного компонента .

. Вы можете запустить поиск в глубину на каждом узле и получить подключенный компонент.Если у вас есть более двух компонентов в результате, тогда да, весь объект не связан со всеми другими объектами. 

class MyObject {
  var id: Int = 0
  var connectedIds: [Int] = []
}

func isAlreadyVisited(n: MyObject, cc: inout [[MyObject]]) -> Bool {
  for c in cc {
    c.forEach {
      return ($0.id == n.id)
    }
  }
  return false
}

func connectedComponent(g: [MyObject]) -> [[MyObject]] {
  var cc = [[MyObject]]()
  for n in g {
    if !isAlreadyVisited(n: n, cc: &cc) {
      var c = DFS(n, g) // Use placeHolder for DFS, you can write your own
      cc.append(contentsOf: c)
    }
  }
  return cc
}

var cc = connectedComponent(g: [MyObject(), MyObject()])
...