Ⅰ matlab中如何存储树希望提供代码，万分感谢，本人编程涉及到剪枝
MATLAB里没有指针。但是考虑到树只是图的一种特例，LZ可以考虑用图的存储策略，用邻接矩阵保存树是不需要指针的，而且MATLAB对矩阵运算比较效率。就是浪费点空间而已。
Ⅱ 怎样将一棵二叉树的存储结构转化为一个无向图的存储结构，谁能说说编程思想啊
图的存储机构一般用邻接矩阵或邻接表,二叉树一般是链表结构,就是把链表变成临近矩阵了,用中序形势对链表节点进行编号和访问并做为临近矩阵的顺序,用中序访问,对当前节点和后继节点判断,然后置对应的矩阵为1,(a[当前],[后继]=1 ,a[后继],[当前]=1 ) ,中序访问完就可以了
Ⅲ 数据结构 ~~~~~最小生成树问题
/* 用邻接矩阵表示的图的prim算法的源程序*/
#include<stdio.h>
#define MAXVEX 6
typedef char VexType;
typedef float AdjType;
typedef struct {
int n;
/* 图的顶点个数 */
/*VexType vexs[MAXVEX];
顶点信息 */
AdjType arcs[MAXVEX][MAXVEX];
/* 边信息 */
} GraphMatrix;
typedef struct{
int start_vex, stop_vex;
/* 边的起点和终点 */
AdjType weight;
/* 边的权 */
} Edge;
Edge mst[5];
#define MAX 1e+8
void prim(GraphMatrix * pgraph, Edge mst[]) {
int i, j, min, vx, vy;
float weight, minweight; Edge edge;
for (i = 0; i < pgraph->n-1; i++) {
mst[i].start_vex = 0;
mst[i].stop_vex = i+1;
mst[i].weight = pgraph->arcs[0][i+1];
}
for (i = 0; i < pgraph->n-1; i++) {
/* 共n-1条边 */
minweight = MAX; min = i;
for (j = i; j < pgraph->n-1; j++)/* 从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 */
if(mst[j].weight < minweight) {
minweight = mst[j].weight;
min = j;
}
/* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */
edge = mst[min];
mst[min] = mst[i];
mst[i] = edge;
vx = mst[i].stop_vex;
/* vx为刚加入最小生成树的顶点的下标 */
for(j = i+1; j < pgraph->n-1; j++) { /* 调整mst[i+1]到mst[n-1] */
vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
if (weight < mst[j].weight) {
mst[j].weight = weight;
mst[j].start_vex = vx;
}
}
}
}
GraphMatrix graph = {
6,
{{0,10,MAX,MAX,19,21},
{10,0,5,6,MAX,11},
{MAX,5,0,6,MAX,MAX},
{MAX,6,6,0,18,14},
{19,MAX,MAX,18,0,33},
{21,11,MAX,14,33,0}
}
};
int main(){
int i;
prim(&graph,mst);
for (i = 0; i < graph.n-1; i++)
printf("(%d %d %.0f)\
", mst[i].start_vex,
mst[i].stop_vex, mst[i].weight);
return 0;
}
Ⅳ 编程实现以邻接表或邻接矩阵为存储结构，图的广度和深度优先搜索
/*******************************************
图的遍历演示
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*******************************************/
#include<iostream>
# include <string.h>
# include <malloc.h>
# include <conio.h>
using namespace std;
int visited[30];
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode //弧
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//表头
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct//图
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph &G)
{
int k,i,v1;
cout<<endl<<"请输入结点个数: ";
cin>>G.vexnum;
cout<<"请输入弧的个数: ";
cin>>G.arcnum;
for(i=1;i<=G.vexnum;i++)//初使化表头
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=1;k<=G.vexnum;k++) //输入边
{
int v2;
cout<<"请输入与结点"<<k<<"相邻的边数:";
cin>>v2;
cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
cin>>v1;
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p->adjvex=v1;
p->nextarc=NULL;
G.vertices[k].firstarc=p;
for(int i=1;i<v2;i++)
{
int m;
cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
cin>>m;
ArcNode *q;
q=(ArcNode *)malloc(sizeof(ArcNode));//动态指针
if(!q) exit(-1);
q->adjvex=m; //顶点给P
q->nextarc=NULL;
p->nextarc=q;
p=q;
//free(q);
}
//free(p);
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
ArcNode *x;
x=(ArcNode*)malloc(sizeof(ArcNode));
if(!x) exit(-1);
x=G.vertices[v].firstarc;
int w;
for (;x;x=x->nextarc)
{ w=x->adjvex;
if(visited[w]==0)
DFS(G,w);
}
}
void DFSB (ALGraph G,int v)//深度搜索的边集
{
visited[v]=1;
ArcNode *y;
y=(ArcNode*)malloc(sizeof(ArcNode));
if(!y) exit(-1);
y=G.vertices[v].firstarc;
int u=G.vertices[v].data;
int w;
for(;y;y=y->nextarc)
{ w=y->adjvex;
if(visited[w]==0)
{
cout<<u<<"--->"<<w<<endl;
DFSB(G,w);
}
}
}
typedef struct QNode
{
int data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue (LinkQueue &Q)//建立一个空队列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(-1);
Q.front->next=NULL;
}
void EnQueue (LinkQueue &Q,int e)//进队
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
//free(p);
}
int DeQueue (LinkQueue &Q,int &e)//出队
{
if(Q.front==Q.rear)
return -1;
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
int QueueEmpty (LinkQueue Q)//判断队列是否为空
{
if(Q.front==Q.rear)
return 1;
return 0;
}
void BFS(ALGraph G,int v)//广度搜索
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *z;
z=(ArcNode*)malloc(sizeof(ArcNode));
if(!z) exit(-1);
z=G.vertices[u].firstarc;
/*
for(int w=z->adjvex;w>=0;w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}*/
int w;
for(;z;z=z->nextarc)
{ w=z->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}
}
}
}
void BFSB (ALGraph G,int v)//广度搜索的边集
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *r;
r=(ArcNode*)malloc(sizeof(ArcNode));
if(!r) exit(-1);
r=G.vertices[u].firstarc;
int w;
for(;r!=NULL;r=r->nextarc)
{ w=r->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<u<<"--->"<<w<<endl;
EnQueue(Q,w);
}
}
}
}
}
int main()
{
int i;
ALGraph G;
CreateDG(G);
int x;
cout<<"请输入结点数:";
cin>>x;
cout<<"邻接表为："<<endl;
for(int j=1;j<=x;j++)
{
cout<<G.vertices[j].data<<" ";
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p=G.vertices[j].firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
cout<<"请输入第一个要访问的结点序号："<<endl;
int n;
cin>>n;
for( i=0;i<30;i++)
visited[i]=0;
cout<<"广度搜索："<<endl;
BFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"边集："<<endl;
BFSB(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<"深度搜索："<<endl;
DFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"边集："<<endl;
DFSB(G,n);
//system("pause");
return 0;
}
前几天上机刚好做了这个,个人感觉很完美,尽管老师说用的是邻接表而不是多重表,太简单,但还不错,界面输入过程比较繁琐,要严格按照提示来输入,是无向图,等级太低,没办法把执行结果粘出来,应该能看懂吧
Ⅳ 有些图论题数据太大无法用邻接矩阵，所以请教教我怎么用数组模拟邻接表建图（带权）。（C/C++代码）
暂且与例题一起的
路径(netbar.pas)
绵阳中学以人数众多而闻名。三个年级共有 10000 多人，学生多了附近的网吧也多。
Mzoiers 都热衷于 Dota，可学校的机子配置相当差(评测服务器除外)，根本不能玩
Dota，那就只有去网吧。星期天到星期五都是晚上 10：20 才下晚自习，几乎没时间玩。
然而星期六下午放假是绝好的时间，但是学校人多啊，一放学去网吧的人就开始狂奔，竞争
之激烈，抢到机子的难度非常之大。往往在我们到达网吧之前都坐满了。
学校到网吧的路是错综复杂的，以致于到一个自己想去的网吧都有非常多的路线可以选
择，而路线的长度又不相同，这样就决定了要花费的时间，因此想要尽快到达，选择一条最
佳的线路是很有必要的。
【问题描述】
为了简化问题，我们把学校与周边的网吧看做图中的顶点，学校与网吧，网吧与网吧之
间的路线看做边，每个边都有一个权，表示我们走完这条路的时间，由于放学人流量大，如
果反向走会有危险，因此这是一个有向图。
我的学校在 S 点，想要去的网吧在 T 点。你的任务就是选择一条最佳路线，使得从
学校到目的地网吧的时间最短，你只需要输出最短到达时间即可。
【输入文件】
netbar.in 中共有 M+2 行数据
第一行两个整数 N，M，表示点数和边数。
然后 M 行每行 3 个正整数(u，v，t)，表示有一条可由 u 到 v 耗时为 t 的边。
最后一行两个正整数 S、T。
【输出文件】
netbar.out 中，只有一行，一个整数表示最短时间。如果 S、T 之间不存在通路则输
出“No Solution!”(双引号不输出，“!”为西文标点)。
【输入样例】
4 4
1 2 3
2 4 10
1 3 5
3 4 5
1 4
【输出样例】
10
【数据规模】
对于 30％的数据保证有 1<N<=1000，1<=M<=1000；
对于全部的数据保证有 1<N<=10000，1<=M<=100000。
解题思路：
题目可以抽象为输入n个顶点，e条边的有向图，再读入源点S和目标点T，求S到T的最短路。输入规模：1<N<=10000，1<=M<=100000。
最短路有三种方法：floyd,dijsktra,spfa。如果用floyd,时间性能为O(n3) , 只能通过1000以内的数据；用dijkstra，时间性能为O(n2) ，只能通过10000以内的数据，且用邻接矩阵存储时，10000*10000*4个字节，总内存达到380多MB，会超内存。用spfa算法，时间性能为O(kM)，能通过所有测试数据，k的值平均为2，表示顶点入队的平均次数。此时，可以采用数组模拟链表的存边方法，开一个边的一维数组，把所有边存储起来。如对于如下输入数据：
5 7
1 2 2
1 5 8
1 3 1
1 4 3
2 5 3
3 5 1
4 3 2
1 5
下面这个图的数组模拟链表的形式存储边，把从某个顶点出来的所有边通过链表的形式，链接起来，就象存储普通有序树一样，右儿子挂到左儿子下面。这里的操作原理是，处理某个顶点出来的边时，下一条边挂到前一条边，如下图，第一条边指向0，后面的边都指向前一条边，所以，在处理某个顶点相连的边的松驰操作时，可以很方便的处理以该顶点连出去的边，当指向0时，则以该 顶点出去的松驰操作完成。
program netbar;
var
list,dis:array [0..10000] of longint; //list存储当前边的指针,dis存储各点到源点的最短路
next,toit,cost,q:array [0..100000] of longint;//next存储当前边指向前一条边的位置，toit表示当前边的出点，cost表示当前边的边权
n,m,i,a,b,c,s,e,tot:longint;
flag:array [0..10000] of boolean;
procere add(a,b,c:longint);//数组模拟链表的添边的方法
begin
inc(tot); //边的数目
toit[tot]:=b; //当前边的出点顶点标号
cost[tot]:=c; //当前边的权值
next[tot]:=list[a]; //当前边指向前一条边的位置，如果当前边是顶点a的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0。
list[a]:=tot; //从入点a引出的边的编号存储给lsit[a]
end;
procere SPFA;
var
i,head,tail,v,k:longint;
begin
fillchar(flag,sizeof(flag),true);
for i:=1 to n do dis[i]:=maxlongint;
head:=1; tail:=1; q[1]:=s; dis[s]:=0; flag[s]:=false;//源点s入队
repeat
v:=q[head]; k:=list[v]; //队列头出队，k存储当前v顶点的边的编号
while k<>0 do //处理v的所有边，直至边指向0，即第一条边也处理了
begin
if dis[v]+cost[k]<dis[toit[k]] then //松驰操作
begin
dis[toit[k]]:=dis[v]+cost[k]; //松驰成功
if flag[toit[k]] then //入队
begin
inc(tail); q[tail]:=toit[k]; flag[toit[k]]:=false;
end;
end;
k:=next[k]; //处理顶点v的前一条边
end;
flag[v]:=true;
inc(head);
until head>tail;
end;
begin
assign(input,'netbar.in'); reset(input);
assign(output,'netbar.out'); rewrite(output);
fillchar(list,sizeof(list),0);
fillchar(next,sizeof(next),0);
fillchar(toit,sizeof(toit),0);
fillchar(cost,sizeof(cost),0);
tot:=0;
readln(n,m);
for i:=1 to m do
begin readln(a,b,c); add(a,b,c); end;
readln(s,e);
SPFA;
if dis[e]<maxlongint then writeln(dis[e])
else writeln('No Solution!');
close(input); close(output);
end.
当N的顶点规模达到10000时，如果用邻接矩阵存储图，容易超内存，且1个亿的运算次数在1S的时限内不一定出得来。
不好意思 这边只有PASCAL 的 暂且将就吧 c语言的MS没有额……
Ⅵ 数据结构，如何根据邻接表画深度，广度优先生成树
深搜中枚举时由大到小就是这个结果。
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix ");
for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵
scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
visited[i]=TRUE; //置已访问标志
for(j=0;j<G->n;j++) //依次搜索Vi的邻接点
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//==========main=====
void main()
{
//int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf(" ");
}
(6)树可以用邻接矩阵存储扩展阅读：
图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
Ⅶ 存储图时，哪些情况用邻接矩阵方便
如果边比较少的情况下，用邻接矩阵节省存储空间。边比较多就可以选择邻接矩阵
Ⅷ 求无向连通图的生成树（用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);}