【习题5-5】

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

## 【习题5-5】

设无向图G=(V,E)，如果顶点可被分割为两个互不相交的子集，并且图中每条边的两个顶点i和i分别属于这两个不同的顶点集，则称图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++语言描述算法，关键之处给出注释。

## 【习题5-6】

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

<!-- verified-by-hand -->
> [!success] 已结合原文第 160 页及 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)说明所设计算法的时间复杂度。

## 【习题5-7】

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

<!-- page 161 -->

<!-- verified-by-hand -->
> [!success] 已结合原文第 161 页及 Markdown 上下文人工校对
> AMLGraph 的左花括号丢失。
typedef struct
{
    VexBox adjMulList[MAXV];
    int numVertices, numEdges;
} AMLGraph;


typedef struct VexBox
{
    char data;
    EBox *firstEdge;
} VexBox;


<!-- verified-by-hand -->
> [!success] 已结合原文第 161 页及 Markdown 上下文人工校对
> 这是被分页拆散的 EBox 尾部，缺失结构体前半；需恢复完整边结点定义。
typedef struct EBox
{
    int mark;
    int ivex, jvex;
    struct EBox *ilink, *jlink;
} EBox;


//顶点信息//指向第一条依附该顶点的边

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

(1)请问图的这种存储结构叫什么？

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

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

## 【习题5-8】

有向完全图的定义是：在有向图中，任意两个顶点u和ν之间，必须同时存在u->v和v->u两条弧。对于有向图G，请设计算法：int IsComplete(OLGraph G)判断它是不是有向完全图，如果是则返回1，否则返回0。请回答：

(1)应该采用以下哪种数据结构保存：邻接多重表还是十字链表？

(2) 写出该数据结构定义。

(3)采用C或C++语言描述算法，关键之处给出注释。

## 5.4.2 真题

## 【2021年41题】

(15 分)已知无向连通图G由顶点集V和边集E组成，E>0，当G 中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为E的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下：

<!-- page 162 -->

typedef struct{ //图的定义
    int numvertices, numEdges; //图中实际的顶点数和边数
    char VerticesList[MAXv]; // 顶点表。MAXV为已定义常量
    int Edge[MAXV][MAXV]; //邻接矩阵
}MGraph;


请设计算法int IsExistEL(MGraph G)，判断G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求:

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

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

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

## 【2023年41题】

(13分）已知有向图G采用邻接矩阵存储，类型定义如下：

typedef struct // 图的类型定义
{
    int numVertices, numEdges; //图的顶点数和有向边数
    char VerticesList[ MAXV ]; // 顶点表，MAXV为已定义常量
    int Edge[ MAXV ][ MAXV ]; //邻接矩阵
} MGraph;


将图中出度大于入度的顶点称为K顶点。例如在下图中，顶点a和b为K顶点。


请设计算法：int printVertices(MGraph G)，对给定的任意非空有向图G，输出G 中所有的 K 顶点，并返回 K 顶点的个数。要求：

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

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

## 【2024年41题】

(13分）2023年10月26日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G采用邻接矩阵存储，类型定义如下。

<!-- verified-by-hand -->
> [!success] 已结合原文第 162 页及 Markdown 上下文人工校对
> MGraph 结构体缺少左花括号且 MAXV 大小写错误。
typedef struct
{
    int numVertices, numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;


请设计算法：int uniquely(MGraqh G)，判定 G 是否存在唯一的拓扑序列，若是，则返回1，否则返回0。要求如下。

1）给出算法的基本设计思想。（4分)

<!-- page 163 -->

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

## 5.5 章节答案


## 5.5.1 习题

## 习题5-1

给定一个用邻接表保存的有向图G，设计算法int OddInDegree(ALGraph G)，返回出度为奇数的顶点个数。邻接表定义如下：

<!-- verified-by-hand -->
> [!success] 已结合原文第 163 页及 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)

1. 设置出度数组 outdegree，初始为0。

2. 遍历所有顶点和边，统计每个顶点的出度。

3.扫描每个顶点，统计出度为奇数的顶点数。

(2)

<!-- verified-by-hand -->
> [!success] 已结合原文第 163 页及 Markdown 上下文人工校对
> while 无花括号导致指针不更新形成死循环；取模判断中的赋值号应为相等号。
int OddInDegree(ALGraph G)
{
    int count = 0;
    for (int i = 0; i &lt; G.numVertices; i++)
    {
        int outdegree = 0;
        for (ArcNode *p = G.VerticesList[i].firstarc; p != NULL; p = p-&gt;nextarc)
            outdegree++;
        if (outdegree % 2 == 1) count++;
    }
    return count;
}


<!-- page 164 -->

(3) O(n+e)


## 习题5-2

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

<!-- verified-by-hand -->
> [!success] 已结合原文第 164 页及 Markdown 上下文人工校对
> 题目重复的邻接表定义中三个结构体左花括号丢失。
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)说明所设计算法的时间复杂度。

【解析】判断图是否连通只需要从任意结点出发遍历即可，遍历完成后如果存在结点未访问则说明该图不连通，否则该图连通。遍历可以选择广度优先遍历BFS或深度优先遍历 DFS 中的一种，本方法用BFS 完成。

1. 队列q保存待访问结点，将0号元素入队。

2.如果队中还有元素则循环：选择队头元素u出队访问并记录，然后将u相邻的未入队过的顶点依次入队，循环执行直到队列访问完，BFS 完成。

3.扫描每个顶点是否都已被访问，如果存在顶点未被访问，则说明不连通，返回0；否则连通，返回1。

(2) 代码如下：

int isConnected(ALGraph G)

<!-- page 165 -->

<!-- verified-by-hand -->
> [!success] 已结合原文第 164-165 页及 Markdown 上下文人工校对
> 函数签名在代码围栏外，函数体缺少外层花括号。
int IsConnected(ALGraph G)
{
    if (G.numVertices == 0) return 1;
    bool visited[MAXV] = {false};
    int q[MAXV], front = 0, rear = 0;
    visited[0] = true;
    q[rear++] = 0;
    while (front &lt; rear)
    {
        int u = q[front++];
        for (ArcNode *p = G.VerticesList[u].firstarc; p; p = p-&gt;nextarc)
        {
            int v = p-&gt;adjvex;
            if (!visited[v])
            {
                visited[v] = true;
                q[rear++] = v;
            }
        }
    }
    for (int i = 0; i &lt; G.numVertices; i++) if (!visited[i]) return 0;
    return 1;
}


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

本题 DFS 和 BFS 都可以

## 习题5-3

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

<!-- page 166 -->

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


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

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

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

【解析】判断图是否有环可以用DFS遍历，遍历完成后如果存在下一个要访问的结点已被访问过则说明存在环，否则不存在环。

## 【答案】

(1）使用深度优先遍历DFS算法：从0号顶点开始，遍历其所有相邻顶点。如果访问过程中遇到已经访问过的顶点（且不是他的父结点），则说明存在环。一轮DFS 完成，继续判断是否还有顶点未访问，下一轮DFS从未访问的顶点开始。而如果访问完所有结点都未发现有环，则说明不存在环。

(2) 代码如下:

bool visited[MAXV] = {false}; 11
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 167 -->

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

## 习题5-4

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

<!-- verified-by-hand -->
> [!success] 已结合原文第 167 页及 Markdown 上下文人工校对
> ArcNode、VNode、ALGraph 均缺少左花括号。
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)

int parent[MAXV];


<!-- page 168 -->

<!-- verified-by-hand -->
> [!success] 已结合原文第 168 页及 Markdown 上下文人工校对
> MSTWeight 被错嵌进 Union，根变量大小写错误，且未处理 FindEdge 返回空指针。
int parent[MAXV];
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)
{
    int count = 0, totalWeight = 0;
    for (int i = 0; i &lt; G.numVertices; i++) parent[i] = i;
    while (count &lt; G.numVertices - 1)
    {
        ArcNode *p = FindEdge();
        if (p == NULL) return -1;
        int rootU = Find(p-&gt;ivex), rootV = Find(p-&gt;jvex);
        if (rootU != rootV)
        {
            Union(rootU, rootV);
            totalWeight += p-&gt;weight;
            count++;
        }
    }
    return totalWeight;
}


<!-- page 169 -->