1. 邻接矩阵：图在计算机中的“身份证”

如果你刚开始学数据结构，一听到“图”这个字，脑子里可能立刻浮现出各种曲线图、柱状图。但在计算机的世界里，图（Graph） 是一种完全不同的东西。你可以把它想象成一张巨大的关系网，比如微信好友关系、城市之间的航线、网页之间的超链接。这张网由两种基本元素构成：顶点（Vertex） 和 边（Edge）。顶点就是网络中的一个个点，比如一个个用户、一座座城市；边就是连接这些点的线，代表了它们之间的关系。

那么问题来了，我们怎么把这张抽象的关系网，塞进计算机冰冷的内存里呢？这就好比你要给一个复杂的人际关系网络办一张“身份证”，让计算机能识别、能查询、能计算。最直接、最经典的方法之一，就是使用 邻接矩阵（Adjacency Matrix）。

邻接矩阵本质上就是一个二维数组，一个方阵。假设我们的图有 n 个顶点，我们就创建一个 n x n 的矩阵。这个矩阵的行和列都代表顶点。如果顶点 i 和顶点 j 之间有一条边相连，我们就在矩阵的第 i 行第 j 列（以及对称的第 j 行第 i 列，因为是无向图）标记为 1；如果没有边，就标记为 0。看，是不是像极了给每个顶点对的关系打上“是”或“否”的标签？

我举个最简单的例子。有四个小伙伴：A, B, C, D。A和B是朋友，A和C也是朋友，其他人都互不认识。用邻接矩阵来表示就是下面这样：

   A  B  C  D
A  0  1  1  0
B  1  0  0  0
C  1  0  0  0
D  0  0  0  0

矩阵里 A行B列 和 B行A列 都是1，表示A和B相连。A行C列 和 C行A列 也是1。D比较孤单，和其他人都没有连接，所以D行D列都是0（注意，我们这里默认顶点到自身的边不算，所以对角线都是0）。

这种存储方式有什么好处呢？查询速度极快。你想知道顶点A和顶点D是不是朋友？直接去矩阵里看 [A][D] 这个位置的值就行，时间复杂度是 O(1)。对于需要频繁判断两点间关系的场景，比如社交网络里的“是否为好友”，这非常高效。而且，矩阵的结构非常直观，打印出来一目了然，就像题目要求输出的一样，非常适合教学和调试。

当然，它也有明显的缺点，就是 空间浪费。尤其是当图的边很少（我们称之为“稀疏图”）的时候，比如有10000个顶点，但只有20000条边，这个10000x10000的矩阵里绝大部分都是0，非常占内存。这时候，邻接表会是更好的选择。但对于我们理解图的基础操作，尤其是连通分量计算，从邻接矩阵入手，能把原理看得清清楚楚。

2. 连通分量：图中的“朋友圈”与“孤岛”

理解了图怎么存，我们来看看一个图论中超级重要的概念：连通分量（Connected Component）。这个名字听起来有点学术，但其实它的生活化比喻非常贴切——朋友圈，或者叫 孤岛。

想象一下，你加入了一个全新的社交App，里面有成千上万的用户。有些用户之间互相是好友，通过好友关系可以间接认识很多人，这群人形成了一个紧密联系的大圈子，这就是一个“连通分量”。而另一些用户，他们可能刚注册，还没加任何人，或者只和极少数人形成了一个小团体，和外面的大圈子没有任何联系。那么，这个小团体就是另一个独立的“连通分量”。整个社交网络，就是由若干个互不连通的“朋友圈”或“孤岛”组成的。

用严谨的话说：在一个无向图中，如果从顶点A出发，沿着边可以走到顶点B，那么A和B就是连通的。一个连通分量，就是图中一个极大的连通子图。所谓“极大”，意思是你再往这个子图里添加任何一个其他顶点，它都会变得不连通。计算一个图有多少个连通分量，就是在数这个图里面有多少个互相独立的“圈子”或“岛屿”。

这个计算在实际中有什么用呢？用处太大了。比如在网络诊断中，你可以把路由器、交换机看作顶点，网线看作边。计算连通分量可以帮你快速发现网络中是否有设备脱机，形成了孤岛。在社交网络分析中，连通分量的数量和大小是衡量社区结构的关键指标。在图像处理里，一张二值化图片（比如黑白扫描件）可以看作一个图，每个像素点是一个顶点，相邻的黑色像素点之间有边，那么每一个连通分量可能就对应着一个独立的字符或图形，这常用于OCR（光学字符识别）中的字符分割。

回到我们开头提到的OJ题目，它的核心目标就是：给你一个无向图的顶点和边信息，请你先构建它的邻接矩阵“身份证”，然后通过这个矩阵，算出这个图到底由几个互不连通的“朋友圈”组成，并输出个数。这就像给你一份人际关系名单，让你统计出这里面存在多少个彼此独立的小团体。

3. 深度优先搜索（DFS）：探索“朋友圈”的万能钥匙

现在我们知道目标了：找出所有的“朋友圈”。那怎么找呢？难道要人工去一个个看吗？当然不是，我们要派一个不知疲倦的“探险家”去自动探索。这个探险家最常用的工具之一，就是 深度优先搜索，也就是DFS（Depth-First Search）。

DFS的策略，可以用一句老话概括：一条道走到黑，撞了南墙再回头。它的探索方式非常像我们走迷宫：从起点开始，随便选一条路往前走，走到头（没路可走）之后，就退回上一个岔路口，换一条没走过的路继续走，直到探索完所有地方。

把它映射到图的世界里，DFS从一个顶点出发，首先标记这个顶点为“已访问”。然后，它去查看这个顶点的所有邻居（在邻接矩阵里，就是遍历这一行所有为1的列），如果发现某个邻居还没被访问过，它就立刻“深入”到这个邻居顶点，并以这个邻居为新的起点，重复上述过程。这个过程会一直递归下去，直到某个顶点的所有邻居都被访问过了，就回溯到上一个顶点，看看还有没有其他未访问的邻居。

这么说可能还有点抽象，我结合邻接矩阵和代码给你拆解一下。我们用一个布尔数组 visited（或者像参考代码里叫 flag）来记录每个顶点是否被访问过，初始都是 false。

假设我们从顶点 i 开始一次DFS：

1. 首先，把 visited[i] 设为 true，表示“我来过这里了”。
2. 然后，我们需要找出 i 的所有邻居。怎么找？在邻接矩阵 matrix 中，扫描第 i 行。如果 matrix[i][j] == 1，那就说明顶点 j 是 i 的邻居。
3. 对于每一个邻居 j，我们检查 visited[j] 是否为 false。如果是，说明这个邻居还没被探索过，那么我们就立刻 递归地 对 j 调用DFS函数。
4. 这个递归调用会一路深入下去，直到某个顶点所有邻居都被访问，递归开始逐层返回，最终回到顶点 i。
5. 当对 i 的DFS调用结束时，所有从 i 出发能走到的顶点，就都被标记为“已访问”了。而这整个被访问到的顶点集合，就构成了一个连通分量！

这里的关键逻辑在于递归。递归让DFS的代码变得异常简洁。就像参考代码里的 dfs 函数，短短几行，却蕴含着强大的探索能力：

void dfs(int i) {
    flag[i] = 1; // 标记当前顶点已访问
    for(int j=0; j<n; j++) // 遍历所有顶点，寻找邻居
        if (juzhen[i][j] && !flag[j]) { // 如果是邻居且未访问
            dfs(j); // 递归深入！
        }
}

你看，它把自己调用自己，就能完成对整个连通区域的“地毯式”搜索。这种“递归深入”的思想，是掌握DFS的核心。

4. 算法实战：一步步拆解连通分量计算

理论说得再多，不如动手过一遍。我们就把参考代码里的算法逻辑，掰开揉碎了，结合一个具体例子走一遍。这样你就能彻底明白，从输入到输出，计算机到底干了啥。

我们拿样例中的第一组数据来演示：

4 A B C D // 4个顶点：A(0), B(1), C(2), D(3)
2         // 2条边
A B       // 边1：连接 A(0) 和 B(1)
A C       // 边2：连接 A(0) 和 C(2)

第一步：初始化与建图 程序首先读取顶点数 n=4 和顶点信息，把它们存到数组 dian 里，并建立一个 4x4 的邻接矩阵 juzhen，所有元素初始化为0。同时，准备一个访问标记数组 flag，全部置为0（未访问）。

接着读取边数 k=2，然后读入每条边。读入 A B 时，通过一个查找函数 xun（其实就是遍历 dian 数组）找到 A 的下标是0，B 的下标是1。然后在矩阵的 [0][1] 和 [1][0] 位置都置为1（因为是无向图）。同理，处理边 A C，在 [0][2] 和 [2][0] 位置置为1。建好的矩阵如下：

A B C D
0 1 1 0  // A行
1 0 0 0  // B行
1 0 0 0  // C行
0 0 0 0  // D行

这个矩阵就是我们图的“身份证”。

第二步：核心计算连通分量个数 现在矩阵有了，flag 数组也全是0。我们开始计算连通分量个数 cc，初始为0。

for(i=0; i<n; i++) {
    if (!flag[i]) { // 发现一个未被访问的顶点！
        flag[i] = 1;
        cc++; // 连通分量数量+1
        dfs(i); // 启动DFS，标记整个“朋友圈”
    }
}

这个循环是算法的灵魂。它按顺序遍历所有顶点（0到3，即A到D）：

1. i=0 (顶点A)：检查 flag[0] 是0（未访问）。好，我们发现了一个新的、未被探索的区域！这很可能是一个新“朋友圈”的起点。于是，cc 加1，变成1。然后调用 dfs(0)。
2. dfs(0) 的执行过程：
   • 标记 flag[0]=1。
   • 遍历 j=0 到 3，寻找顶点0（A）的邻居。
   • j=1：juzhen[0][1]==1 且 flag[1]==0，条件成立，递归调用 dfs(1)。
     • dfs(1)：标记 flag[1]=1。寻找顶点1（B）的邻居。发现 juzhen[1][0]==1 但 flag[0]==1（已访问），跳过。没有其他邻居了，dfs(1) 结束返回。
   • j=2：juzhen[0][2]==1 且 flag[2]==0，条件成立，递归调用 dfs(2)。
     • dfs(2)：标记 flag[2]=1。寻找顶点2（C）的邻居。发现 juzhen[2][0]==1 但 flag[0]==1，跳过。没有其他邻居，dfs(2) 结束返回。
   • j=3：juzhen[0][3]==0，跳过。
   • dfs(0) 结束。 经过这次DFS，顶点A、B、C的 flag 都被标记为1了。这意味着我们探索完了包含A的第一个“朋友圈”。
3. 循环继续，i=1 (顶点B)：检查 flag[1]，发现已经是1了，跳过。
4. i=2 (顶点C)：flag[2] 也是1，跳过。
5. i=3 (顶点D)：检查 flag[3]，发现是0！这说明D不在刚才那个“朋友圈”里，它是一个新的孤岛。于是，cc 加1，变成2。调用 dfs(3)。
   • dfs(3)：标记 flag[3]=1。寻找顶点D的邻居。遍历发现 juzhen[3][0]到[3][2]都是0，没有邻居。dfs(3) 结束。 这样，第二个“朋友圈”（其实只有D自己）也被标记了。

循环结束，我们得到 cc = 2。算法完美地识别出图中有两个连通分量：{A, B, C} 和 {D}。

第三步：输出结果 最后，按照题目要求，先输出顶点信息，再输出邻接矩阵，最后输出连通分量个数 cc。每组数据后用空行分隔。

走完这个过程，你应该能清晰地感受到，cc 增加的时机，正是我们发现一个全新的、未被任何已探索区域触及的顶点的时候。每一次 cc++，都代表我们发现了一个新的“孤岛”或“朋友圈”。而DFS，就是那个帮我们摸清一个“朋友圈”到底有多大的探险家。

5. 从理解到优化：邻接矩阵DFS的细节与思考

虽然上面的代码已经能AC题目，但作为学习者，我们不能止步于此。里面有几个细节和潜在的优化点，值得深入琢磨。把这些搞懂了，你才算真正吃透了这个算法。

第一个细节：visited 标记的时机。 仔细看参考代码，在主循环里，它先 flag[i]=1 和 cc++，然后再调用 dfs(i)。而在 dfs 函数内部，第一句又是 flag[i]=1。对于起点 i 来说，这不是重复标记了吗？确实，对于起点，flag[i] 被设置了两次。但这并不影响结果的正确性，因为它的状态已经是“已访问”了。更常见的写法是，在主循环里只做判断和计数，把标记工作完全交给 dfs 函数，这样逻辑更清晰：

for(i=0; i<n; i++) {
    if (!flag[i]) {
        cc++;
        dfs(i); // 在dfs内部标记起点
    }
}
void dfs(int i) {
    if (flag[i]) return; // 甚至可以加一个递归终止条件，虽然这里不需要
    flag[i] = 1;
    for(int j=0; j<n; j++)
        if (juzhen[i][j] && !flag[j])
            dfs(j);
}

两种写法都可以，但后一种避免了重复操作，是更标准的DFS模板。

第二个关键点：递归深度与栈溢出。 DFS是递归实现的，递归就要用到系统的调用栈。如果图非常大，并且非常“深”（比如是一条长长的链），那么递归的层数可能会非常深，有可能导致栈溢出错误。这是DFS使用邻接矩阵时的一个潜在风险。在实际工程中，对于顶点数成千上万的图，有时会采用迭代式的深度优先搜索（使用显式的栈数据结构）或者广度优先搜索（BFS）来避免这个问题。不过对于OJ题目和一般教学场景，顶点数较少，递归实现是最简洁明了的。

第三个优化方向：邻居查找的效率。 这是我们这个实现可以明显优化的地方。注意看 dfs 函数中的循环：for(int j=0; j<n; j++)。它在遍历图中的 所有顶点，然后通过 if (juzhen[i][j] ...) 来判断是不是邻居。这意味着，即使顶点 i 只有一个邻居，它也要完整地扫描一行 n 个元素。在图论中，我们称这种操作为 O(n) 的邻居查找。 对于一个稀疏图（边数远小于 n^2），这种遍历方式做了大量无用功。这就是为什么对于稀疏图，邻接表（Adjacency List） 是更优的存储方式。邻接表为每个顶点维护一个链表，链表中只存储它的邻居顶点。这样在DFS时，找邻居就直接遍历这个短链表，效率高得多。当然，邻接矩阵在查找任意两点间是否有边时是O(1)，这是它的优势。存储结构和算法选择，永远是在做权衡。

关于连通分量本身，我们计算的是数量。但有时候问题会要求输出每个连通分量具体包含哪些顶点。这也很容易修改，只需要在DFS过程中，将访问到的顶点加入一个临时列表（或直接打印），每次主循环开始一次新的DFS前，清空并开始记录一个新的列表即可。这让你不仅能数出有几个“朋友圈”，还能把每个“朋友圈”的成员名单都列出来。

最后，一定要自己动手敲一遍代码。你可以先完全按照参考代码敲，跑通样例。然后，尝试我的优化建议，改成更标准的DFS标记方式。再进一步，挑战自己，用邻接表的数据结构重新实现一遍这个程序。这个过程里你会遇到各种小问题，比如邻接表怎么构建、DFS的参数如何调整，解决这些问题带来的理解深度，是光看文章无法比拟的。

图算法的学习，就像探索一个未知的迷宫。邻接矩阵是你的地图，DFS是你的探索方法，而连通分量则是你探索完成后绘制的区域报告。掌握了这个基础组合，你就拿到了打开图论世界大门的第一把钥匙。后面无论是学习最短路径的Dijkstra算法，还是最小生成树的Kruskal算法，都会发现它们都建立在这种“存储”与“遍历”的核心思想之上。多练，多思考，把这张“图”真正装进脑子里。