图-算法题

求无向图中连通分量个数

已知无向图G由顶点集 V 和边集E 组成，|V|>0。设图 G采用邻接矩阵存储，类型定义如下:

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

Info

连通分量是图中一个极大连通子图。在每个连通分量内，任意两个顶点都是可达的，但不同连通分量中的顶点之间不可达。 请设计算法，计算无向图 G的连通分量的个数。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

方法一： 使用深度优先搜索 (DFS) 来遍历图，标记已经访问的顶点。每次从未访问的顶点开始进行 DFS，即可找到一个连通分量。统计这种 DFS 开始的次数，即为连通分量的个数。

实现步骤：

1. 初始化：
2. 创建一个 visited 数组，标记每个顶点是否已被访问。
3. 初始化连通分量计数器 count 为 0。
4. 遍历所有顶点：
5. 对每个未访问的顶点，执行 DFS，标记所有可达的顶点，并将 count 增加 1。
6. 每次执行 DFS 发现一个新的连通分量。
7. 输出：count 即为图的连通分量个数。

代码实现：

#include <iostream>
#include <vector>

using namespace std;

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

// 深度优先搜索（DFS）函数
void DFS(MGraph &G, vector<bool> &visited, int v) {
    visited[v] = true; // 标记顶点 v 为已访问
    // 遍历顶点 v 的所有邻接顶点
    for (int i = 0; i < G.numVertices; ++i) {
        if (G.edges[v][i] == 1 && !visited[i]) { // 如果存在边且未访问
            DFS(G, visited, i); // 递归调用 DFS
        }
    }
}

// 计算图的连通分量个数
int countConnectedComponents(MGraph &G) {
    vector<bool> visited(G.numVertices, false); // 初始化访问标记数组
    int count = 0; // 连通分量计数器

    // 遍历所有顶点
    for (int i = 0; i < G.numVertices; ++i) {
        if (!visited[i]) { // 如果顶点 i 未被访问
            DFS(G, visited, i); // 从顶点 i 开始 DFS
            count++; // 每次 DFS 完成，增加连通分量计数器
        }
    }

    return count; // 返回连通分量个数
}

// 测试主函数
int main() {
    MGraph G;
    // 初始化图 G 的相关属性，例如 numVertices、edges 等
    // ...

    int connectedComponents = countConnectedComponents(G);
    cout << "连通分量的个数为: " << connectedComponents << endl;

    return 0;
}

Info

时间复杂度：

无论是\(bfs\)实现还是\(dfs\)实现，遍历顶点 \(v\) 并从 \(v\) 开始泛洪。考虑图所有顶点构成 完全图  (任意两个顶点间都有边连接)，那么对第一个顶点 \(v\) 执行搜索后，每个顶点都会询问所有他的 \(|V| - 1\) 个邻接顶点是否已被访问。最坏和平均时间复杂度为\(O(|V|^2)\)。

空间复杂度：

• visited 数组的空间复杂度为 O(V)。
• 递归调用栈的空间复杂度最坏情况下也为 O(V)（对于深度优先搜索的递归深度）

因此空间复杂度为 O(V)。

方法二：使用并查集，如果该无向图是用邻接矩阵存储，遍历它的上三角区域，如果G.edges[i][j]!=0,并且i,j的祖先结点不同，也就是说二者不在一个集合，那么就将这两个点加入并查集集合中，遍历结束后，再遍历一下父节点数组查看值为\(-1\)的元素个数，这就是集合的个数，也就是连通分量的个数；

代码实现：

#define MAXV 100  // 顶点数目的最大值

typedef struct {
    int numVertices;       // 图中实际的顶点数
    int numEdges;          // 图中实际的边数
    char vertexList[MAXV]; // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

int s[MAXV];  // 集合元素数组，用于双亲表示法的数据结构

// 初始化并查集
void Initial(int Size) {
    for(int i = 0; i < Size; ++i) {
        s[i] = -1;  // -1 表示每个元素都为根节点
    }
}

// 查操作，找 x 所属集合（返回 x 所属树的根节点）
int Find(int x) {
    while(s[x] >= 0) {  // 只要数组中该元素值 >= 0，说明还未找到其所属集合根节点，继续循环寻找
        x = s[x];  // 更新 x 为其父节点的下标
    }
    return x;  // 返回根节点的下标
}

// 将 v->u 这条边加入并查集
void join(int u, int v) {
    u = Find(u);  // 查找顶点 u 的根节点
    v = Find(v);  // 查找顶点 v 的根节点
    if(u == v) return;  // 如果二者本来就属于同一个集合，则直接返回
    s[v] = u;  // 将顶点 v 的根节点设置为 u，合并两个集合
}

// 计算图的连通分量的个数
int countComponents(MGraph G) {
    Initial(G.numVertices);  // 初始化并查集

    // 遍历邻接矩阵的上三角区域
    for(int i = 0; i < G.numVertices; ++i) {
        for(int j = i + 1; j < G.numVertices; ++j) {
            if(G.edges[i][j] != 0) {  // 如果 i 和 j 之间有边
                if(Find(i) != Find(j))  join(i, j);  // 如果二者不在同一个集合中，将 j 并入 i 所在的集合
            }
        }
    }

    // 计算集合的个数
    int count = 0;
    for(int i = 0; i < G.numVertices; ++i) {
        if(s[i] == -1) {  // 如果在父节点数组中值为 -1，说明它是某个集合的根节点
            count++;
        }
    }
    return count;  // 返回连通分量的个数
}

---

求无向图中无环连通分量个数

已知无向图G由顶点集 V 和边集E 组成，|V|>0。设图 G采用邻接矩阵存储，类型定义如下:

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

Info

连通分量是图中一个极大连通子图。在每个连通分量内，任意两个顶点都是可达的，但不同连通分量中的顶点之间不可达。 请设计算法，计算无向图 G的无环连通分量的个数。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

解题思路：

• DFS遍历图：利用DFS遍历图中的每个连通分量。
• 判断无环性：对于每个连通分量，通过计算其边数和顶点数来判断是否是无环图。对于无环连通分量，其满足 边数 = 顶点数 - 1 的特性。
• 记录结果：每找到一个无环连通分量，则计数加一。

#include <iostream>
#include <vector>

using namespace std;

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

// 深度优先搜索，用于遍历图的连通分量，同时记录边数和顶点数。
void DFS(MGraph &G, int v, vector<int> &visited, int &edgeCount, int &vertexCount) {
    visited[v] = 1;  // 标记顶点 v 为已访问
    vertexCount++;   // 统计顶点数

    for(int i = 0; i < G.numVertices; ++i) {
        if(G.edges[v][i] == 1) {  // 如果 v 和 i 之间有边
            edgeCount++;  // 统计边数（无向图中每条边会被计算两次）
            if(visited[i] == 0) {
                DFS(G, i, visited, edgeCount, vertexCount);
            }
        }
    }
}

// 判断每个连通分量是否是无环的，并统计无环连通分量的数量。
int countAcyclicComponents(MGraph &G) {
    vector<int> visited(G.numVertices, 0);  // 记录顶点是否被访问
    int cnt = 0;  // 记录无环连通分量的个数

    for(int i = 0; i < G.numVertices; ++i) {
        if(visited[i] == 0) {  // 找到一个未访问的顶点，开始一个新的连通分量的DFS
            int edgeCount = 0;
            int vertexCount = 0;
            DFS(G, i, visited, edgeCount, vertexCount);

            // 每条边在无向图中会被计算两次，所以需要除以2
            edgeCount /= 2;

            // 判断是否是无环图：边数 = 顶点数 - 1
            if(edgeCount == vertexCount - 1) {
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    MGraph G;
    // 初始化G的值，包括顶点数、边数、邻接矩阵等

    cout << "Number of acyclic connected components: " << countAcyclicComponents(G) << endl;
    return 0;
}

• 时间复杂度：\(O(V^2)\)
• 空间复杂度：\(O(V)\)

---

判断无向图是不是一颗树

已知无向图G由顶点集 V 和边集E 组成，|V|>0。设图 G采用邻接矩阵存储，类型定义如下:

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

Info

请设计算法，判断无向图 G是不是一个树，如果是返回true，不是返回 false。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

---

【算法设计思想】：

要判断一个无向图是否为树，需要满足以下条件：

1. 连通性：从任意一个顶点出发，可以遍历图中的所有顶点。
2. 无环性：图中没有环。
3. 边的数量：对于一个有 n 个顶点的图，如果它是一个树，那么它应该有 n-1 条边。

Note

基于以上条件，算法设计如下：

1. DFS/BFS遍历：从任意一个顶点出发，使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图。在遍历过程中，统计访问的顶点数 vertexCount 和边数 edgeCount。
2. 判断连通性：如果一次遍历可以访问到所有顶点，说明图是连通的，否则不是连通图。
3. 判断无环性：遍历过程中，如果发现已经访问过的顶点再次出现，则说明图中有环。
4. 判断边的数量：如果遍历结束后，edgeCount == 2 * (n - 1)（无向图中，每条边会被计数两次），则满足树的边数条件。

代码实现

#include <iostream>
#include <vector>

using namespace std;

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

// DFS遍历图，并判断是否有环
bool DFS(MGraph &G, int v, vector<int> &visited, int parent, int &vertexCount, int &edgeCount) {
    visited[v] = 1;
    vertexCount++;

    for(int i = 0; i < G.numVertices; ++i) {
        if(G.edges[v][i] != 0) {
            edgeCount++;  // 统计边数

            if(!visited[i]) {
                if(DFS(G, i, visited, v, vertexCount, edgeCount)) {
                    return true;  // 如果DFS过程中发现环，直接返回true
                }
            } else if(i != parent) {
                // 如果访问的顶点不是当前顶点的父节点，并且已经访问过，说明有环
                return true;
            }
        }
    }
    return false;
}

// 判断无向图是否为树
bool isTree(MGraph &G) {
    vector<int> visited(G.numVertices, 0);
    int vertexCount = 0;
    int edgeCount = 0;

    // 从第一个顶点开始DFS
    if(DFS(G, 0, visited, -1, vertexCount, edgeCount)) {
        return false;  // 如果DFS发现有环，则不是树
    }

    // 如果所有顶点都被访问过，并且边的数量满足条件，则是树
    return (vertexCount == G.numVertices) && (edgeCount == 2 * (G.numVertices - 1));
}

int main() {
    MGraph G;
    // 初始化G的值，包括顶点数、边数、邻接矩阵等

    if(isTree(G)) {
        cout << "The graph is a tree." << endl;
    } else {
        cout << "The graph is not a tree." << endl;
    }

    return 0;
}

时间复杂度和空间复杂度分析

• 时间复杂度：O(V^2)
• 空间复杂度：存储访问状态的 visited 数组需要 ( O(V) ) 的空间

---

判断二分图 （leetcode785）改编

已知无向图G由顶点集 V 和边集E 组成，|V|>0。设图 G采用邻接矩阵存储，类型定义如下:

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

Info

若存在图 G的两个顶点子集A和B，满足AUB等于顶点集V，A∩B等于空集，且属于同一子集的任意两个顶点之间不存在边，则称图G为二分图。请设计算法，判断无向连通图G是不是二分图，如果是返回true，不是返回 false。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

【算法设计思想】：

要判断一个无向图是否为二分图，可以使用着色法（两种颜色）。具体步骤如下：

1. 顶点着色：给定图中的某一个顶点，给它染上一个颜色，然后对与它相邻的顶点染上另一种颜色。继续递归或迭代处理相邻顶点，保证相邻顶点染不同颜色。
2. 检测冲突：如果在着色过程中，发现一个顶点已经被染色，并且它与当前顶点颜色相同，那么图不是二分图，因为这意味着图中存在奇数长度的环。
3. 遍历所有顶点：由于图可能是不连通的，需要检查每一个未被访问的顶点，以确保整个图的所有连通分量都满足二分图的条件。

代码实现

#include <iostream>
#include <vector>

using namespace std;

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

// 使用DFS判断图是否为二分图
bool DFS(MGraph &G, int v, vector<int> &color, int currentColor) {
    color[v] = currentColor;

    for (int i = 0; i < G.numVertices; ++i) {
        if (G.edges[v][i] == 1) {  // 如果 v 和 i 之间有边
            if (color[i] == 0) {  // 如果顶点 i 未被染色
                if (!DFS(G, i, color, 3 - currentColor)) {  // 递归着色，交替使用颜色1和2
                    return false;
                }
            } else if (color[i] == currentColor) {  // 如果相邻顶点有相同的颜色，返回false
                return false;
            }
        }
    }
    return true;
}

// 判断无向图是否为二分图
bool isBipartite(MGraph &G) {
    vector<int> color(G.numVertices, 0);  // 颜色数组，0表示未染色，1和2表示两种颜色

    for (int i = 0; i < G.numVertices; ++i) {
        if (color[i] == 0) {  // 如果顶点未被染色
            if (!DFS(G, i, color, 1)) {  // 从顶点 i 开始染色
                return false;  // 如果发现不是二分图，直接返回 false
            }
        }
    }
    return true;  // 如果所有顶点都被正确染色，则是二分图
}

int main() {
    MGraph G;
    // 初始化G的值，包括顶点数、边数、邻接矩阵等

    if (isBipartite(G)) {
        cout << "The graph is bipartite." << endl;
    } else {
        cout << "The graph is not bipartite." << endl;
    }

    return 0;
}

时间复杂度和空间复杂度分析

• 时间复杂度：DFS在邻接矩阵存储的图上，遍历所有顶点和边的时间复杂度为 \(O(V^2)\)，其中 V 是顶点数。
• 空间复杂度：主要是存储颜色信息的数组 color，其空间复杂度为 \(O(V)\)。

---

求不带权的无向连通图G 中距离顶点v 最远的一个顶点

已知无向图G由顶点集 V 和边集E 组成，|V|>0。设图 G采用邻接矩阵存储，类型定义如下:

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    char vertexList[MAXV];  // 顶点表
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

Info

设计一个算法，求不带权无向连通图 G 中距离顶点 v 最远的一个顶点（所谓最远就是到顶点 v 的路径长度最大）要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

【算法思想】：

图 G 是不带权的无向连通图，一条边长度计为 1，因此求距离顶点 v 的最远的顶点即求距离顶点 v 的边数最多的顶点。基于图的广度优先搜索遍历方式，其体现了图中由某个顶点开始，以近向远扩展的方式遍历图中结点的过程。从顶点 v 出 发进行广度优先遍历类似于从顶点v 出发一层一层地向外扩展，到达顶点j，……， 最后到达的一个顶点k 即为距离v最远的顶点。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define MAXV 100  // 顶点数目的最大值

// 图的邻接矩阵存储结构定义
typedef struct {
    int numVertices;        // 图中实际的顶点数
    int numEdges;           // 图中实际的边数
    int edges[MAXV][MAXV];  // 邻接矩阵
} MGraph;

int findFarthestVertex(MGraph* G, int v) {
    int dist[MAXV];          // 存储从顶点 v 到其他顶点的距离
    bool visited[MAXV];      // 标记顶点是否被访问过
    queue<int> q;            // 队列用于BFS
    int farthestVertex = v;  // 距离最远的顶点
    int maxDist = 0;         // 最大距离

    // 初始化距离和访问标记数组
    for (int i = 0; i < G->numVertices; i++) {
        dist[i] = 0;
        visited[i] = false;
    }

    // 起始顶点入队并标记为已访问
    q.push(v);
    visited[v] = true;

    // 开始BFS遍历
    while (!q.empty()) {
        int current = q.front();
        q.pop();

        // 遍历当前顶点的所有邻接顶点
        for (int i = 0; i < G->numVertices; i++) {
            if (G->edges[current][i] == 1 && !visited[i]) {  // 存在边且未访问
                visited[i] = true;
                dist[i] = dist[current] + 1;  // 更新距离
                q.push(i);

                // 更新最远顶点和最大距离
                if (dist[i] > maxDist) {
                    maxDist = dist[i];
                    farthestVertex = i;
                }
            }
        }
    }

    return farthestVertex;
}

int main() {
    MGraph G;
    // 初始化图的顶点和边（这里的邻接矩阵是一个示例）
    G.numVertices = 5;
    G.numEdges = 6;
    int adjacencyMatrix[MAXV][MAXV] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 1, 1, 0, 1},
        {0, 0, 0, 1, 0}
    };
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.edges[i][j] = adjacencyMatrix[i][j];
        }
    }

    int startVertex = 0;
    int farthestVertex = findFarthestVertex(&G, startVertex);
    cout << "从顶点 " << startVertex << " 到最远的顶点是 " << farthestVertex << "。" << endl;

    return 0;
}

• 时间复杂度：O(V^2)，因为对于每个顶点，我们都要检查它与其他所有顶点之间是否存在边。
• 空间复杂度：O(V)，因为我们需要存储队列、距离数组和访问标记数组。

若题目让你用邻接表实现，思想一样，代码如下：

#define MAXV 1000  // 顶点数目的最大值

typedef struct ArcNode {  // 边表结点
    int adjvex;            // 指向的顶点的索引
    struct ArcNode* next;  // 指向下一条边的指针
} ArcNode;

typedef struct VNode {     // 顶点表结点
    char data;             // 顶点信息
    ArcNode* firstarc;     // 指向第一条依附于该顶点的边的指针
} VNode, AdjList[MAXV];

typedef struct {
    int numVertices, numEdges;  // 图中的顶点数和边数
    AdjList vertices;           // 顶点表
} ALGraph;

// 使用 BFS 找到最远顶点
int findFarthestVertex(ALGraph* G, int v) {
    int dist[MAXV];          // 存储从起始顶点到其他顶点的距离
    bool visited[MAXV];      // 标记顶点是否被访问过
    int maxDist = 0;         // 最大距离
    int farthestVertex = v;  // 最远的顶点

    // 初始化距离和访问标记数组
    for (int i = 0; i < G->numVertices; i++) {
        dist[i] = -1;  // 使用 -1 表示尚未访问
        visited[i] = false;
    }

    // 使用队列进行 BFS
    int queue[MAXV];
    int front = 0, rear = 0;

    // 起始顶点入队并标记为已访问
    queue[rear++] = v;
    visited[v] = true;
    dist[v] = 0;

    while (front < rear) {
        int current = queue[front++];

        // 遍历当前顶点的所有邻接顶点
        ArcNode* node = G->vertices[current].firstarc;
        while (node != NULL) {
            int neighbor = node->adjvex;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                dist[neighbor] = dist[current] + 1;
                queue[rear++] = neighbor;

                // 更新最远顶点和最大距离
                if (dist[neighbor] > maxDist) {
                    maxDist = dist[neighbor];
                    farthestVertex = neighbor;
                }
            }
            node = node->next;
        }
    }

    return farthestVertex;
}