I create a myGraph class as shown below. Then I created an instance of the graph by giving the adjacency list as a NSDictionary and then call the isGraphCycleFree method. Will this answer look good if asked during an interview programming round?

Initializing the myGraph class and calling the isGraphCycleFree method

NSDictionary *graphAdjacencyList = @{@(0): @[@(1),@(2)],
                                             @(1): @[@(3)],
                                             @(2): @[@(4)],
                                             @(3): @[@(2)],
                                             @(4): @[@(3)]
        myGraph *newGraph = [[myGraph alloc] initWithAdjacencyList:graphAdjacencyList];

        if([newGraph isGraphCycleFree])
            NSLog(@"Graph is cycle free");
            NSLog(@"Graph has a cycle");

.h of the myGraph class

@interface myGraph : NSObject

-(instancetype) initWithAdjacencyList:(NSDictionary <NSNumber*,NSArray*>*)adjacencyList;

-(BOOL) isGraphCycleFree;


.m of the myGraph class

@interface myGraph()

@property NSDictionary <NSNumber*,NSArray*>*adjacencyList;


@implementation myGraph

-(instancetype) initWithAdjacencyList:(NSDictionary <NSNumber*,NSArray*>*)adjacencyList
    self = [super init];
    if (self) {
        _adjacencyList = adjacencyList;

    return self;

    -(BOOL) isGraphCycleFree
        //DO a DFS from any node (pick first node that is a key in adjacency list).
        NSNumber *firstNode = [[self.adjacencyList allKeys] objectAtIndex:0];

        return [self dfsWithStartNode:firstNode withVistedSet:nil];

    -(BOOL) dfsWithStartNode:(NSNumber *)visitedNode withVistedSet:(NSMutableSet *)visitedSet

        if(visitedSet != nil)
            if ([visitedSet containsObject:visitedNode]) {
                return FALSE; //Visiting a node that os alreday in visited set == Cycle
            visitedSet = [[NSMutableSet alloc] init];

        [visitedSet addObject:visitedNode];

        for (NSNumber *nextEdge in self.adjacencyList[visitedNode])
            NSLog(@"from %@ Calling dfs on node %@ with visited list %@",visitedNode,nextEdge,visitedSet);
            if([self dfsWithStartNode:nextEdge withVistedSet:[visitedSet mutableCopy]] == FALSE)
                return FALSE;

        return TRUE;


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.