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