c語言鄰接矩陣
❶ 數據結構-圖的鄰接矩陣表示(c語言)
#include<stdio.h>
int min(int a,int b)
{
return a>b?b:a;
}
int fun(int **a,int n,int begin,int end)
{
int m=~(1<<31),i;
if(begin==end)
return 0;
else
{
for(i=0;i<n;i++)
if(a[begin][i]!=-1&&a[begin][i]!=0)
m=min(fun(a,n,i,end),m);
return m;
}
}
int main()
{
int n,i,js=0;
char begin,end;
int a[26][26],b[26]={0};
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d,&a[i][j]");
if(i>j&&a[i][j]!=-1)
b[i]++;
}
getchar();
scanf("%c %c",&begin,&end);
for(i=0;i<n;i++)
s=s+b[i];
printf("%d\n",s);
for(i=0;i<n;i++)
printf("%d\n",b[i]);
fun(a,n,begin-'A',end-'A');
return 0;
}
❷ c語言編寫請簡單點。用帶權鄰接矩陣輸入一幅無向圖，使用兩種不同的演算法計算出最短路徑長度並輸出路徑。
//Floyed 實現賦權無向圖定點對間的最短路徑，時間復雜度O(n^3)
1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
#include<stdio.h>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("輸入圖的頂點數:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("輸入邊(%d,%d)的權值,若不存在輸入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向圖就刪掉這里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的權值為0
for(i=1;i<=n;i++) //初始化路徑
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中間節點，i是起點j是中點。其實就是枚舉中間節點，來求i j 的最短路徑
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //鬆弛 覆蓋原來的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//記錄i j的中間點是k
}
}
}
while(1)//也可以用遞歸的形式輸出parth
{
printf("輸入2點:");
scanf("%d%d",&x,&y);
printf("最短距離為%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}
❸ 誰給我解釋一下 C語言中圖鄰接矩陣0 和1 是咋弄的 我沒看懂
1表示想通，0表示不相通。
這里是讓你理解。無向圖有對稱性。有向圖則沒有。
以後你做題題目會直接給你矩陣不是給你圖讓你生成。
後面你會學到>1的 ，那種要求最短路的就是有權值的了。
❹ 用C語言實現 圖的鄰接表和鄰接矩陣數據結構的定義、創建；圖的深度優先遍歷、廣度優先遍歷。
/*
程序1：鄰接表的dfs,bfs
其中n是點的個數,m是邊的個數,你需要輸入m條有向邊，如果要無向只需要反過來多加一遍即可。
*/
#include<stdio.h>
#include<string.h>
#defineMAXM100000
#defineMAXN10000
intnext[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
voidinput_data()
{
scanf("%d%d",&n,&m);
inti,x,y;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}else
printf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])dfs(y);
p=next[p];
}
}
voidbfs(intk)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
intmain()
{
input_data();//讀入圖信息。
pre();//初始化
printf("圖的深度優先遍歷結果:");
inti;
for(i=1;i<=n;i++)//對整張圖進行dfs;加這個for主要是為了防止不多個子圖的情況
if(!flag[i])
dfs(i);
printf(" ------------------------------------------------------------- ");
pre();//初始化
printf("圖的廣度優先遍歷結果為:");
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf(" ----------------------end------------------------------------ ");
return0;
}
/*
程序2:鄰接矩陣
圖的廣度優先遍歷和深度優先遍歷
*/
#include<stdio.h>
#include<string.h>
#defineMAXN1000
intn,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
voidinput_data()
{
scanf("%d%d",&n,&m);
inti;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])dfs(y);
}
}
voidbfs(intt)
{
inthead=0,tail=1;
dl[1]=t;flag[t]=1;
while(head<tail)
{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
intmain()
{
input_data();
printf("圖的深度優先遍歷結果:");
pre();
inti;
for(i=1;i<=n;i++)
if(!flag[i])
dfs(i);
printf(" --------------------------------------------------------------- ");
printf("圖的廣度優先遍歷結果:");
pre();
for(i=1;i<=n;i++)
if(!flag[i])
bfs(i);
printf(" -----------------------------end-------------------------------- ");
return0;
}
❺ C語言 圖 鄰接矩陣 深度優先遍歷 DFS搜索
DFS(g,j);
DFSL(ga,p->adjvex);
除了上面兩句話，其他沒什麼問題，首先如果圖不連通，當你用從某一點遍歷的方法，本身就沒辦法遍歷整個圖
❻ 數據結構c語言版 鄰接矩陣
#include<stdio.h>
#include<stdlib.h>
typedefintVertexType;
typedefintEdgetype;
#defineMaxVertexNum30
typedefstructGraph{
VertexTypevertexs[MaxVertexNum];
Edgetypearcs[MaxVertexNum][MaxVertexNum];
intvextexNum,edgeNum;
}MGraph;
voidCreatGraph(MGraph*G)
{
inti,j,k;
scanf("%d,%d",&(G->vextexNum),&(G->edgeNum));//vertexNum是頂點數edgeNum是邊數
for(i=0;i<G->vextexNum;i++)//輸入頂點信息，建立頂點表
scanf("%c",&(G->vertexs[i]));
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->edgeNum;k++)
{
scanf("%d,%d",&i,&j);
G->arcs[i][j]=1;//若加入G->arcs[j][i]=1;則為無向圖
}
}
voidPrintGraph(MGraph*G)
{
inti,j;
for(i=0;i<G->vextexNum;i++)
{
printf("%c",G->vertexs[i]);
}
for(i=0;i<G->vextexNum;i++)
{
for(j=0;j<G->vextexNum;j++)
printf("%d",G->arcs[i][j]);
printf(" ");
}
}
voidmain()
{
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
CreatGraph(G);
PrintGraph(G);
}
❼ 用C語言實現無向圖的鄰接矩陣，求大神看有什麼問題
指針只是申明了，沒有初始化。
voidmain()
{
Mgraphg;
Mgraph*G=&g;
//...
}
或者
voidmain()
{
Mgraphg;
CreateMGraph(&g);
}
CreateMGraph()裡面的錯誤自己看吧。
PS：C語言標准要求main函數返回值為int類型。
❽ 路網中結點和邊的關系用C語言鄰接矩陣的方法怎樣表示
比如ABC三個節點{ 0 1 1
1 0 0
1 1 0 }
兩兩相連1表示鏈接，0表示沒連接。
❾ 怎麼用C語言將鄰接矩陣轉化為可達矩陣 （急）
第一步，二重循環：鄰接矩陣+單位矩陣
for i=0 to shangxian (i++)
for j=0 to shangxian (j++)
if i=j then a[i,j]=a[i,j]+1(單位矩陣對角線上的值為1)
nextj,i
第二步，所得矩陣和自身相乘（二重循環）。矩陣乘法需要些好多字，就不寫了，相信你知道，至少也應該能查到。
第三步，相乘後得到的矩陣和為相乘前的矩陣比較，（也是二重循環）。如相等則完事，否則重復執行第二、三步。
如果自動執行二、三的相乘和比較過程，則需要在外面加一層條件循環。