Last active
August 29, 2015 14:00
-
-
Save yulingtianxia/11142742 to your computer and use it in GitHub Desktop.
用DFS算法计算SpriteKit中复合体的构成
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// Graph.h | |
// ColorAtom | |
// | |
// Created by 杨萧玉 on 14-4-21. | |
// Copyright (c) 2014年 杨萧玉. All rights reserved. | |
// | |
#import <Foundation/Foundation.h> | |
@import SpriteKit; | |
@interface Graph : NSObject | |
@property NSMutableArray *nodes;//节点数组 | |
@property NSMutableArray *sets;//子图(联通图)数组,数组每个元素都是个集合,集合中包含这个子图中所有的node | |
-(id) initWithNodes:(NSArray*) nodeArr; | |
-(void)DFSVisitNode:(SKSpriteNode *) node; | |
@end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// Graph.m | |
// ColorAtom | |
// | |
// Created by 杨萧玉 on 14-4-21. | |
// Copyright (c) 2014年 杨萧玉. All rights reserved. | |
// | |
#import "Graph.h" | |
@implementation Graph | |
@synthesize nodes; | |
@synthesize sets; | |
-(id) initWithNodes:(NSArray*) nodeArr{ | |
if (self=[super init]) { | |
//初始化所有节点,将其访问信息设置为未被访问 | |
nodes = [NSMutableArray arrayWithArray:nodeArr]; | |
sets = [NSMutableArray array]; | |
for (int i=0; i<[nodes count]; i++) { | |
// The userData property is initially nil. You have to create a dictionary and assign it first | |
((SKSpriteNode *)nodes[i]).userData = [NSMutableDictionary dictionary]; | |
[((SKSpriteNode *)nodes[i]).userData setObject:@"WHITE" forKey:@"visited"]; | |
} | |
//遍历数组nodes中所有节点,如果节点未被访问,则调用深度优先搜索算法访问之 | |
for (int i=0; i<[nodes count]; i++) { | |
if ([[((SKSpriteNode *)nodes[i]).userData objectForKey:@"visited"] isEqualToString:@"WHITE"]) { | |
[sets addObject:[NSMutableSet setWithObject:nodes[i]]]; | |
[self DFSVisitNode:nodes[i]]; | |
} | |
} | |
} | |
return self; | |
} | |
//深度优先搜索算法 | |
-(void)DFSVisitNode:(SKSpriteNode *) node{ | |
[node.userData setObject:@"GRAY" forKey:@"visited"];//将节点node标记为正在访问 | |
NSArray *adj = node.physicsBody.joints;//获得节点node的所有的边 | |
for (int i = 0; i<[adj count]; i++) { | |
//根据边adj[i]来找到与节点node相连的另一个节点v | |
SKPhysicsJoint *joint = adj[i]; | |
SKSpriteNode *v; | |
if ([joint.bodyA isEqual:node.physicsBody]) { | |
v = (SKSpriteNode *)joint.bodyB.node; | |
} | |
else{ | |
v = (SKSpriteNode *)joint.bodyA.node; | |
} | |
//如果v没被访问过,那就将其纳入节点node所在的集合,并记录节点v的父节点为node | |
if ([[v.userData objectForKey:@"visited"] isEqualToString:@"WHITE"]) { | |
[v.userData setObject:node forKey:@"parent"]; | |
for (int j=0; j<[sets count]; j++) { | |
if ([sets[j] containsObject:node]) { | |
[sets[j] addObject:v]; | |
} | |
} | |
[self DFSVisitNode:v];//递归访问节点v的子结点 | |
} | |
} | |
[node.userData setObject:@"BLACK" forKey:@"visited"];//将节点node标记为访问结束 | |
} | |
@end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment