习题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)
{
int color[MAXV] = {0}, q[MAXV];
for (int s = 0; s < G.numV; s++)
{
if (color[s] != 0) continue;
int front = 0, rear = 0;
color[s] = 1;
q[rear++] = s;
while (front < rear)
{
int u = q[front++];
for (int w = 0; w < G.numV; w++)
{
if (G.Edge[u][w] == 0) continue;
if (color[w] == color[u]) return 0;
if (color[w] == 0)
{
color[w] = 3 - color[u];
q[rear++] = w;
}
}
}
}
return 1;
}
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;
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->adjvex] != true)
DFS(G, p->adjvex);
p = p->nextarc;
}
}
int ponents(ALGraph G)
{
int count = 0;
for (int i = 0; i < G.numVertices; i++)
if (visited[i] != true)
{
count++;
DFS(G, i);
}
return count;
}
int father[MAXV];
int find(int x)
{
if (father[x] != x) father[x] = find(father[x]);
return father[x];
}
void unite(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy) father[fy] = fx;
}
int ponents(ALGraph G)
{
for (int i = 0; i < G.numVertices; i++) father[i] = i;
for (int i = 0; i < G.numVertices; i++)
for (ArcNode *p = G.VerticesList[i].firstarc; p; p = p->nextarc)
unite(i, p->adjvex);
int count = 0;
for (int i = 0; i < G.numVertices; i++) if (find(i) == i) count++;
return count;
}
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)请问图的这种存储结构叫什么？
(2) 给出算法的基本设计思想。
(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
## 【解析】
(1) 邻接多重表
(2)
1. 从 G.adjMulList[k].firstEdge 开始，拿到第一条边。
2. 循环执行，直到查找完链表（NULL）：
a. 计数器加一。
b. 根据当前顶点是ivex还是jvex，选择正确的下一条边指针。
(3)
<!-- verified-by-hand -->
> [!success] 已结合原文第 173 页及 Markdown 上下文人工校对
> return 被错嵌进 while，后续十字链表类型定义也被串进同一函数。
int KDegree(AMLGraph G, int k)
{
int degree = 0;
EBox *p = G.adjMulList[k].firstEdge;
while (p != NULL)
{
degree++;
p = p->ivex == k ? p->ilink : p->jlink;
}
return degree;
}
int IsComplete(OLGraph G)
{
if (G.numEdges == G.numVertices*(G.numVertices-1))
return 1; // e = n×(n-1)
else 0;
}
int IsComplete(OLGraph G)
{
for (int i = 0; i < G.numVertices; i++)
{
int count = 0;
for (ArcBox *p = G.VerticesList[i].firstout; p; p = p->tlink) count++;
if (count != G.numVertices - 1) return 0;
}
return 1;
}
typedef struct{ //图的定义
int numVertices, numEdges; //图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表。MAXV为已定义常量
int Edge[MAXV][MAXV]; //邻接矩阵
}MGraph;
int IsExistEL(MGraph G)
{
int count = 0;
for (int i = 0; i < G.numVertices; i++)
{
int degree = 0;
for (int j = 0; j < G.numVertices; j++)
if (G.Edge[i][j] != 0) degree++;
if (degree % 2 == 1) count++;
}
return count == 0 || count == 2;
}
typedef struct
{
int numVertices, numEdges;
char VerticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
原资料配图 · 转写内容请回源核验
请设计算法：int printVertices(MGraph G)，对给定的任意非空有向图G，输出 G 中所有的 K 顶点，并返回 K 顶点的个数。要求：
1）给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
## 【解析】
出度大于入度的顶点称为K顶点，本题关键是遍历图求出所有顶点的入度和出度，才能判断出顶点是否为K顶点。依次判断所有顶点是否为K顶点，并统计数量即可。
注：以下两种答案本质一样，仅供参考
## 【答案】
(1)图的邻接矩阵G.Edge[i][j]>0表示i到j有边，二重循环遍历邻接矩阵，算出每个顶点的入读indegree和出度outdegree，然后判断每个顶点是否为 K顶点，如果是则输出并且计数器count+1，最后返回count即可。
(2) 写法 1:
int printVertices(MGraph G)
{
int indegree, outdegree; // 入度和出度
int count = 0; // 计数器count初值为0
for (int i = 0; i < G.numVertices; i++)
{
indegree = outdegree = 0; //更换i之后要清零，重新统计入度和出度
for (int j = 0; j < G.numvertices; j++)
if (G.Edge[i][j] > 0) outdegree++; // i到j有边，i的出度+1
for (int j = 0; j < G.numvertices; j++)
if (G.Edge[j][i] > 0) indegree++; // j到i有边，i的入度+1
if (outdegree > indegree) // 如果i的出度大于入度则说明i是K顶点
{
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int printVertices(MGraph G)
{
int count = 0;
for (int i = 0; i < G.numVertices; i++)
{
int indegree = 0, outdegree = 0;
for (int j = 0; j < G.numVertices; j++)
{
if (G.Edge[i][j] > 0) outdegree++;
if (G.Edge[j][i] > 0) indegree++;
}
if (outdegree > indegree)
{
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
typedef struct
{
int numVertices, numEdges;
char VerticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
原资料配图 · 转写内容请回源核验