图论之图的存储邻接矩阵、邻接表和链式前向星

ゞ浴缸里的玫瑰 2023-02-15 10:25 153阅读 0赞

#### 一、图的存储方式 ####

目前常用的图的存储方式有两种，邻接矩阵和邻接表存储。  
边数M相对小（远远小于n\*（n-1））的图为**稀疏图**，反之为**稠密图**。稀疏图可用邻接表存储，稠密图可用邻接矩阵存储。邻接表可用数组或链表实现，邻接矩阵可用二维数组实现。

#### 二、邻接矩阵 ####

**1、邻接矩阵简介**

> 邻接矩阵很好理解，实质是用二维数组来存储一个图的各边的信息，例如用矩阵e\[ i \]\[ j \]来存储，其中下标i是指一条边的起点的编号，而下标j就是该边终点的编号，e\[ i \]\[ j \]的值存的是该边的权值。  
> 用邻接矩阵既可以存储无向图，也可以存储有向图。例如对于权值为x的ab边存无向图时，e\[ a \]\[ b \] = x; e\[ b \]\[ a \] = x; 。而存有向图时只需e\[ a \]\[ b \] = x;即可。

例如，将下方的有向图以邻接矩阵的方式存储  
![图的邻接矩阵存储][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]  
![邻接矩阵][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]  
顶点自身到自身的权值默认为0，若该边不存在，就存为无穷大。

**2、邻接矩阵存储的代码模板**

#include<iostream>
    
    using namespace std;
    const int N = 110,INF = 0x3f;	//N为最多顶点数，INF为无穷大
    
    int e[N][N],n,m;	//e是邻接矩阵，n是顶点数，m是边数
    
    int main()
    { 
    	int a,b,w;
    	cin >> n >> m;
    	for(int i = 0;i <= n;i++)	//矩阵初始化
    		for(int j = 0;j <= n;j++)
    			if(i == j)
    				e[i][j] = 0;	//自身存为0
    			else
    				e[i][j] = INf;	//其他边为无穷
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> w;
    		e[a][b] = w;		//加入边
    		//e[b][a] = w; //无向图的存储
    	}
    
    	return 0;
    }

--------------------

#### 三、邻接表 ####

**1、邻接表简介**  
稀疏图用邻接矩阵存储十分浪费空间，大部分数据全是没有意义的无穷大，所以在文章开始提到了：稀疏图我们用邻接表存储比较好

正经的邻接表（链表实现）：

![邻接表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 2]

不正经的邻接表（数组实现）：

> 我们用较为容易的数组来实现邻接表，先对1~m条边编号，然后用u，v，w三个一维数组存储边的信息，其中u\[ i \]，v\[ i \]，w\[ i \]分别表示第i条边的起点是u\[ i \]，终点是v\[ i \]，权值是w、\[ i \]。然后我们还需要数组来存储顶点和边的关系，我们用一个first\[ i \]来存储i顶点的第一条边的编号，next\[ i \]存储第i条边的下一条边的编号，最后一条边的下一条边存为-1 。

例如还是存储一图

![邻接表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 4]  
**2、邻接表存储的代码模板**

#include<iostream>
    #include<cstring>
    
    using namespace std;
    const int N = 110;
    int u[N],v[N],w[N],n,m;
    int first[N],next[N*N];
    
    int main()
    { 
    	cin >> n >> m;
    	memset(next,-1,sizeof next);		//将next数组初始化为-1
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> u[i] >> v[i] >> w[i];	//存储第i条边的信息
    		next[i] = first[u[i]];		//先将第i边的下一条边设为顶点u[i]的第一条边
    		first[u[i]] = i;		//然后将顶点u[i]的第一条边更新为i
    	}
    
    	return 0;
    }

**3、邻接表的遍历**  
邻接表的遍历不像邻接矩阵一样直接遍历矩阵即可，如图  
![邻接表的遍历][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 5]  
**邻接表遍历代码**

for(int i = 1;i <= n;i++)
    { 
    	int k = first[i];
    	while(k != -1)
    	{ 
    		cout << u[k] << " " << v[k] << " " << w[k] << endl;
    		k = next[k];
    	}
    }

--------------------

#### 四、链式前向星 ####

**1、链式前向星简介**  
链式前向星的思想其实还是邻接表，也就是对上面数组实现的邻接表的一个优化，在比赛中一般用链式前向星多一些，非常实用。

**2、代码模板**

#include<iostream>
    #include<cstring>
    
    using namespace std;
    const int N = 110;
    int e[N],ne[N],h[N],w[N],idx;	//若不存权值可省略w数组
    int n,m;
    
    void add(int a,int b,int w)	//加边模板
    { 
    	e[idx] = b;	//idx为边的编号，idx边的终点是e[idx]
    	w[idx] = w;	//idx边的权值是w[idx]
    	ne[idx] = h[a];	//idx边同起点的下一条边的编号是ne[idx]
    	h[a] = idx++;	//a顶点的第一条边的编号是h[a]
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);		//h要初始化为-1
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		add(a,b,c);
    	}
    
    	return 0;
    }

**3、链式前向星的遍历**

for(int i = 1;i <= n;i++)
    { 
    	for(int k = h[i];k > 0;k = ne[k])
    		cout << i << << e[k] << w[k];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605102415347.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200605102457404.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200605140708793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200605111714953.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200605111714932.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200605112627130.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70