圖是一個好東西，能夠使用圖來模擬或解決很多生活問題，同時在各大比賽上都少不了有關(guān)于圖的問題.圖是關(guān)系與頂點與邊的，那么我們該如何來存入圖的信息呢?

（1）直接存邊

我們開一個數(shù)組，數(shù)組里每個元素是圖的一條邊。其中存的每一條邊都包含這些信息：頂點 v 與 u , 邊的權(quán)值。

這就用到結(jié)構(gòu)體數(shù)組，對于無向圖，只需要存兩個頂點 , 有向圖的話需要區(qū)分起點、終點。

// 直接存邊 
struct edge{
    int start; // 起點
    int to;    // 終點
    int cost;  // 花費(權(quán)值)
}G[MAXN];

這樣做有個缺點 , 每次想要知道兩個點之間是否有連邊（或者說一條邊是否存在），都需要遍歷整個數(shù)組進行查找.而且如果沒有進行排序的話 , 還不能使用二分查找( O(log n) ) , 只能順序查找 ( O(n) ) , 對于需要多次查找的情況 , 顯然是不合適的 . 但在使用 Kruskal 算法求最小生成樹的時候能用到這種方法。

應(yīng)用：

1. 由于直接存邊的遍歷效率低下，一般不用于遍歷圖。

2. 在 Kruskal 算法 中，由于需要將邊按邊權(quán)排序，需要直接存邊。

3. 在有的題目中，需要多次建圖（如建一遍原圖，建一遍反圖），此時既可以使用多個其它數(shù)據(jù)結(jié)構(gòu)來同時存儲多張圖，也可以將邊直接存下來，需要重新建圖時利用直接存下的邊來建圖。

（2）鄰接矩陣

鄰接矩陣的英文名是 adjacency matrix。它的形式是 bool adj[n][n] , 這里需要存 n 個節(jié)點，adj[x][y] 表示節(jié)點x與節(jié)點y 之間是否有邊，如果邊有權(quán)值的話 , 用 int adj[n][n] 直接把邊權(quán)存進去。

無向圖需要 x 與 y 有邊則需要存 adj[x][y] 與 adj[y][x] 表示有雙向?qū)?, 有向圖則 x -> y 則存 adj[x][y] 就行了 .

#include<bits/stdc++.h>

using namespace std;

int adj[MAXN][MAXN],n,m;  // n 為節(jié)點數(shù) , m 為邊數(shù)

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
        scanf("%d %d %d",&x,&y,&v);
        adj[x][y]=adj[y][x]=v;//向x,y間添加一個權(quán)值為v的邊(無向)
        //有向圖為adj[x][y]=v;
    }
    return 0;
}

它的優(yōu)點是 , 在查詢兩點間是否有邊時 , 時間復(fù)雜度為 O(1) , 但是缺點是它存邊卻是極占內(nèi)存，它的空間(內(nèi)存)復(fù)雜度是 O(n^2) . 對于一個稀疏的圖（邊相對于點數(shù)的平方比較少）來說，用鄰接矩陣來存的話，成本偏高。

如果n*m超過3×1e7，內(nèi)存就超過128MB了，所以當(dāng)看到類似的 n,m=<1e4時就不要用鄰接矩陣 , 需要考慮其他的存儲方式。

（3）鄰接表

鄰接表英文名是 adjacency list . 鄰接表是鏈狀的，它實際上是一個離散化的鄰接矩陣。edge[i] 代表第 i 號節(jié)點 , .to[] 表示到與別的節(jié)點聯(lián)通的路徑 ，.v[ ]是 i 到 edge[i].to[j] 號節(jié)點的權(quán)值， .len 用來標(biāo)記一共有幾個聯(lián)通 i 號節(jié)點的邊 (也稱節(jié)點i的出度)

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int to[1010];  //存儲與當(dāng)前節(jié)點相接的節(jié)點
    int v[1010];   //兩節(jié)點間的邊的權(quán)值
    int olen;      //出度
    //int ilen;      //入度 
}edge[1010];
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,v1;
        scanf("%d %d %d",&x,&y,&v1);
        edge[x].len++;edge[y].len++;
        edge[x].to[edge[x].len]=y;edge[y].to[edge[x].len]=x;
        edge[x].v[edge[x].len]=edge[y].to[edge[x].len]=v1;//向x,y間添加一個權(quán)值為v的邊(無向)
        /*有向圖為
        edge[x].len++;
        edge[x].to[edge[x].len]=y;
        edge[x].v[edge[x].len]=v1;
        */
    }
    return 0;
}

應(yīng)用：

1. 存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點數(shù)較少，可以使用鄰接矩陣）。

2. 尤其適用于需要對一個點的所有出邊進行排序的場合。

（4）鏈?zhǔn)角跋蛐?/p>

本質(zhì)上是用鏈表實現(xiàn)的鄰接表，核心代碼如下：

// C++ Version
// head[u] 和 cnt 的初始值都為 -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  // 當(dāng)前邊的后繼
  head[u] = cnt;         // 起點 u 的第一條邊
  to[cnt] = v;           // 當(dāng)前邊的終點
}

// 遍歷 u 的出邊
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
  int v = to[i];
}