现在的位置: 首页 > 综合 > 正文

图的几种表示方法

2017年10月17日 ⁄ 综合 ⁄ 共 1526字 ⁄ 字号 评论关闭

已经学会的图的表示方法有这几种

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的点作为树根建树,依次将以起点从小到大排列的边插入树中

 

听说还有一种叫后向星,十字矩阵等等表示,暂时还没学到也没用到,如果以后用到再添加

抱歉!评论已关闭.