DFS算法实现在Objective C

-1

我正在尝试实现此算法的Objective C实现。在这里它的实现：DFS算法实现在Objective C

@implementation DFSAlgorithm 
    -(void)dfs:(Graph*)g andStartingPosition:(int)s{ 
     [self performDFS:g andPosition:s]; 
    } 
    -(void)markedArrayInit:(int)capacity{ 
      //0 is for unmarked vertices 
      //1 is form marked ones 
      self.marked=[[NSMutableArray alloc]initWithCapacity:capacity]; 
      for(int i=0;i<[self.marked count];i++) 
       [self.marked replaceObjectAtIndex:i withObject:[NSNumber numberWithInt:0]]; 
     } 
     -(void)performDFS:(Graph *)g andPosition:(int)v{ 
       [self markedArrayInit:(int)[g numberOfVertices]]; 
       [self.marked replaceObjectAtIndex:v withObject:[NSNumber numberWithInt:1]]; 
    for (NSNumber *vertex in [g.vertices objectAtIndex:v]){ 
     if(1==[self isMarked:v atGraph:g]){ 
      NSLog(@"%d",(int)vertex); 
      [self performDFS:g andPosition:(int)vertex]; 
     } 
    } 
    } 
      -(int)isMarked:(int)v atGraph:(Graph *)g{ 
      return [self.marked objectAtIndex:v]; 
     } 
      @end

不过，我不明白为什么会出现以下错误：

[__NSArrayM replaceObjectAtIndex:withObject:]: index 0 beyond bounds for empty array'

我该如何正确初始化数组明显？

谢谢。

来源

2015-04-12 mr.M

的NSMutableArray创建空的，你通过了容量值仅仅是一个暗示，实现你期望有多大的阵列就成了。

因此replaceObjectAtIndex:withObject:不适合你，因为数组是空的，所以你没有要替换的对象。

取而代之的只是使用addObject:capacity次。

来源

2015-04-12 18:42:27 CRD

谢谢！从我身边真的是愚蠢的问题=） –

-1

您尝试更换阵列中不存在的对象。在markedArrayInit使用来自NSMutableArray的addObject:方法。 [self.marked count]始终为0进行循环。

来源

2015-04-12 18:39:15 vojer

在您的markedArrayInit方法中，您将创建空的可变阵列并为其保留至少capasity项目数的内存。但是你实际上并没有添加任何东西（for循环中的这个方法实际上并没有做任何事情）。要解决你的问题，你可以在for循环中添加项目的足够数量：

for (int i=0;i< initWithCapacity:capacity;i++) 
     [self.marked addObject: @0]; 
}

编辑： 你实现了其他几个问题：

你在每次调用performDFS:andPosition:初始化marked阵列，并递归调用该方法。你应该将初始化dfs:andStartingPosition:方法
在isMarked:atGraph:方法从数组的形式返回对象，而不是其持有的数值 - 所以它永远不会是1，你可能想用下面的实现来代替它（注意方法名意味着我们返回一些布尔值，而不是我们需要在后面解释整数）：
```
-(BOOL)isMarked:(int)v atGraph:(Graph *)g { 
    return [self.marked[v] intValue] == 1; 
} 

... 
if([self isMarked:v atGraph:g]){ 
    ... 
} 
```
有会更好的数据结构来存储标节点，例如指数NSSet或NSIndexSet

来源

2015-04-12 18:39:49 Vladimir

DFS算法实现在Objective C

回答

相关问题