您的位置:

以图判树c语言,c语言关于树的算法

本文目录一览:

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;

}