请用c语言完成给定无权有向图G(V,E),请判断G是否是一个有向无环图(DAG)。
时间: 2024-02-06 22:10:10 浏览: 28
可以使用拓扑排序来判断一个有向图是否为DAG。
具体步骤如下:
1. 统计每个顶点的入度,存储在数组indegree中。
2. 将入度为0的顶点加入队列queue中。
3. 取出队头顶点u,并将其从图中删除,即将u所能到达的所有顶点的入度减1。如果有某个顶点的入度减为0,则将其加入队列queue中。
4. 重复步骤3,直到队列queue为空。
5. 如果图中还有顶点没有被删除,则说明图中存在环,即不是DAG。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100 // 最大顶点数
typedef struct node{
int v; // 顶点编号
struct node *next; // 指向下一个邻接点
}Node;
Node* graph[MAXV]; // 邻接表
int indegree[MAXV]; // 入度数组
int isDAG(int n) // 判断是否为DAG
{
int i, v, count = 0;
Node *p;
int queue[MAXV], front = 0, rear = 0;
// 初始化入度数组和邻接表
for(i = 0; i < n; i++){
indegree[i] = 0;
graph[i] = NULL;
}
// 读入图的边信息,建立邻接表和入度数组
while(scanf("%d", &v) != EOF){
Node *newnode = (Node*)malloc(sizeof(Node));
newnode->v = v;
newnode->next = graph[i];
graph[i] = newnode;
indegree[v]++;
}
// 将所有入度为0的顶点加入队列
for(i = 0; i < n; i++){
if(indegree[i] == 0){
queue[rear++] = i;
}
}
// 拓扑排序
while(front != rear){
v = queue[front++];
count++;
for(p = graph[v]; p != NULL; p = p->next){
indegree[p->v]--;
if(indegree[p->v] == 0){
queue[rear++] = p->v;
}
}
}
// 判断是否为DAG
if(count == n){
return 1;
}else{
return 0;
}
}
int main()
{
int n; // 顶点数
scanf("%d", &n);
if(isDAG(n)){
printf("It is a DAG!\n");
}else{
printf("It is not a DAG!\n");
}
return 0;
}
```