(2) 代码如下：

强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## (2) 代码如下：

int isConnected(ALGraph G)
{
    bool visited[MAXV] = {false};
    //1.队列q保存待访问结点，将0号元素入队。
    int q[MAXV]; //队列q存储待访问顶点
    int front = 0, rear = 0; //队头front和队尾rear
    int u = 0; //选择0号顶点作为起始顶点
    visited[u] = true; q[rear++] = 0;
    //2.如果队中还有元素则循环处理
    while (front &lt; rear)
    {
        u = q[front++];
        ArcNode* p = G.VerticesList[u].firstarc;
        while (p != NULL)
        {
            int v = p-&gt;adjvex; // v是u的相邻顶点
            if (visited[v] != true) // 如果v未被访问则入队
            {
                visited[v] = true;
                q[rear++] = v;
            }
            p = p-&gt;nextarc;
        }
    }
    //3.扫描每个顶点是否都已被访问
    for (int i = 0; i &lt; G.numVertices; i++) // 检查所有顶点是否访问过
    if (visited[i] != true)
    return 0; //图不连通
    return 1; 机考矿 //图连通
}


## (3) 时间复杂度：O(n + e)

## 本题 DFS 和 BFS 都可以

## 习题5-3

给定一个用邻接表保存的无向图 G，设计算法 int HasCycle(ALGraph \*G) 判断该图是否含有环，若含有环则返回1，否则返回0。邻接表定义如下：

typedef struct ArcNode
{
    int adjvex; // 该弧所指向的顶点
    struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode; //边结点
typedef struct
{
    ArcNode *VerticesList[MAXV]; //顶点数组
    int numVertices, arcnum; // 图的当前顶点数和弧数
}ALGraph;


<!-- page 235 -->

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

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

【解析】判断图是否有环可以用DFS 遍历，遍历完成后如果存在下一个要访问的结点已被访问过则说明存在环，否则不存在环。【答案】（1）使用深度优先遍历DFS算法：从0号顶点开始，遍历其所有相邻顶点。如果访问过程中遇到已经访问过的顶点（且不是他的父结

## (2) 代码如下：

bool visited[MAXV] = {false}; // 记录顶点是否被访问过
bool DFS(ALGraph *G, int v, int parent)
{
    visited[v] = true;
    ArcNode *p = G-&gt;VerticesList[v];
    while (p != NULL)
    {
        int u = p-&gt;adjvex;
        if (visited[u] != true)
        if (DFS(G, u, v) == true) return true;
        else;
        else
        if (u != parent) return true;
        p = p-&gt;nextarc;
    }
    return false;
}
int HasCycle(ALGraph *G)
{
    for (int i = 0; i &lt; G-&gt;numVertices; i++)
    visited[i] = false;
    for (int v = 0; v &lt; G-&gt;numVertices; v++)
    if (visited[v] != true)
    if (DFS(G, v, -1) == true) return 1;
    return 0;
}


## (3) 时间复杂度：O(n + e)

<!-- page 236 -->

int parent[MAXV];
//边结构体定义


题目中给的是 ALGraph G，DFS 中也是 ALGraph G，所以 G 后面应该写 "->"而不是"."，请思考这样写有何好处。

## 习题5-4

给定一个用邻接表保存的带权无向图 G，你可以直接调用该函数 ArcNode\* FindEdge() 得到一个指针，指向当前未处理过的边中权值最小的那条边(内部实现细节不需要考虑)。设计算法int MSTWeight(ALGraph G) 判断返回最小生成树的权值之和。邻接表定义如下： 人

<!-- verified-by-hand -->
> [!success] 已结合原文第 236 页及 Markdown 上下文人工校对
> ArcNode 左花括号行混入水印，VNode 左花括号丢失。
typedef struct ArcNode
{
    int ivex, jvex;
    struct ArcNode *nextarc;
    int weight;
} ArcNode;
typedef struct
{
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct
{
    VNode VerticesList[MAXV];
    int numVertices, arcnum;
} ALGraph;


(1)FindEdge()函数每次会从某个数据结构中取出最小边，应该使用什么数据结构？为什么？ (2)给出算法的基本设计思想。(3)采用C 或C++ 语言描述算法，关键之处给出注释。

【答案】(1)FindEdge()的内部数据结构为了每次都能快速找到权值最小的边，最适合的数据结构是最小堆(Min-Heap)，也叫优先队列。原因：把所有边放进最小堆里，堆顶永远是当前权值最小的边。每次获取最小边的操作(出队）时间复杂度是O(loge)，这比每次都遍历所有边来找最小值的 O(e) 要快得多。(2)

1. 准备一个并查集，一开始每个顶点都是一个单独的集合。

2. 循环，直到已经选中 n-1 条不成环的边：a. 每次通过 FindEdge() 得到一条边 〈u, v>。b.用并查集检查u和ν是不是已经在同一个集合里了。如果在，说明加上这条边会形成环，就跳过边〈u，v>。c. 如果不在，选择该边、合并这两个集合，把边的权重加到总和里)。

3. 重复这个过程，直到选出了 n-1 条边，最小生成树就找到了。(3)

<!-- page 237 -->

typedef struct {
    int u, v; // 边的两个顶点
    int weight: //边的权值
} Edge;
// 查找根结点
int Find(int x)
{
    if (parent[x] != x)
    parent[x] = Find(parent[x]); //路径压缩
    return parent[x];
}
//并查集:合并集合
void Union(int x, int y) {
    parent[Find(y)] = Find(x);
}
int MSTWeight(ALGraph G)
{
    Edge edges[MAXE] ; //边集数组
    int count = 0; //统计已纳入生成树中的边数
    int totalWeight = 0;
    //1.初始化并查集，初始时所有顶点属于不同集合。
    for (int i = 0; i &lt; G.numVertices; i++)
    parent[i] = i;
    // 2.循环,直到选出 n-1 条不成环的边
    while (count &lt; G.numVertices-1)
    {
        // 3-a.通过 FindEdge() 得到最
        ArcNode *p = FindEdge();
        //3-b.对于还未处理的最小边，使用并查集判断该边的两个端点分别属于哪个集合
        int rootU = Find(p-&gt;ivex);
        int rootV = Find(p-&gt;jvex);
        //3-c.如果不属于同一个集合则选择该边、合并这两个集合
        if (rootU != rootV)
        {
            Union(rootU, rootV);
            totalWeight += p-&gt;weight; count++;
        }
    }
} return totalWeight;


## 习题5-5

<!-- page 238 -->

设无向图G=(V，E)，如果顶点可被分割为两个互不相交的子集，并且图中每条边的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。无向图G为二分图的充要条件是：G中至少包含两个顶点且G中任意一个简单回路所包含的边数为偶数。图G采用邻接矩阵存储，类型定义如下：

typedef struct {
    int numV, numE; // 顶点数和边数
    char VerticesList[MAXV]; // 顶点信息
    int Edge[MAXV] [MAXV]; //权值矩阵
}MGraph;


请设计算法 int IsBipartite (MGraph G)，判断无向图 G 是否为二分图，是则返回 1，否则返回0。(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 V

【解析】本题是要判断是否存在含有偶数个元素的环，此处可以用 DFS也可以用BFS。【答案】（1）使用广度优先遍历BFS算法：从任意未染色的顶点开始，先将起始0号顶点染色为1，并将其入队。依次处理队列中的顶点，出队一个顶点v，遍历其所有相邻顶点u。若u未被染色，则将其染色为与ν不同的颜色(1 或2)，并将其入队。若u已被染色且颜色与ν相同，则说明图G不是二分图，返回0。重复上述步骤，直到队列为空。若所有顶点都被染色且没有相邻顶点颜色相同的情况，则说明图G是二分图，返回1。(2)代码如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 238 页及 Markdown 上下文人工校对
> 无条件 continue 使每个分量都被跳过；while 缺花括号，颜色冲突判断次序和 return 也丢失。正文还把二分图条件误写成检查偶环，应为不存在奇环。
int IsBipartite(MGraph G)
{
    int color[MAXV] = {0}, q[MAXV];
    for (int s = 0; s &lt; G.numV; s++)
    {
        if (color[s] != 0) continue;
        int front = 0, rear = 0;
        color[s] = 1;
        q[rear++] = s;
        while (front &lt; rear)
        {
            int u = q[front++];
            for (int w = 0; w &lt; G.numV; w++)
            {
                if (G.Edge[u][w] == 0) continue;
                if (color[w] == 0)
                {
                    color[w] = 3 - color[u];
                    q[rear++] = w;
                }
                else if (color[w] == color[u]) return 0;
            }
        }
    }
    return 1;
}


<!-- page 239 -->

## 习题5-6

请设计算法：int ponents(ALGraph G)，对给定的无向图G，返回其中连通分量的个数。邻接表定义如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 239 页及 Markdown 上下文人工校对
> ArcNode、VNode 和 ALGraph 的左花括号全部丢失。
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct
{
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct
{
    VNode VerticesList[MAXV];
    int numVertices, arcnum;
} ALGraph;


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

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

## 【答案1】DFS （1）

1. 设置计数器 count，初始为 0。准备一个 visited 数组，记录哪些点走过了，初始都为falseX

2. 循环检查每个顶点：如果该顶点还未访问过，说明找到了一个新的连通分量的起点，就把count 加1，递归调用深度优先遍历 DFS。(2)代码如下：

bool visited[MAXV] = {false};
//DFS函数，用于遍历一个连通分量
void DFS(ALGraph G, int v)
{
    visited[v] = true;
    ArcNode *p = G.VerticesList[v].firstarc;
    while (p != NULL)
    {
        if (visited[p-&gt;adjvex] != true)
        DFS(G, p-&gt;adjvex);
        p = p-&gt;nextarc;
    }
}
int ponents(ALGraph G)
{
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    if (visited[i] != true)
    {
        count++;
        DFS(G, i);
    }
    return count;
}


<!-- page 240 -->

(3) O(n+e)。


## 【答案2】并查集 （1)

1. 设置并查集 father，初始时每个结点的 father[i] = i 自身。

2. 遍历所有边 <u， v>，合并 u 和 ν 所在的并查集。

3. 统计这些顶点属于几个集合。

<!-- verified-by-hand -->
> [!success] 已结合原文第 240 页及 Markdown 上下文人工校对
> Union 缺少闭合花括号，导致主函数被非法嵌套；图类型名和题目函数名也被 OCR 破坏。
int father[MAXV];
int find(int x)
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}
void Union(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) father[fy] = fx;
}
int components(ALGraph G)
{
    for (int i = 0; i &lt; G.numVertices; i++) father[i] = i;
    for (int i = 0; i &lt; G.numVertices; i++)
        for (ArcNode *p = G.VerticesList[i].firstarc; p != NULL; p = p-&gt;nextarc)
            Union(i, p-&gt;adjvex);
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
        if (find(i) == i) count++;
    return count;
}


<!-- page 241 -->

## 习题5-7

## 已知无向图G 类型定义如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 241 页及 Markdown 上下文人工校对
> EBox 与 VexBox 的左花括号丢失。
typedef struct EBox
{
    int mark;
    int ivex, jvex;
    struct EBox *ilink, *jlink;
} EBox;
typedef struct VexBox
{
    char data;
    EBox *firstEdge;
} VexBox;
typedef struct
{
    VexBox adjMulList[MAXV];
    int numVertices, numEdges;
} AMLGraph;


请设计算法：int KDegree(AMLGraph G, int k)，对给定的无向图 G，返回图 G 中顶点下标为k的顶点的度。例如图G2，k=1 时，对应顶点V2，度为3，返回3。要求：(1)请问图的

<!-- page 242 -->

#define MAXV 100
//边结点
typedef struct ArcBox


这种存储结构叫什么？ (2)给出算法的基本设计思想。(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

## 【解析】(1)邻接多重表(2)

1. 从 G.adjMulList[k].firstEdge 开始，拿到第一条边。

2. 循环执行，直到查找完链表(NULL)： a. 计数器加一。b. 根据当前顶点是ivex还是jvex,选择正确的下一条边指针。(3) 人

int KDegree(AMLGraph G, int k)
{
    int degree = 0;
    // 1.从第一条边开始
    EBox *p = G.adjMulList[k].firstEdge;
    // 2.循环执行，直到查找完链表
    while (p != NULL)
    {
        2-a.计数器加一
        degree++;
        //2-b.根据当前顶点是ivex还是jvex，选择正确的下一条边指针
        if (p-&gt;ivex == k)
        p = p-&gt;ilink;
        else
    } p = p-&gt;jlink;
    return degree;
}


## 习题5-8

有向完全图的定义是：在有向图中，任意两个顶点u 和ν之间，必须同时存在u->v和v->u两条弧。对于有向图G，请设计算法：int IsComplete(OLGraph G)判断它是不是有向完全图，如果是则返回1，否则返回0。请回答：（1）应该采用以下哪种数据结构保存：邻接多重表还是十字链表？ (2)写出该数据结构定义。(3)采用C 或C++ 语言描述算法，关键之处给出注释。

【解析】对于简单图来说，有向图是有向完全图等价于：e= n×(n-1)。或者可以遍历统计所有顶点，看每个顶点是否都可以到达其他顶点。【答案】（1）十字链表（2）定义：

<!-- page 243 -->

<!-- verified-by-hand -->
> [!success] 已结合原文第 243 页及 Markdown 上下文人工校对
> ArcBox、VexNode 和 OLGraph 的声明头/左花括号丢失，两个计数字段粘连。
typedef struct ArcBox
{
    int tailvex, headvex;
    struct ArcBox *hlink, *tlink;
    int weight;
} ArcBox;
typedef struct VexNode
{
    char data;
    ArcBox *firstin, *firstout;
} VexNode;
typedef struct
{
    VexNode VerticesList[MAXV];
    int numVertices, numEdges;
} OLGraph;


(3) 代码如下：

int IsComplete(OLGraph G)
{
    if (G.numEdges == G.numVertices*(G.numVertices-1))
    return 1; // e = n×(n-1)
    else 0;
}


或者统计所有结点的出度是否为 n-1：

int IsComplete(OLGraph G)
{
    //遍历所有顶点
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int count = 0; //统计到达几个顶点
        //遍历当前顶点i发出的所有边
        ArcNode *p = G.VerticesList[i].firstout; //请注意是出边
        while (p != NULL)
        count++; //访问对应边
        p = p-&gt;tlink; //起点相同
    }
    if (count != G.numVertices-1) return 0;
}
return 1; // 十算机 所有顶点都满足要求


<!-- page 244 -->