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