前言
图是一种非线性的数据结构(数组、链表就是线性的数据结构)。而我们现在要学习一下这种不是线性的数据结构。
生活中有很多图的例子,比如说城市1和城市2之间有一条通路,城市2和城市3之间也有一条通路,城市1和城市3之间也有一条通路,如下图
所以如果我们想用计算机存储这种信息应该怎么做呢? 文邹邹的说:怎么把这种机外表示转化为机内表示?
图的邻接矩阵存储
如果我们现在有n个城市, 那么我们就建立一个n*n的矩阵
1 2 3 ... n
2
3
.
n ... n
下一步,我们把每个行当作是图中的某一个点, 例如第一行是C1 (C stands for city)。然后我们把每一列当作是与另一个点的关系。比如说 矩阵第一行第二列的值 表示C1和C2的关系。
在这里,我们用0,表示自己到自己的距离、用1表示两个点之间有路、用-1表示两个点没有路。
基于有上面的认知,我们看看下面的矩阵
0 1 1
1 0 0
1 0 0
我们可以知道第一个点到第二个点和第三个点之间是有路的,而第二个点和第三个点之间没有路
所以到现在,我们用这种办法来存储图的信息,而这种办法就叫做图的邻接矩阵表示法
图的遍历
遍历的意思就是挨个访问数据内的每个数据单元,在这里我们要掌握一种用代码来访问图的每个节点的方法,今天用的是深度优先搜索算法。
就是说,我们先基于某个点开始(从矩阵的某一行开始),按照一定的顺序(矩阵的从左到右),判断两点之间(第i行第j列)是否通路?如果有通路,我们就进入这个被连接的点,基于这个点,再进行操作(递归地)。
不懂没关系,通过代码执行过程来理解这个事情
void dfs(int cur) // 参数的意思就是进入这个点
{
printf("访问了第%d个点\n", cur); // 图像上表示出来
// 标记这个点已经访问过了
book[cur] = 1;
// 访问的点的总数增加1
sum++;
// 如果到现在访问完了所有点的话,就返回吧
if (sum == 5) return;
// 所谓从左到右的顺序
for (int i = 1; i < 5; ++i)
{
// 如果有路可走,并且没有走过这个点
if (ar[cur][i] == 1 && book[i] == 0)
{
dfs(i); // 基于新的点,递归的访问这个点
}
}
return; // 递归最顶层的返回
}
如果你认真的阅读了前面的内容,那你到现在的话应该就懂了。如果你还没懂,建议你手抄一下这份代码。
关于本章知识的一个Ncurses小程序
如果你学过Ncurses,或者认真读我的其他文章,那接下来的内容,你应该能自行理解。
操作的矩阵
int ar[][5] = {
{ 0, 1, 1, -1, 1 },
{ 1, 0, -1, 1, -1 },
{ 1, -1, 0, -1, 1 },
{ -1, 1, -1, 0, -1 },
{ 1, -1, 1, -1, 0 }
};
显然是一个5*5的矩阵
效果
代码
|
|
总结
还是很简单的