前面实现的邻接矩阵面临一个巨大的问题:对于稀疏矩阵,将耗费巨大的资源,而大部分都是0。
现实中,绝大多数矩阵都是稀疏的!
我们可以采用如下的邻接表方法存储。
首先定义每个弧如下:
ivex是在顶点在数组中的下标。
next是一条链表,即某个顶点i的所有邻接结点的弧组成。
// Arc
struct Arc
{
int ivex; // The vex position in vexs array
struct Arc* next;
};
然后对于每[......]
前面实现的邻接矩阵面临一个巨大的问题:对于稀疏矩阵,将耗费巨大的资源,而大部分都是0。
现实中,绝大多数矩阵都是稀疏的!
我们可以采用如下的邻接表方法存储。
首先定义每个弧如下:
ivex是在顶点在数组中的下标。
next是一条链表,即某个顶点i的所有邻接结点的弧组成。
// Arc
struct Arc
{
int ivex; // The vex position in vexs array
struct Arc* next;
};
然后对于每[......]
可以用两个数组分别存储数据元素(顶点)、数据元素之间的关系(边或弧度)。
顶点数组不说了,表示弧的数组称为“邻接矩阵”AdjMatrix。
对于有向图:AdjMatrix[i][j]为0表示顶点i和顶点j之间无弧,1为i和j间有弧。
对于无向图:AdjMatrix[i][j]同样是1表示有弧,0无弧。单AdjMatrix[i][j]为1则一定有AdjMatrix[j][i]为1,因为弧是无方向对称的。
对于网(弧带权):AdjMatrix[i][j]上是w或者无穷大,w表[......]
1、在图结构中,结点关系是任意的:任意两个数据元素(结点)之间都可能有关系。
2、有向图可以表示为G={V, A},V是顶点集合,A是关系(边)的集合,也可称作VR。关系(边)用有序对<v, w>表示。图形表示是一条有向弧。v是初始点(弧尾),w是终端点(狐头)。
3、无向图一般表示为G={V, E},V还是顶点集合,E是边集合。边用无序对(v, w)表示。图形表示是一条边(无向)。
有向图G1:
A1 = {[......]