c语言生成树

❶ c语言算法求解：对任意给定的网络（顶点数和边数自定），设计算法生成它的最小生成树。

上一个图和代码：

图1为要创建的图，图2为对应的最小生成树

代码为：

//图论之最小生成树：prim算法实现

#include"stdio.h"

#include"malloc.h"

//声明

voidoutput(structadjacentlisthead*alh,intmapsize);

structadjacentlistson//邻接表项结构体

{

intsonelement;

intquanvalue;

structadjacentlistson*next;

};

structadjacentlisthead//邻接表头结构体

{

charflag;

intelement;

intcurqvalue;

structadjacentlisthead*previous;

structadjacentlistson*startson;

};

structadjacentlisthead*mapinitialnize(intmapsize)//初始化图函数

{

structadjacentlisthead*alh=NULL;

structadjacentlistson*newnode=NULL;

inti,x,y,z;

alh=malloc(sizeof(structadjacentlisthead)*mapsize);

if(alh==NULL)

returnNULL;

for(i=0;i<mapsize;i++)

{

alh[i].flag=0;

alh[i].element=i+1;

alh[i].curqvalue=0;

alh[i].previous=NULL;

alh[i].startson=NULL;

}

scanf("%d%d%d",&x,&y,&z);

while(x&&y)//直到输入的x,y中至少有一个0为止

{

newnode=malloc(sizeof(structadjacentlistson));

newnode->sonelement=y;

newnode->quanvalue=z;

newnode->next=alh[x-1].startson;

alh[x-1].startson=newnode;

scanf("%d%d%d",&x,&y,&z);

}

returnalh;

}

intfindminnode(structadjacentlisthead*alh,intmapsize)//找到最小权值对应的结点

{

inti,minvalue=~(1<<(sizeof(int)*8-1)),minplace=0;

for(i=0;i<mapsize;i++)

{

if(alh[i].flag==0&&alh[i].curqvalue!=0)

{

if(alh[i].curqvalue<minvalue)

{

minvalue=alh[i].curqvalue;

minplace=i+1;//

}

}

}

returnminplace;

}

voidfindthemintree(structadjacentlisthead*alh,intstartplace,intmapsize)//找到最小生成树

{

structadjacentlistson*alstmp=NULL;

intcurplace=startplace;

while(curplace)

{

alstmp=alh[curplace-1].startson;

alh[curplace-1].flag=1;//正在访问

while(alstmp)

{

if(alh[alstmp->sonelement-1].flag==0)

{

if(alh[alstmp->sonelement-1].curqvalue==0||(alh[alstmp->sonelement-1].curqvalue>alstmp->quanvalue))//比较方法与有权图有一点不同

{

alh[alstmp->sonelement-1].curqvalue=alstmp->quanvalue;

alh[alstmp->sonelement-1].previous=&alh[curplace-1];

}

}

alstmp=alstmp->next;

}

curplace=findminnode(alh,mapsize);//通过函数找到最小的一个结点

}

}

voidoutput(structadjacentlisthead*alh,intmapsize)

{

inti;

for(i=0;i<mapsize;i++)

{

printf("%d点的权值为：%d ",i+1,alh[i].curqvalue);

}

printf("................................................... ");

}

intmain()

{

structadjacentlisthead*alh=NULL;

intmapsize=7,startplace=1;

alh=mapinitialnize(mapsize);

findthemintree(alh,startplace,mapsize);

output(alh,mapsize);

}

输入数据对应第一图：

122

134

141

212

243

2510

314

342

365

411

423

432

457

468

474

5210

547

576

635

648

671

744

756

761

000

❷ 求无向连通图的生成树（用c语言设计程序）

不知道你要的是不是这个 完整实现如下： #define INFINITY 65535typedef int status;# include <stdio.h># include <stdlib.h># include <conio.h># include "string.h"# define maxlen 10typedef struct{ char vexs[maxlen][maxlen];/*顶点信息集合,我们用它来存入顶点名字*/ int vexnum,arcnum;/*顶点数和边数*/ int arcs[maxlen][maxlen];/*邻接矩阵*/}graph;//定位输入节点的名称int LocateVex(graph G,char u[maxlen]){int i;for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1;} void prim(graph &g)/*最小生成树*/{ int i,j,k,min,w,flag; int lowcost[maxlen];/*权值*/ int closet[maxlen];/*最小生成树结点*/ char va[maxlen],vb[maxlen]; //初始化邻接矩阵 //printf("请输入顶点数和边数：\n"); //scanf("%d%d",&g.vexnum,&g.arcnum); g.vexnum=6; g.arcnum=10; printf("请输入顶点信息(我们这里指名字)：\n"); for(int j=0;j<g.vexnum;j++) scanf("%s",g.vexs[j]); for(i=0;i<g.vexnum;++i) for(j=0;j<g.vexnum;++j)//初始化邻接矩阵 { g.arcs[i][j]=INFINITY; //任意两个顶点间距离为无穷大。 }//for /*printf("请输入%d条弧的弧尾 弧头 权值（以空格为间隔)\n",g.arcnum); for(k=0;k<g.arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w);//用%*c吃掉回车符 i=LocateVex(g,va); //注意，这里定义的是char va[5]，也就是说va是首地址 j=LocateVex(g,vb); g.arcs[i][j]=w; //无向网 g.arcs[j][i]=w; //无向网 }//for */ g.arcs[0][1]=6; g.arcs[1][0]=6; g.arcs[0][2]=1; g.arcs[2][0]=1; g.arcs[0][3]=5; g.arcs[3][0]=5; g.arcs[1][2]=5; g.arcs[2][1]=5; g.arcs[1][4]=3; g.arcs[4][1]=3; g.arcs[2][3]=5; g.arcs[3][2]=5; g.arcs[2][4]=6; g.arcs[4][2]=6; g.arcs[2][5]=4; g.arcs[5][2]=4; g.arcs[3][5]=2; g.arcs[5][3]=2; g.arcs[4][5]=6; g.arcs[5][4]=6; printf("最小生成树的边为:\n"); for(i=1;i<g.vexnum;i++) { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[0]=0; //初始v1是属于集合U的，即设它是最小生成树中节点的一员 j=1; //V是顶点集合 for(i=1;i<g.vexnum;i++) { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; //记录当前要加入集合U的节点号 }//if if(i==1) flag=0; else flag=closet[k]; //还没有加入集合U的节点的closet[]值是 //记录了上一次加入集合U的节点号 closet[k]=0; //将刚刚找到的点加入到集合U中 printf("(%s,%s),",g.vexs[k],g.vexs[flag]);//输出刚刚找到的最小生成树树枝 for(j=1;j<g.vexnum;j++) if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; //更新lowcost[]的值，且在还没有加入U集合的 //的closet[]中记录刚刚加入U集合的节点号以备 //下一循环中输出用 closet[j]=k; } }} int main(){graph g;prim(g);}

❸ C语言数据结构的最小生成树不是唯一的吗

生成树是一个包含n个结点的连通图G的一个子图。该子图必须包含G中的所有n个结点以及G中的n-1条边并且保持连通性。
最小生成树是G的所有可能的生成树中，n-1条边的权值总和最小的那一个（或多个）生成树。

❹ 用prim算法的思想，用C语言编写出最小生成树的方法的代码

PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){
//求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)；
//根据新红点v调整候选轻边集
}
}

❺ c语言绘制二叉树

你那里是打印出的啥？不会是没有存下数据打印了乱码吧？:)

[修改]
比如，我把和你的二叉树相关的代码去掉，改了一下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <graphics.h>

int main()
{
char str[10];
int x = 100, y = 100;
int e = 9;

/* select a driver and mode that supports */
/* multiple drawing colors. */
int gdriver = DETECT, gmode = VGA, errorcode;

detectgraph(&gdriver, &gmode);
/* initialize graphics and local variables */
initgraph(&gdriver, &gmode, "d:\\bc\\bgi");

/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk) /* an error occurred */
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1); /* terminate with an error code */
}

setcolor(BLACK);
setfillstyle(SOLID_FILL,BLACK);
fillellipse(x,y,9,9);
setcolor(WHITE);
circle(x,y,10);

sprintf(str,"%d",e);
outtextxy(x-3,y-2,str);

/* clean up */
getch();
/* colse */
closegraph();

return 0;
}
就能在圈圈里打印出"9"

❻ 图的遍历和生成树求解实现 (c语言版)

这是树的遍历：我以前做的··
#include<stdio.h>#include<malloc.h>
#define NULL 0

typedef struct node{
char data;
int ltag,rtag;
struct node * lch,* rch;
}node;

node * jianli(node * p){
int x;
scanf("%d",&x);
if(x==0)
p=NULL;
else
{
p=(node *)malloc(sizeof(node));
p->data=x;
printf("输入%d的左孩子\n",p->data);
p->lch= jianli(p->lch);
printf("输入%d的右孩子\n",p->data);
p->rch =jianli(p->lch);
}
return p;
}

void bianli(node * p){
if(p==NULL);
else
{
printf("%d",p->data );
bianli(p->lch );
bianli(p->rch );
}
}

void main(){
node * T=NULL;

printf("输入树根\n");
T=jianli(T);
bianli(T);

}

❼ c语言最小生成树

我前段时间写了一个。
你自己改改吧。

#include <stdio.h>
#include <math.h>

struct point
{
double x,y;
};

struct distence
{
double _distence;
bool islink;
};

static double CaculateDistence(point x,point y)
{
return sqrt(pow((x.x-y.x),2.0)+pow((x.y-y.y),2.0));
}

static bool isInGroup(int *group,int value)
{
for(int i=0;i<10;++i)
{
if(value==group[i]){return true;}
}
return false;
}

int main()
{
/* 初始化各个点的值 */
point _point[10]={{2.4169,8.2119},{4.0391,0.1540},{0.9645,0.4302},{1.3197,1.6899},{9.4205,6.4912},
{9.5613,7.3172},{5.7521,6.4775},{0.5978,4.5092},{2.3478,5.4701},{3.5316,2.9632}};
/* 初始化距离数组 */
distence _distence[10][10]={0.0,0};
////////////////////////////////////////////////////////////////

/* 计算距离 */
int i,j;
for (i=0;i<10;++i)
{
for(j=0;j<10;++j)
{
if(i==j)_distence[i][j]._distence=0;
else _distence[i][j]._distence=CaculateDistence(_point[i],_point[j]);
}
}
////////////////////////////////////////////////////////////////////

int pointgroup[10]={0};
int size=1;
pointgroup[0]=0;

///////////////////////////////////////////////////////////////
/* 计算最小生成树 */
for(;size<10;)
{
double dismin=32454.0;
int tmpx=0,tmpy=0;
for(i=0;i<size;++i)
{
for(j=0;j<10;++j)
{
if(_distence[pointgroup[i]][j].islink)continue;
else if(pointgroup[i]==j)continue;
else if(_distence[pointgroup[i]][j]._distence<dismin &&
!isInGroup(pointgroup,j)){
dismin=
_distence[pointgroup[i]][j]._distence;
tmpx=pointgroup[i];
tmpy=j;
}
else continue;
}
}

_distence[tmpx][tmpy].islink=true;
_distence[tmpy][tmpx].islink=true;
pointgroup[size]=tmpy;
++size;
}

//////////////////////打印最小生成树//////////////////////////
for(i=0;i<10;++i)
{
for(int j=0;j<10;++j)
{
if(_distence[i][j].islink)printf("%d ------ %d\n",i,j);
}
}

return 0;
}

❽ 用C语言实现…设计一个通用的最小生成树求解程序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct road
{
int st;
int ed;
int w;
};
road all[900];
int A[30];
int cmp(const void *a,const void *b)
{
return (*(road *)a).w - (*(road *)b).w;
}
int find(int x)
{
if (x != A[x])
A[x] = find(A[x]);
return A[x];
}
int main()
{
int i,j,k,q,p,m,n,sum;
char s,e;
while (scanf("%d",&n) != EOF)
{
if (n == 0) break;
memset(A,0,sizeof(int));
for (i = 1;i <= n;i++)
A[i] = i;
m = 0;
for (i = 1;i < n;i++)
{
scanf(" %c%d",&s,&p);
while (p--)
{
scanf(" %c%d",&e,&q);
all[m].st = s - 'A';
all[m].ed = e - 'A';
all[m].w = q;
m++;
}
}
qsort(all,m,sizeof(all[0]),cmp);
k = 0;sum = 0;
while (k < m)
{
all[k].st = find(all[k].st);
all[k].ed = find(all[k].ed);
if (all[k].st != all[k].ed)
{
sum += all[k].w;
A[all[k].st] = all[k].ed;
}
k++;
}
printf("%d\n",sum);
}
system("pause");
return 0;
}
这是杭电上的jungle roads 的代码，，就用的是最小生成树，，你看看吧。。。

❾ 求c语言数据结构二叉树的建树，前序遍历，输出树的代码，能用采纳。

#include
#include
#define
MAXSIZE
100
//二叉树中最多的结点数
typedef
char
TElemType;
typedef
struct
BiTNode
{
TElemType
data;
struct
BiTNode
*lchild,*rchild;
}BiTNode,*BiTree;
//定义函数指针
typedef
void(*
Visit)(BiTree);
//二叉树的初始化
void
Init_BiTree(BiTree
*T)
{
*T
=
NULL;
}
//判断二叉树是否为空,返回1
int
IsEmpty_BiTree(BiTree
*T)
{
return
*T
==
NULL;
}
//创建二叉树
void
Create_BiTree(BiTree
*T)
{
char
ch;
ch
=
getchar();
//当输入的是"#"时，认为该子树为空
if(ch
==
'#')
*T
=
NULL;
//创建树结点
else{
*T
=
(BiTree)malloc(sizeof(BiTNode));
(*T)->data
=
ch;
//生成树结点
//生成左子树
Create_BiTree(&(*T)->lchild);
//生成右子树
Create_BiTree(&(*T)->rchild);
}
}
//输出结点的值
void
Print_BiTreeNode(BiTree
T)
{
printf("%c\t",T->data);
}
//先序遍历二叉树
void
PreOrder_BiTree(BiTree
T,Visit
visit)
{
if(!IsEmpty_BiTree(&T))
{
visit(T);
PreOrder_BiTree(T->lchild,visit);
PreOrder_BiTree(T->rchild,visit);
}
}
int
main(){
BiTree
T;
//将二叉树初始为一个空的二叉树
Init_BiTree(&T);
//创建二叉树
Create_BiTree(&T);
//先序遍历
printf("\n先序遍历结果：");
PreOrder_BiTree(T,Print_BiTreeNode);
return
0;
}

❿ C语言（关于图最小生成树方法）

/*
邻接矩阵存储图
测试数据
610
126
131
145
235
253
345
356
364
462
566
*/

#include<stdio.h>
#include<limits.h>
#defineN100

intp[N],key[N],tb[N][N];

voidprim(intv,intn)
{
inti,j;
intmin;

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];
}
}

intmain()
{
intn,m;
inti,j;
intu,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("
");
}
return0;
}