本题要求实现一个函数,输出有向图所有出度为0的顶点。 函数接口定义: void PrintV(MGraph G); G为采用邻接矩阵作为存储结构的有向图。 裁判测试程序样例: #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct { char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 }MGraph;
时间: 2024-02-05 18:10:28 浏览: 32
实现思路:
遍历邻接矩阵的每一行,如果该行所有元素都为0,则说明该顶点的出度为0,输出该顶点即可。
代码实现:
```c
void PrintV(MGraph G){
int i, j, flag;
for(i = 0; i < G.vexnum; i++){
flag = 1;
for(j = 0; j < G.vexnum; j++){
if(G.arcs[i][j] != 0){
flag = 0;
break;
}
}
if(flag == 1){
printf("%c ", G.vexs[i]);
}
}
}
```
相关问题
有向图输出出度为0顶点
可以使用DFS或BFS遍历有向图,当遍历到一个顶点时,检查它的出度是否为0,如果是,则将该顶点输出。以下是DFS的实现示例:
```
void dfs(int v, vector<int> adj[], vector<bool>& visited, vector<int>& outdegree_zero) {
visited[v] = true;
if (adj[v].size() == 0) { // 检查出度是否为0
outdegree_zero.push_back(v);
}
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u, adj, visited, outdegree_zero);
}
}
}
vector<int> findOutdegreeZeroVertices(int n, vector<pair<int, int>>& edges) {
vector<int> adj[n];
for (auto e : edges) {
int u = e.first, v = e.second;
adj[u].push_back(v);
}
vector<bool> visited(n, false);
vector<int> outdegree_zero;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited, outdegree_zero);
}
}
return outdegree_zero;
}
```
其中,`n`是顶点个数,`edges`是边的集合,每条边表示为一对`(u, v)`,表示从顶点`u`到顶点`v`有一条有向边。`adj`是邻接表,`adj[u]`表示顶点`u`的所有出边所连接的顶点。`visited`记录每个顶点是否已被访问过,`outdegree_zero`保存所有出度为0的顶点。最后调用`findOutdegreeZeroVertices(n, edges)`即可输出所有出度为0的顶点。
用c语言写出有向图输出出度为0的顶点
以下是一个简单的 C 语言程序,用于输出有向图中出度为 0 的顶点:
```
#include <stdio.h>
#define MAX_VERTICES 100 // 最大顶点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int outdegree[MAX_VERTICES]; // 出度数组
int main() {
int n; // 顶点数
scanf("%d", &n);
// 读入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
}
}
// 计算出度数组
for (int i = 0; i < n; i++) {
int degree = 0;
for (int j = 0; j < n; j++) {
if (adj[i][j]) {
degree++;
}
}
outdegree[i] = degree;
}
// 输出出度为 0 的顶点
for (int i = 0; i < n; i++) {
if (outdegree[i] == 0) {
printf("%d\n", i);
}
}
return 0;
}
```
该程序先读入有向图的邻接矩阵,然后计算每个顶点的出度,并输出出度为 0 的顶点。