鄰接矩陣和鄰接表的使用

鄰接矩陣

為了遍歷一個圖，我們使用了鄰接矩陣，及用$a_{i,j}$表示由a到b的邊權
注：若這兩個點不相連或$i=j$，那么這個值就會設定為一個非正常的值，以便遍歷時特判不走這條邊
使用：

scanf("%d%d%d",&x,&y,&z);//x指向y，邊權為z a[i][j]=z;b[1] = 0; for(int i=1;i<=n;++i)//總共n個點if (a[1][i]) b[i]=b[1]+a[1][i];//到點i

鄰接表

使用鄰接矩陣會有許多不足之處，如空間時間浪費太多
所以我們又使用了另一種存儲方法——鄰接表
我們定義如下

我們定義head_A為A讀入的最后一條邊（為了便于分辨，把數字的編號寫成大寫英文字母）
$a_k.to$為$k$這條邊連向的點
$a_k.l$為$k$這條邊的邊權
$a_k.next$為和$k$源頭相等的上一條邊
使用：

scanf("%d%d%d",&x,&y,&z);//讀入 a[++tot].to=y;//tot是這條邊的編號，指向y a[tot].l=z;//邊長為z a[tot].next=head[x];//它的上一條邊是加載它之前的最后一條邊 head[x]=tot//現在的最后一條邊是它b[1] = 0; for(int i=head[1];i;i=a[i].next)//從1的最后一條邊開始遍歷，每一次遍歷上一條邊，直到沒有上一條邊，及遍歷完 {x=1;//源頭y=a[i].to;//指向哪z=a[i].l;//邊權 }

總結

以上是生活随笔為你收集整理的邻接矩阵和邻接表的使用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。