1
\$\begingroup\$

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");
        else
            NSLog(@"Graph has a cycle");

.h of the myGraph class

@interface myGraph : NSObject

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

-(BOOL) isGraphCycleFree;

@end

.m of the myGraph class

@interface myGraph()

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

@end


@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
            }
        }
        else
        {
            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;
    }

    @end
\$\endgroup\$

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.