Ⅰ 用c语言编无向图的存储实验..真心求指导求程序！！！急！！！
#include<stdio.h>
#include<stdlib.h>
#defineCNT5
structElemType
{
charvalue;
structNode*first;//链表头
};
structNode//存放邻接表
{
charvalue;
structNode*next;
};
intmain()
{
boolarr[CNT][CNT];
ElemTypeelems[CNT];
printf("inputtheelems:");
for(inti=0;i!=CNT;++i)
{
scanf("%c",&(elems[i].value));
elems[i].first=NULL;
}
intb=0;
printf("inputthearray:");
for(inti=0;i!=CNT;++i)
{
for(intj=i+1;j!=CNT;++j)
{
scanf("%d",&b);
arr[i][j]=arr[j][i]=(bool)b;
}
arr[i][i]=0;
}
for(inti=0;i!=CNT;++i)
{
for(intj=i+1;j!=CNT;++j)
{
if(arr[i][j])
{
printf("(%c,%c)",elems[i].value,elems[j].value);
}
}
}
printf(" ");
Node*temp;
for(inti=0;i!=CNT;++i)
{
for(intj=0;j!=CNT;++j)
{
//如果有无向边存在的话
if(arr[i][j])
{
if(elems[i].first==NULL)
{
elems[i].first=(Node*)malloc(sizeof(Node));
elems[i].first->value=elems[j].value;
elems[i].first->next=NULL;
continue;
}
//创建一个新的NODE节点，并给它赋值
if((temp=(Node*)malloc(sizeof(Node)))==NULL)
{
printf("分配失败！");
exit(0);
}
temp->value=elems[j].value;
temp->next=elems[i].first;
elems[i].first=temp;
}
}
}
for(inti=0;i!=CNT;++i)
{
printf("%c:",elems[i].value);
Node*pNode=elems[i].first;
while(pNode!=NULL)
{
printf("%c",pNode->value);
pNode=pNode->next;
}
printf(" ");
}
return0;
}
代码比较简单，如果楼主有哪里不懂，随时HI我
Ⅱ 无向图采用邻接表存储结构,编写算法输出图中各连通分量的节点序列
//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.仅适用于邻接表结构
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表结点
LinkQueue Q;//链队列类型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值为未被访问
}
InitQueue(&Q);//初始化辅助队列Q
for (v=0; v<G.vexnum; ++v)//如果是连通图，只v=0就遍历全图
{
if (! visited[v])//v尚未被访问
{
visited[v] = TRUE;//设v为已被访问
Visit(G.vertices[v].data);//访问v
EnQueue(&Q,v);//v入队
while (! QueueEmpty(Q))//队列不空
{
DeQueue(&Q,&u);//队头元素出队并置为u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的邻接顶点
{
if (! visited[p->data.adjvex])//u的邻接顶点尚未被访问
{
visited[p->data.adjvex] = TRUE;//该邻接顶点设为已被访问
Visit(G.vertices[p->data.adjvex].data);//访问该邻接顶点
EnQueue(&Q,p->data.adjvex);//入队该邻接顶点序号
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
Ⅲ 数据结构，求无向图用邻接矩阵和邻接表的存储空间大小，怎么算
邻接表所需的存储空间为e（边数），但不适合查询两点间是否存在路径
邻接矩阵所需的存储空间为你n^2，适合查询两点间是否存在路径
对于第二问，邻接表所需的存储空间为9900，邻接矩阵所需的存储空间为你n^2=10000，差不多，所以选性能更优的邻接矩阵
实际上像（2）这种稠密图（其实是个满图）一般适合邻接矩阵
Ⅳ 无向图的邻接表存储方式和深度优先遍历的方法（代码）
type
node=record
y:longint;
flag:boolean;
next:longint;
p:-1..1;
end;
var
n,m,i,j,x,y:longint;
map:array [0..40000] of node;
a:array [0..40000] of longint;
procere dfs(i:longint);
var
j:longint;
begin
j:=a[i];
while j>-1 do begin
if map[j].flag then begin
map[j].flag:=false;
map[j xor 1].flag:=false;
if map[j].p>-1 then begin
map[j].p:=0;
writeln(i);
dfs(map[j].y);
map[j].p:=1;
end;
end;
j:=map[j].next;
end;
end;
begin
readln(n,m);
for i:=1 to n do a[i]:=-1;
for j:=1 to m do begin
readln(x,y);
map[2*j-2].y:=y;
map[2*j-2].next:=a[x];
map[2*j-2].flag:=true;
a[x]:=2*j-2;
map[2*j-1].y:=x;
map[2*j-1].next:=a[y];
map[2*j-1].flag:=true;
a[y]:=2*j-1;
end;
map[a[1]].p:=0;
dfs(1);
map[a[1]].p:=1;
end.
Ⅳ 无向图G.，有n个顶点，m条边，如何采用邻接表存储该图主要是想知道算法~用c语言
无向图就是不分方向的图
连接表的横列有N项，纵列也是N项
形成的N*N项每项都被称为边结点
每项都有纵横两个坐标，例如点（N,N-1），表示的就是从第N点向第N-1点有无路径。
由于有E条边，自然有E条路径，但是由于无向，=双向，所以要乘以二
Ⅵ 计算机C语言题目，已知赋权无向图，画邻接矩阵和邻接表。还有最小支撑树
所要求赋权无向图的邻接矩阵和邻接表，还有最小支撑树见下图：
Ⅶ 请教编程大神数据结构题目：c语言使用邻接链表存储结构实现用户输入的无向图的连通性判断
#include<stdio.h>
#include<stdlib.h>
#defineMAX_VERTEX_NUM100
typedefstructArcNode{
intadjvex;//该边的另一个顶点的位置
structArcNode*nextarc;//指向下一条边
}ArcNode;
typedefstructVNode{
intdata;//顶点的值
ArcNode*firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;//顶点数组
intvexnum,arcnum;
}ALGraph;
intLocateVex(ALGraphG,intv){//定位函数
for(inti=0;i<G.vexnum;i++){
if(v==G.vertices[i].data)returni;
}
}
voidCreateUDG(ALGraph&G){
ArcNode*p,*q;
inti,j,k,v1,v2;
printf("分别输入顶点个数和边的数目： ");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("分别输入各个顶点值： ");
for(i=0;i<G.vexnum;i++){
scanf("%d",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;//初始化
}
printf("分别输入各条边的两个顶点： ");
for(k=0;k<G.arcnum;k++){
scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1);j=LocateVex(G,v2);//定位
p=(ArcNode*)malloc(sizeof(ArcNode));//申请一个结点
p->adjvex=j;p->nextarc=NULL;//赋值
p->nextarc=G.vertices[i].firstarc;//连接结点
G.vertices[i].firstarc=p;//连接结点
q=(ArcNode*)malloc(sizeof(ArcNode));
q->adjvex=i;q->nextarc=NULL;
q->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=q;
}
}
voidPrintUDG(ALGraphG){//输出邻接表
inti,j;
for(i=0;i<G.vexnum;i++){
printf("%d:",i);
ArcNode*p;
p=G.vertices[i].firstarc;
while(p!=NULL){
printf("->%d",p->adjvex);
p=p->nextarc;
}
printf(" ");
}
}
intmain(){
ALGraphG;
CreateUDG(G);
PrintUDG(G);
return0;
}
Ⅷ 无权无向图，用邻接表存储，求各个顶点之间的最小边数，求c++或c代码。十分感谢啊
最小生成树：
并查集方法：
#include<bits/stdc++.h>
usingnamespacestd;
intn,m,ans=0,tot=0,f[10005];
structedge{
intto,from,v;
}e[100005];
boolcmp(edgea,edgeb)
{
returna.v<b.v;
}
intfind(intx)
{
if(f[x]==x)
returnf[x];
else
returnf[x]=find(f[x]);
}
intmain()
{
cin>>n>>m;
for(inti=1;i<=n;++i)
f[i]=i;
for(inti=1;i<=m;++i)
cin>>e[i].from>>e[i].to>>e[i].v;
sort(e+1,e+m+1,cmp);
for(inti=1;i<=m;++i)
{
intx=e[i].from,y=e[i].to;
f[x]=find(x);
f[y]=find(y);
if(f[x]!=f[y])
{
f[find(y)]=f[x];
ans+=e[i].v;
tot++;
}
}
if(tot!=(n-1))
{
cout<<"-1"<<endl;
return0;
}
cout<<ans<<endl;
return0;
}
Pirm算法：
#include<bits/stdc++.h>
usingnamespacestd;
intn,m,ans=0,tot=0,head[100005]={0},cnt=0;
boolvis[100005]={0};
structedge{
intto,next,v;
}e[200005];
voidinsert(inta,intb,intc)
{
e[++tot].next=head[a];
e[tot].to=b;
e[tot].v=c;
head[a]=tot;
}
structcmp{
booloperator()(edgea,edgeb)
{
returna.v>b.v;
}
};
priority_queue<edge,vector<edge>,cmp>q;
intmain()
{
cin>>n>>m;
for(inti=1;i<=m;++i)
{
inta,b,c;
cin>>a>>b>>c;
insert(a,b,c);
insert(b,a,c);
}
intx=1;
while(1)
{
vis[x]=true;
for(inti=head[x];i;i=e[i].next)
{
inty=e[i].to;
if(vis[y]==false)
q.push(e[i]);
}
if(!q.empty())
{
edgez=q.top();
q.pop();
while(vis[z.to]==true&&!q.empty())
{
z=q.top();
q.pop();
}
if(vis[z.to]==true)
break;
x=z.to;
ans+=z.v;
cnt++;
}
else
break;
}
if(cnt<(n-1))
{
cout<<"-1"<<endl;
return0;
}
cout<<ans<<endl;
return0;
}