首页 > 代码库 > 最短路径算法之五——邻接表

最短路径算法之五——邻接表

2024-07-13 15:09:10   222人阅读

邻接表

　　邻接矩阵来存储图的信息相对于非完全图，会浪费大量的空间，同时在求最短路径的时候也会有多余的计算浪费时间。

　　使用邻接表可以节约这些浪费的时间。

　　这里介绍的是用数组模拟的邻接表：

　　定义begin[MAXN],end[MAXN],dis[MAXN],first[MAXN],next[MAXN]五个数组。

　　例子描述如下：

　　　　4 5

　　　　1 4 9

　　　　4 3 8

　　　　1 2 5

　　　　2 4 6

　　　　1 3 7

Step1：

 

1

2

3

4

5

begin

 

 

 

 

 

end

 

 

 

 

 

dis

 

 

 

 

 

first

-1

-1

-1

-1

-1

next

 

 

 

 

 

Step2：

 

1

2

3

4

5

begin

1

 

 

 

 

end

4

 

 

 

 

dis

9

 

 

 

 

first

1

-1

-1

-1

-1

next

-1

 

 

 

 

Step3：

 

1

2

3

4

5

begin

1

4

 

 

 

end

4

3

 

 

 

dis

9

8

 

 

 

first

1

-1

-1

2

-1

next

-1

-1

 

 

 

Step4：

 

1

2

3

4

5

begin

1

4

1

 

 

end

4

3

2

 

 

dis

9

8

5

 

 

first

3

-1

-1

2

-1

next

-1

-1

1

 

 

Step5：

 

1

2

3

4

5

begin

1

4

1

2

 

end

4

3

2

4

 

dis

9

8

5

6

 

first

3

4

-1

2

-1

next

-1

-1

1

-1

 

Step6：

 

1

2

3

4

5

begin

1

4

1

2

1

end

4

3

2

4

3

dis

9

8

5

6

7

first

5

4

-1

2

-1

next

-1

-1

1

-1

3

创建邻接表：

 1 nt n,m,i; 2 int begin[6],end[6],dis[6]; 3 int first[6],next[6]; 4 scanf("%d %d",&n,&m); 5 //初始化first数组 6 for(i=1;i<=n;i++) 7     first[i]=-1; 8 for(i=1;i<=m;i++) 9 {10     scanf("%d %d %d",&begin[i],&end[i],&dis[i]);11     next[i]=first[begin[i]];12     first[begin[i]]=i;13 }

遍历1号顶点所有边：

 

1 k=first[1];2 while(k!=-1)3 {4     printf("%d %d %d\n",begin[k],end[k],dis[k]);5     k=next[k];6 }

 

 

 


联系
我们