2015-04-12 77 views
-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' 

我該如何正確初始化數組明顯?

謝謝。

回答

2

NSMutableArray創建空的,你通過了容量值僅僅是一個暗示,實現你期望有多大的陣列就成了。

因此replaceObjectAtIndex:withObject:不適合你,因爲數組是空的,所以你沒有要替換的對象。

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

+0

謝謝!從我身邊真的是愚蠢的問題=) –

-1

您嘗試更換陣列中不存在的對象。在markedArrayInit使用來自NSMutableArray的addObject:方法。 [self.marked count]始終爲0進行循環。

1

在您的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]){ 
        ... 
    } 
    
  • 有會更好的數據結構來存儲標節點,例如指數NSSetNSIndexSet