返回主页
已有2条笔记
[数据结构 P2012] 已知有向图 G 采用邻接矩阵存储，类型定义如下：
未通过
已知有向图 G 采用邻接矩阵存储，类型定义如下：
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
将图中出度大于入度的顶点称为 K 顶点。例如在题41图中，顶点 a 和 b 都是 K 顶点。
设计算法 int printVertices(MGraph G)对给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。
(1)给出算法的设计思想。
(2)根据算法思想，写出 C/C++描述，并注释。
加入错题本
个人笔记
解答：
⑴
⑵...
用户登录可进行刷题及查看答案
解答：
⑴
⑵ 根据上述思路，C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int indegrees[G.numVertices];
int outdegrees[G.numVertices];
memset(indegrees, 0, sizeof(indegrees));
memset(outdegrees, 0, sizeof(outdegrees));
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
outdegrees[i] += G.Edge[i][j];
indegrees[j] += G.Edge[i][j];
}
}
int count = 0;
// 遍历indegrees和outdegrees数组统计出度大于入度的顶点
for (int i = 0; i < G.numVertices; i++) {
if (outdegrees[i] > indegrees[i]) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。
时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int count = 0, indegree = 0, outdegree = 0;
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
indegree = 0; // i的入度
outdegree = 0; // i的出度
for (int j = 0; j < G.numVertices; j++) {
outdegree += G.Edge[i][j];
indegree += G.Edge[j][i];
}
if (outdegree > indegree) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(1) ，使用了常数个辅助变量。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发