【LSP】数据结构——图—概念和存储（邻接矩阵，邻接表）
http://cdn.u1.huluxia.com/g4/M01/5B/42/rBAAdl9u_nuAeYirAACt4WdlvYs568.jpg
图的储存-邻接表
http://cdn.u1.huluxia.com/g4/M01/5B/42/rBAAdl9u_nyAVCLDAABXZabMssU022.jpg
邻接表的基本概念
1.为什么要有邻接表
可以想象如果有一个图他的顶点特别多而边只有一个？那么是不是用邻接矩阵特别浪费内存呢？
所以需要邻接表（不同于邻接表主要以链表形式实现）
2.怎么理解邻接表呢？
首先看上面b图，最边上的表我们给他起名——顶点表；其他的我们给另外的变我们给他起名边表；
3.顶点表
顶点表用来开始储存图中的各个顶点，可以看到我们给顶点表开辟了两个域，第一个域存放了顶点了第二个域呢？
我们可以看出来顶点表的第二个域指向了边表，所以在顶点表的第二个域里面我们存放边表类型让他变成边表的头结点指向边表；
4.边表
上图中边表有两个域一个存放和顶点边中有关系的顶点，另外一个也就是他的NEXT域和链表一样在后面没有时他指向为空，其实还可以给他加第三个域比如权值等等这个很简单了
这样各个就形成了一个邻接表了
邻接表的实现
首先是定义这个结构体类型
/*
下面代码的总体意思就是先定义边表我们给了他3个域分别是顶点域 权值域和next域
在定义顶点表 他有两个域分别是顶点域和代表边表头结点的first_v域
最后我们定义一个顶点表的顺序表类型。类似于图b中最左边的那个顺序表
这样一个邻接表就定义好了
*/
typedef int VertexType;/*顶点类型有用户定义*/
typedef struct EdgeNode//定义边表
{
int adjvex;//邻接点域 里面放各个和顶点表对应节点有关的顶点
int weight;//权值
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode /*定义顶点表*/
{
VertexType data;//顶点域，存储顶点信息
EdgeNode *first_v;//边表的头指针
}VertexNode;
typedef struct //邻接表
{
VertexNode adjlist; //用于存放头结点和顶点的顺序表；
int n_v,n_e;
}LinkdeGraph;
创建邻接表
/*
下面代码的主要含义是
1.先获取到图中的顶点数和边数，然后以顶点数为最大创建顶点表数组并且初始化
2.然后定义一个边表类型，输入某个边上的两个顶点，并且用头插发插入
边的表示（vi vj）表示连接vi vj的边
3.函数解释
大概意思就是接收到边上的两个顶点后，把和i有边的j节点用头插发插在顶点表中有i顶点那一段之后；http://cdn.u1.huluxia.com/g4/M01/5B/42/rBAAdl9u_n2ACxi7AAKimDqtRMQ912.jpg
页:
[1]