圖的幾種存儲結構：

1,、鄰接矩陣

2,、鄰接表

3、鏈式前向星

4,、C++中vector的鄰接表實現(xiàn)（補充）

（一）鄰接矩陣

鄰接矩陣是表示頂點之間相鄰關系的矩陣,。

鄰接矩陣的好處：

（1）直觀、簡單,、好理解

（2）方便檢查任意一對定點間是否存在邊

（3）方便找任一頂點的所有“鄰接點”（有邊直接相連的頂點）

（4）方便計算任一頂點的度

對于無向圖,，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點的度。

對于有向圖,，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點的出度（或入度）。

鄰接矩陣的局限性：時間復雜度O(n^2）,，空間復雜度O(n^2)

（1）浪費空間,。對于稠密圖還是很合算的。

                          但是對于稀疏圖（點很多而邊很少）有大量無效元素,。

（2）浪費時間,。要確定圖中有多少條邊,，則必須按行、按列對每個元素進行檢測,，所花費的時間代價很大,。

bb這么多，我們直接來以OJ此專題第一題為例

這題二維數(shù)組map不能用int,，會爆內存,，bool可以自己百度，簡而言之就是用于邏輯判斷,，只有true和false兩種情況,。

bool類型在存儲二值變量，或者說只有真假時,，更具優(yōu)勢,，因為只有0和1即false和true，省空間

（int型的0和1都是4字節(jié),，bool都是1字節(jié)）

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
bool map[5001][5001];
int main()
{
    int n,m;
    int u,v;
    int q;
    while(~scanf("%d %d",&n,&m))
    {
        memset(map,false,sizeof(map));
        while(m--)
        {
            scanf("%d %d",&u,&v);
            map[u][v]=true;
        }
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&u,&v);
            if(map[u][v])
            {
                printf("Yes\n");
            }else
            {
                printf("No\n");
            }
        }
    }
    return 0;
}

（二）鄰接表

圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法,。

在鄰接表中，對圖中每個頂點建立一個單鏈表,，第i個單鏈表中的節(jié)點表示依附于頂點i的邊（對有向圖是以頂點i為尾的邊）,。每個單鏈表上附設一個表頭節(jié)點。

鄰接表的特點如下：

（1）鄰接表表示不唯一,。這是因為在每個頂點對應的單鏈表中,，各邊節(jié)點的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序,。

（2）對于有n個頂點和e條邊的無向圖,，其鄰接表有n個頂點節(jié)點和2e個邊節(jié)點。顯然,，在總的邊數(shù)小于n(n-1)/2的情況下,，鄰接表比鄰接矩陣要節(jié)省空間。

（3）對于無向圖,，鄰接表的頂點i對應的第i個鏈表的邊節(jié)點數(shù)目正好是頂點i的度,。

（4）對于有向圖，鄰接表的頂點i對應的第i個鏈表的邊節(jié)點數(shù)目僅僅是頂點i的出度,。其入度為鄰接表中所有adjvex域值為i的邊節(jié)點數(shù)目,。
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    struct node *next;
};
int main()
{
    int n, u, j, i, v;
    struct node *p, *a[5050];
    while(~scanf("%d", &n))
    {
        for(i = 0; i < n; i++)
            a[i] = NULL;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                scanf("%d", &u);                       //審清題意
                if(u == 1)
                {
                    if(a[i] == NULL)
                    {
                        p = (struct node *)malloc(sizeof(struct node));
                        p -> data = j;
                        p -> next = NULL;
                        a[i] = p;
                    }
                    else
                    {
                        p = (struct node *)malloc(sizeof(struct node));
                        p -> next = a[i] -> next;
                        p -> data = j;
                        a[i] -> next = p;
                    }
                }
            }
        }
        int q;
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d%d", &u, &v);
            p = a[u];
            int flag = 0;
            while(p)
            {
                if(p -> data == v)
                {
                    flag = 1;
                    break;
                }
                p = p -> next;
            }
            if(flag)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

（三）鏈式前向星

 https://blog.csdn.net/Binary_Heap/article/details/78209086

1. 結構

這里用兩個東西：

1 結構體數(shù)組edge存邊，edge[i]表示第i條邊,

2 head[i]存以i為起點的第一條邊(在edge中的下標)

struct edge{
	int to;     //這條邊的終點 
	int w;      //權值 
        int next;   //下一條邊的存儲下標(默認0) 
}e[500010];

2.增邊

若以點u為起點的邊新增了一條,，在edge中的下標為cnt.

那么edge[++cnt].next=head[u];然后head[u]=cnt.

即每次新加的邊作為第一條邊,，最后倒序遍歷

void add(int u, int v, int w) 
{   
        e[cnt].to = v;
	e[cnt].w = w;
        e[cnt].next = head[u];//cnt為邊的計數(shù)，從1開始計 
	head[u] = cnt++;    //第一條邊為當前邊 
} 

3. 遍歷

遍歷以st為起點的邊

for(int i=head[st]; i!=0; i=edge[i].next)

 i 開始為第一條邊，每次指向下一條(以0為結束標志)  （若下標從0開始,，next應初始化-1）

鏈式前向星主要是用來優(yōu)化的,，可以用來優(yōu)化BFS，SPFA算法等等,。在做最短路的時候一直T就是因為沒有用鏈式前向星存邊導致的超時,，所以這個坑我先和你們說下。

（四）vector的鄰接表（補充）

vector是C++STL里面的一個東西,，簡單的來說就是一個可變長的數(shù)組,，你可以通過往它里面壓入數(shù)據(jù)來使它變長，

想深入了解的可以自己百度一波,，還是以這道題為例：

#include<iostream>
#include<cstdio>
#include<vector>//注意這個頭文件不能丟,，要么你就去用萬能頭
using namespace std;
#define N 500001
vector<int>MAP[N];//可以理解為二維的，每個MAP可以包含若干項,，這些項是以當前編號點為起點
int main()
{
    int n,m,u,v,i;
    while(~scanf("%d %d",&n,&m))
    {
        while(m--)
        {
            scanf("%d %d",&u,&v);
            MAP[u].push_back(v);//擴充
        }
        int q;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&u,&v);
            int len=MAP[u].size();
            int flag=0;
            for(i=0;i<len;i++)
            {
                if(MAP[u][i]==v)
                {
                    flag=1;
                }
            }
            if(flag)
            {
                cout<<"Yes"<<endl;
            }else
            {
                cout<<"No"<<endl;
            }
        }
        for(int i=0; i<N; i++)
        {
            MAP[i].clear();
        }
    }
    return 0;
}

嗯,，目前我用過的圖的幾種存儲方式就這樣啦，謝謝大家觀賞拙作,。