已经学会的图的表示方法有这几种
1.邻接矩阵
2.邻接表(静态链表)
3.链式前向星
4.前向星
假设读入数据为
起点 | 终点 | 权值 |
1 | 2 | 5 |
1 | 3 | 3 |
2 | 3 | 4 |
4 | 5 | 2 |
5 | 3 | 1 |
6 | 5 | 4 |
边数为Edges;
一、邻接矩阵
for(k=1;k<=Edges;k++){ fscanf("%d %d %d",&i,&j,&Value); Matrix[i][j]=Value; }
二、邻接表
本来应该使用链表,可以节省空间
为了避免链表操作的繁琐和易错性,用数组来模拟链表
memset(Link,0,sizeof(Link)); for(k=1;k<=Edges;k++){ fscanf("%d %d %d",&i,&j,&Value); Link[i][LvN[i]][0]=j; Link[i][LvN[i]][1]=Value; LvN[i]++; }
LvN[i]记录节点i的邻接边的数量
查找所有以i为起点的边:
for(k=0;k<LvN[i];i++){ Action(Link[i][k][0]); }
三、链式前向星
由于使用静态链表仍然可能比使用动态链表需要更大的空间开销
所以可以改用链式前向星,其实质仍然是邻接表
我们用e[i]记录第i条边的目标节点
Value[i]记录第i条边的权值
用head[i]记录以i为起点的边所对应下标
用next[i]记录同起点的下一条边的下标
memset(next,0,sizeof(next)); memset(head,0,sizeof(head)); for(k=1;k<=Edges;k++){ fscanf("%d %d %d",&i,&j,&v); e[k]=j; next[k]= head[i]; head[i]=k; Value[k]=v; }
读入完毕后,数组的状态:
1 | 2 | 3 | 4 | 5 | 6 | |
head | 2 | 3 | 0 | 4 | 5 | 6 |
e | 2 | 3 | 3 | 4 | 3 | 5 |
next | 0 | 1 | 0 | 0 | 0 | 0 |
如果要查找所有以1为起点的边可以这样
i=head[1]; while(i!=0){ Action(e[i]); i=next[i]; }
四、前向星
由于刘汝佳的书上面的前向星实在是看不懂,研究了一晚上弄懂了也值得了
同链式前向星一样,用e[i]记录第i条边的目标节点
用数组st[i]来记录第一条以i为起点的边的下标-------这个表示要求:读入的边必须按照起点从小到大进行排序
那么以i为起点的边的下标则必然在区间[st[i],st[i+1])内
由于需要对边进行排序,我们假定从邻接矩阵中读入数据:
m=0,u=0; for(i=1;i<=N;i++){ for(j=1;j<=N;j++){ if(Map[i][j]){ e[++m]=j; while(u<i) st[++u]=m; } } }
此时数组的状态为
1 | 2 | 3 | 4 | 5 | 6 | |
e | 2 | 3 | 3 | 5 | 3 | 5 |
st | 1 | 3 | 4 | 4 | 5 | 6 |
刘汝佳的书上还介绍了一种将前向星转化为根树的方法:
void star2lsrs () { memset (son , 0 , sizeof ( son )); /*清零,为零代表链表为空son */ for (i = 1; i <= n ; i ++) /*按逆序考虑各个结点,则最后的链表是顺序的*/ for (j = st [i +1] -1; j >= st [i ]; j - -) { bro [j ] = son [i ]; son [i ] = e[j ]; /*插到链表首部*/ } }
该例程将起点为1的点作为树根建树,依次将以起点从小到大排列的边插入树中
听说还有一种叫后向星,十字矩阵等等表示,暂时还没学到也没用到,如果以后用到再添加