本文目录一览:
c语言判断有向图G是否是一棵以v0为根的有向树
遍历一下算出这棵树的深度k,然后用公式看看深度和点数之间是否具有点数n=2^k-1的关系,具有就是完全二叉树,否则不是。
C语言,判断树的编程
一般构树的题都用最小生成树算法,但鉴于你的这题的特殊性,直接深搜,O(n)的时间复杂度就可以过了
#includecstdio
#includecstring
using namespace std;
bool bo[1100];
int n,m,a[1100][1100];
void search(int x){
for(int i=1;i=a[x][0];i++){//询问与x相连的每一个点是否染了色
int y=a[x][i];
if(!bo[y]){//如果y没有被染色,就把y染色,并用y去更新别的节点
bo[y]=1;
search(y);
}
}
}
int main(){
scanf("%d%d",n,m);//这里需要你输入结点个数和边数,比如你的那组数据就输入10 9表示10个点,9条边
if(mn-1){printf("NO\n");return 0;}//如果你的边数比节点数-1还要小的话,那根本不可能联成一个整体
for(int i=1;i=m;i++){
int x,y;scanf("%d%d",x,y);
a[x][++a[x][0]]=y;//记录下x这个点可以连到y这个点,下同
a[y][++a[y][0]]=x;
}
memset(bo,0,sizeof(bo));//刚开始时除节点1外没有一个节点是在这个图中的,然后从1开始往别的点染色
bo[1]=1;
search(1);
for(int i=1;i=n;i++)
if(!bo[i]){//如果有点没有被染色就说明不能连成一棵树
printf("NO\n");
return 0;
}
printf("YES\n");
return 0;
}
平衡二叉树的判定的c语言算法
设置一个char a[]来保存输入的Input 然后遍历数组a[],直到strlen 根据a[]/删除平衡平衡二叉树的结点e,并保持平衡二叉树的性质。 int
判断完全二叉树用C语言编写
用一个线性表和一个队列,表存放的是边集,队列用于按层次遍历。程序流程如下
1 初始化空表、空队;
2 输入结点数、指定根结点,输入边到表中;
3 根结点进队;
4 将队首出队到p;
5 若表为空,返回1(真)。不空则在表中查找第一项等于p的边i。若找到,将边i的第二项进队,从表中删除边i。若没有找到,则返回0(假)。
6 若表为空,返回1(真)。不空则在表中查找第二项等于p的边i。若找到,将边i的第一项进队,从表中删除边i。若没有找到,则返回0(假)。
7 跳到4。
补充提供一个相应的程序代码如下,你可以试试
#include stdio.h
#define N 1024
void main( )
{
short list[N][2], queue[N], listLength = 0, front = 0, rear = 0, r, n, i, p;/*1 初始化空表,空队*/
char flag; /*flag是判断结果标识*/
scanf("%d%d", n, r); /*2 输入结点数、指定根结点,输入边到表中*/
for(i = 0; i n - 1; i++)
scanf("%d%d", list[i][0], list[i][1]);
listLength = n - 1;
queue[rear++] = r; /*3 根结点进队*/
while(1) {
p = queue[front++]; /*4 将队首出队到p*/
if(listLength == 0) { /*5 如果表为空,则返回1(真)*/
flag = 1;
break;
}
for(i = 0; i listLength list[i][0] != p; i++); /*寻找第一项等于p的边i*/
if(i == listLength) { /*如果没有找到,返回0(假)*/
flag = 0;
break;
}
queue[rear++] = list[i][1]; /*将边i的第二项进队*/
for(; i listLength - 1; i++) /*删除边i*/
list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];
listLength--;
if(listLength == 0) { /*6 若表为空,返回1(真)*/
flag = 1;
break;
}
for(i = 0; i listLength list[i][1] != p; i++); /*在表中查找第二项等于p的边i*/
if(i == listLength) { /*如果没有找到,返回0(假)*/
flag = 0;
break;
}
queue[rear++] = list[i][0]; /*将边i的第一项进队*/
for(; i listLength - 1; i++) /*删除边i*/
list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];
listLength--;
} /*7 跳到4*/
if(flag)
printf("yes\n");
else
printf("no\n");
}
运行结果
C语言(关于图最小生成树方法)
/*
邻接矩阵存储图
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/
#include stdio.h
#include limits.h
#define N 100
int p[N], key[N], tb[N][N];
void prim(int v, int n)
{
int i, j;
int min;
for (i = 1; i = n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i = n; i++)
{
min = INT_MAX;
for (j = 1; j = n; j++)
if (key[j] 0 key[j] min)
{
v = j;
min = key[j];
}
printf("%d%d ", p[v], v);
key[v] = 0;
for (j = 1; j = n; j++)
if (tb[v][j] key[j])
p[j] = v, key[j] = tb[v][j];
}
}
int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf("%d%d", n, m))
{
for(i = 1; i = n; i++)
{
for (j = 1; j = n; j++)
tb[i][j] = INT_MAX;
}
while (m--)
{
scanf("%d%d%d", u, v, w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf("\n");
}
return 0;
}