图是由一组顶点和一组能够将两个顶点连接的边组成的，两个顶点通过一条边相连的时，我们称这两个顶点是相邻的，并称这条边依附于两个顶点，某个顶点的都市即为依附于它的边的总数。图是一种比线性表和树更复杂的数据结构，树算是图的一种特殊情况下的数据结构（无环连通图），图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例，如果一幅图中不同的边的数量只占顶点总数的一小部分，那么图称之为稀疏图，反之是稠密图。
无向图基础
我们首先来来看一个最基本的图:
我们需要一个数据结构能够快速的处理开发过程的各种用例，有三种可选方式，邻接矩阵（当节点的数量太大的时候不能满足需求），边的数组，我们可以通过实例化一个类，保存两个节点的变量，但是实现起来效率很低，第三种就是邻接表数组，以一个顶点为索引的相邻数组，使用的空间是边和顶点的和，添加一条边的时间为常数。现在我们通过代码实现邻接表的形式，代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
@
interface
Graph : NSObject
//顶点的数量
@property (assign,nonatomic) NSInteger vertexs;
//边的数量
@property (assign,nonatomic) NSInteger edges;
//连接点的边
@property (strong,nonatomic) NSMutableArray *adjDataSource;
-(instancetype)initWithVertex:(NSInteger)vertexs;
//添加一条链接它们的边
-(
void
)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex;
@end
|
实现:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
@implementation Graph
-(instancetype)initWithVertex:(NSInteger)vertexs{
self=[super init];
if
(self) {
self.vertexs=vertexs;
for
(NSInteger i=0; i<vertexs; i++) {
NSMutableArray *neighbourVertex=[[NSMutableArray alloc]initWithCapacity:1];
[self.adjDataSource addObject:neighbourVertex];
//创建邻接表,将所有链表初始化为空
}
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang
-(
void
)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex{
//将endVertex添加到startVertex的链表中
[self.adjDataSource[startVertex] insertObject:[NSNumber numberWithInteger:endVertex] atIndex:0];
//将startVertext添加到endVertex的链表中
[self.adjDataSource[endVertex] insertObject:[NSNumber numberWithInteger:startVertex] atIndex:0];
self.edges=self.edges+1;
}
#pragma mark getter and setter
-(NSMutableArray *)adjDataSource{
if
(!_adjDataSource) {
_adjDataSource=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_adjDataSource;
}
@end
|
算法测试
关于无向图的测试比较简单，节点是自己自己手动添加进去的，当然如果有数据源直接测试效果会更好:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
Graph *graph=[[Graph alloc]initWithVertex:13];
[graph addEdges:0 endVertex:1];
[graph addEdges:0 endVertex:2];
[graph addEdges:0 endVertex:5];
[graph addEdges:0 endVertex:6];
[graph addEdges:3 endVertex:4];
[graph addEdges:3 endVertex:5];
[graph addEdges:4 endVertex:5];
[graph addEdges:4 endVertex:6];
[graph addEdges:7 endVertex:8];
[graph addEdges:9 endVertex:10];
[graph addEdges:9 endVertex:11];
[graph addEdges:9 endVertex:12];
[graph addEdges:11 endVertex:12];
for
(NSInteger i=0; i<[graph.adjDataSource count]; i++) {
NSLog(
@"节点%ld:相邻的节点:%@"
,i,[graph.adjDataSource[i] componentsJoinedByString:
@"--"
]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
实际应用中我们可能会需要删除边检查图种是否还有某一条边，实现这些操作我们可以通过顺序链表代替目前的数组结构，不过会稍微麻烦一点，因为图本来就比较麻烦，本来是打算无向图的深度搜索和广度搜索一起写的，考虑放在一个文章里面会显的阅读起来不是很方便，本文算是图的基本入门知识。深度搜素和广度搜索接下来文章会补上。
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4691102.html，如需转载请自行联系原作者
