鄰接表（數組）

概要

相比于二維數組存儲，鄰接表占有更小的空間，且在周遊時具有較小的時間複雜度。      

int g[n][n];//二維數組存儲      

在保證不超限的情況下，也可以用這種方式存圖：      

struct node{
  int num[n];//該邊通向的邊的編号
  int cnt;//該邊通向的邊數量
}g[n];//邊的編号      

鄰接表存儲

看過許多篇部落格都是用指針存儲，但奈何本人不怎麼喜歡指針這東西（其實是我不會 ），是以就學習了用數組來模拟鄰接表的存儲。

首先我們需要建立一個結構體用來儲存每一條邊

struct node{
  int from;//起始點
  int to;//終點
  int next;
}g[n];//邊的編号      

關于next，後面再做解釋。

我們知道，用指針實作的鄰接表可以通過選擇的起點來找到所有與它相連的終點，進而友善周遊，而next正是用于實作這個功能。

接下來我們來看一段添加邊的代碼，在這之前，需要先開一個head數組，用于存儲對應點的頭節點的“最後”的邊。

void add(int x,int y)//1
{//2
  g[++cnt].next = head[x];//3
  g[cnt].to = y;//4
  head[x] = cnt;//5
}//6      

在上面這段代碼中，cnt代表的是邊的編号，在第三行代碼中，我們将head[x]指派給目前邊的next，意思就是将距離點x最近建立的一條邊的編号指派給next，如果是第一次建邊，那麼next就為0，結合第5行代碼：将目前邊的編号指派給head[x]（也就是将建立的這條邊作為點x最近建立的這條邊），那麼我們就能通過next周遊點了。

int x;
cin>>x;
for(int i = head[x]; i; i = head[g[i].next])
{
  cout<<g[i].to;
}