前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

基于图的基础概念，要在计算机中存储一个图，需要保存这个图的点集和边集。

保存所有节点的信息是容易的，节点总是有编号或者可编号的，因此可以考虑使用链表或者线性表来存储和快速检索节点信息。
大多数情况下对图不涉及频繁的增删节点，而是频繁的检索各个节点的信息，所以还是推荐使用数组来存储接地那信息。

相较于节点，保存边集总不是那么容易，一方面边不能脱离节点单独存储，一条边连接两个节点，是两个节点间的一个关系；另一方面，边集的规模比较大，在没有重边的情况下，完全无向图边的数量为 C n 2 = n ( n + 1 ) 2 C^2_n=\frac{n(n+1)}{2} Cn2​=2n(n+1)​条边，这个规模是 n 2 n^2 n2级别，如果选择了不恰当的存储结构，冗余的空间将会是巨大的浪费。

那么这一节，我们将介绍两种存储图的方法：邻接矩阵和邻接表

邻接矩阵

邻接矩阵是使用一个 n ∗ n n*n n∗n的矩阵 A = ( a i j ) A=(a_{ij}) A=(aij​)来表示一张图。用矩阵中的每一个元素就表示了一对点之间的边信息。

无权图的邻接矩阵

对于无权图，邻接矩阵有：

• a i j = 0 a_{ij}=0 aij​=0，节点i和节点j之间不存在边
• a i j = 1 a_{ij}=1 aij​=1，节点i和节点j之间有一条边由i指向j

对于下面的有向图：

其邻接矩阵为：

从该图中我们可以看到，由于不存在指向自己的边，所以矩阵的主对角元素都是0

对于如下无向图：

其邻接矩阵为：

可以发现，对于无向图，邻接矩阵总是对称的。如果节点i和节点j之间存在无向边，则 a i j = a j i = 1 a_{ij}=a_{ji}=1 aij​=aji​=1。这个也给了我们一个启示，即无向边可以看作两条方向相反的两条有向边。

代码实现

在程序中，完全可以使用二维数组来模拟矩阵，我们用矩阵a[i][j]来表示 a i j a_{ij} aij​。

例如，统计一张图每个结点的入度和出度：

输入格式：首行为两个整数n,m表示图中点的数量和边的数量，接下来m行，每行两个整数i和j，代表一条有向边从i指向j

输出格式：输出包含2*n行，前n行为该图的邻接矩阵，后n行每行三个整数k,a,b，k表示结点编号，a为该节点入读，b为出度

#include<stdio.h>
int a[100][100];
int main(){ 
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 0,x,y;i < m;i++){ 
		scanf("%d%d",&x,&y);
		a[x][y] = 1;
	}
	for(int i = 1;i <= n;i++){ 
		for(int j = 1;j <= n;j++){ 
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	for(int i = 1,rd,cd;i <= n;i++){ 
		rd = 0;
		for(int j = 1;j <= n;j++){ 
			rd += a[i][j];
		}
		cd = 0;
		for(int j = 1;j <= n;j++){ 
			cd += a[j][i];
		}
		printf("%d %d %d\n",i,rd,cd);
	}
}	

运行结果如下：

有权图的邻接矩阵

对于有权图来说，仅仅记录两个结点之间是否存在边已经不足以记录足够的信息了，还需要记录这些边的权重。于是不妨规定：

• a i j = ∞ a_{ij}=\infty aij​=∞，节点i和节点j之间没有边
• a i i = 0 a_{ii}=0 aii​=0
• a i j = v a l a_{ij}=val aij​=val，节点i和节点j之间存在边，权重为val

例如对下面的权图：

其邻接矩阵为：

对于无穷大的设置，一般来说，可以取int的上限，起到标记的作用。其本质是取一个边权值无法达到的一个值，通常取一个大值，这样便于后续有关图算法的设计。

代码实现

例如，统计一张有向有权图每个结点的出度边权和：

输入格式：首行为两个整数n,m表示图中点的数量和边的数量，接下来m行，每行两个整数i,j和v，代表一条有向边从i指向j，权值为v

输出格式：输出包含2*n行，前n行为该图的邻接矩阵，后n行每行三个整数k,a，k表示结点编号，a为出度边权和

#include<stdio.h>
int a[100][100];
const int inf = 1 << 30;
int main(){ 
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){ 
		for(int j = 0;j <= n;j++){ 
			a[i][j] = i == j ? 0 : inf;
		}
	}
	for(int i = 0,x,y,v;i < m;i++){ 
		scanf("%d%d%d",&x,&y,&v);
		a[x][y] = v;
	}
	for(int i = 1;i <= n;i++){ 
		for(int j = 1;j <= n;j++){ 
			if(a[i][j] == inf){ 
				printf("inf ");
			}else{ 
				printf("%-4d",a[i][j]);				
			}
		}
		printf("\n");
	}
	for(int i = 1,cd;i <= n;i++){ 
		cd = 0;
		for(int j = 1;j <= n;j++){ 
			cd += a[i][j] == inf ? 0 : a[i][j];
		}
		printf("%d %d\n",i,cd);
	}
}	

邻接表

不难发现使用邻接矩阵存储图结构由于需要表示每一个可能存在的边，需要开 n 2 n^2 n2个空间。当图中点较多且较为稀疏时，这样的存储方式将会是极大地浪费。

此时可以使用邻接表来存储图结构

邻接表的思想简单来说就是为每一个节点提供一个长度可变的线性结构，每添加一个新边，就放置在线性表后面。而这个长度可变的线性结构通常使用链表来实现。

它的邻接矩阵为：

其实对比观察不难发现，邻接表就是将邻接矩阵每一行中的“1”用链表串联起来且不分顺序。

代码实现

首先，使用邻接表存储边信息，其结构为链表，所以每个链节点除了要存储指向节点的之外至少需要有next指针。为什么是至少呢？因为一条边可能还有边权等等其他字段。所以至少是指向节点和next指针，最后一个结点指向NULL

typedef struct _Edge{ 
	int vertex;
	struct _Edge * next;
}Edge;

为了存储邻接表，还需要一个链首数组存放每个节点邻接链表的链首。

Edge * head[N];

则初始化图的时候需要给head数组置空：

void init(int n){ 
	for(int i = 1;i <= n;i++){ 
		head[i] = NULL;
	}
}

当追加一条边时，在起点的边链表中插入一个节点。

void link(int x,int y){ 
	Edge * edge = (Edge*)malloc(sizeof(Edge));
	edge->vertex = y;
	edge->next = head[x];
	head[x] = edge;
}

当需要遍历一个结点的以其为起点的边时，使用指针进行迭代：

void getEdges(int k){ 
	for(Edge* edge = head[k];edge != NULL;edge = edge->next){ 
		printf("%d ",edge->vertex);
	}
}
//node != NULL 可简写为node

示例：

输入格式：第一行为两个整数n,m代表结点个数和边的数量，接下来m行，每行两个整数，表示边的起点和终点。
输出格式：该图的邻接矩阵

#include<stdio.h>
#include<malloc.h>
const int N = 1000;
typedef struct _Edge{ 
	int vertex;
	struct _Edge * next;
}Edge;
Edge * head[N];
int matrix[N][N];

void link(int x,int y){ 
	Edge * edge = (Edge*)malloc(sizeof(Edge));
	edge->vertex = y;
	edge->next = head[x];
	head[x] = edge;
}

int main(){ 
	int n,m;
	scanf("%d%d",&n,&m);
	//初始化邻接表 
	for(int i = 1;i <= n;i++){ 
		head[i] = NULL;
	}
	//读入边 
	for(int i = 0,x,y;i < m;i++){ 
		scanf("%d%d",&x,&y);
		link(x,y);
	} 
	//构建邻接矩阵 
	for(int i = 1;i <= n;i++){ 
		for(Edge * edge = head[i];edge;edge = edge->next){ 
			matrix[i][edge->vertex] = 1;
		}
	}
	//打印邻接矩阵 
	for(int i = 1;i <= n;i++){ 
		for(int j = 1;j <= n;j++){ 
			printf("%-2d",matrix[i][j]);
		}
		printf("\n"); 
	}
}

当图无向时，可以将一条无向边转化为两条方向相反的有向边进行存储。

...
scanf("%d%d",&x,&y);
link(x,y);
link(y,x);
...

当边具有边权等其他字段时，需要在边结构体中加入对应字段定义，并在创建边的时候将这些属性赋予边。

void link(int x,int y,int len...){ 
	Edge * edge = (Edge*)malloc(sizeof(Edge));
	edge->vertex = y;
	edge->len = len;
	...
	edge->next = head[x];
	head[x] = edge;
}

数组模拟邻接表

邻接表很好，但有时候他也会戳到我们的软肋——动态内存管理

每一个存储的边都是块动态内存，当图不再使用的时候能想起来释放他们总是一件难事。除此之外，当需要频繁的创建新图时，不断地申请和释放也会占据不少的时间。

那么有没有静态内存的替代方案呢？答案是肯定的，可以使用数组来模拟链表。

其实说来，就是预先开辟足够大小的数组模拟边结点将会申请到的内存，并定义一个指针指向当前可以用的位置。那么边结点中的next指针含义也变成了下一个边结点在数组中的下标

typedef struct _Edge{ 
	int vertex;
	int next;
}Edge;

Edge edges[M];
int pointer = 0;

为了表示链表中的最后一个元素，我们规定边结点下标从1开始计数，这样最后一个元素的next值可以指向0表示结束。

与邻接表类似，仍需要一个head数组记录所有结点边链表的链首，只不过这回他不用是指向该节点的指针，而是它在数组中的下标。

int head[N];

同理，我们需要在初始化时将所有结点边链表置空，前面约定0表示结束，所以在这里就是head数组置零，计数指针置零

void init(int n){ 
	for(int i = 1;i <= n;i++){ 
		head[i] = 0;
	}
	pointer = 0;
}

当添加一个元素时，直接将指针后移一个指向新边结点。新节点的插入和链表插入操作类似，方便的是，给结构体赋值可以使用大括号式：

void link(int x,int y){ 
	nodes[++pointer] = { y,head[x]};
	head[x] = pointer;
}

遍历时，同样采用迭代的方式：

void getEdge(int k){ 
	for(int i = head[k];i;i = edges[i].next){ 
	....
	}
}

用这种形式，再来实现一下上面的示例：

#include<stdio.h>
const int N = 1000;
const int M = 10000;
typedef struct _Edge{ 
	int vertex;
	int next;
}Edge;
Edge edges[M];
int head[N];
int pointer;
int matrix[N][N];

void link(int x,int y){ 
	edges[++pointer] = { y,head[x]};
	head[x] = pointer;
}

int main(){ 
	int n,m;
	scanf("%d%d",&n,&m);
	//初始化邻接表 
	for(int i = 1;i <= n;i++){ 
		head[i] = 0;
	}
	//读入边 
	for(int i = 0,x,y;i < m;i++){ 
		scanf("%d%d",&x,&y);
		link(x,y);
	} 
	//构建邻接矩阵 
	for(int i = 1;i <= n;i++){ 
		for(int j = head[i];j;j = edges[j].next){ 
			matrix[i][edges[j].vertex] = 1;
		}
	}
	//打印邻接矩阵 
	for(int i = 1;i <= n;i++){ 
		for(int j = 1;j <= n;j++){ 
			printf("%-2d",matrix[i][j]);
		}
		printf("\n"); 
	}
}

往期博客

• 【数据结构基础】数据结构基础概念
• 【数据结构基础】线性数据结构——线性表概念 及 数组的封装
• 【数据结构基础】线性数据结构——三种链表的总结及封装
• 【数据结构基础】线性数据结构——栈和队列的总结及封装(C和java)
• 【算法与数据结构基础】模式匹配问题与KMP算法
• 【数据结构与算法基础】二叉树与其遍历序列的互化 附代码实现（C和java）
• 【数据结构与算法拓展】 单调队列原理及代码实现

参考资料：

• 《数据结构》（刘大有，杨博等编著）
• 《算法导论》（托马斯·科尔曼等编著）
• 《图解数据结构——使用Java》（胡昭民著）
• OI WiKi