图的邻接矩阵存储法和邻接表存储

一、邻接矩阵存储法 

以两图为例：（《啊哈！算法》）

 图一为二维数组，图二为要存储的图。

图一的二维数组中，第i行第j列表示的是点i到点j是否有边。

1表示有边，∞表示没有边。0表示（i=j）时自己到自己（沿主对角线对称）。

 示例代码

const int N=110;
int e[N][N];
int a,b;//为可连顶点的两端顶点
int INF=0x3f3f3f3f;
//其下在main函数中
//初始化二维矩阵
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        if(i==j)e[i][j]=0;
        else
        e[i][j]=INF;
    }
}
//读入顶点之间的边
for(int i=1;i<=m;i++)
{
    cin>>a>>b;
    e[a][b]=1;
    e[b][a]=1;//因为是无向图，且边权为1
}

二、图的邻接表存储法

用了数组链表，顺序存储表头，链式存储连接 

struct GraphNode
{
    int label;//图的顶点
    vector<GraphNode*>neighbors;//连接的节点指针
}
int main()
{
    GraphNode G[4];
    for(int i=0;i<4;i++)
    {
        G[i].label=i;
    }
    G[0].neighbors.push_back(&G[2]);
    G[0].neighbors.push_back(&G[3]);//存储0结点到2、3的边，以下同理
    …………
}

三、存储法的选用：（n为点的数量，m为边的数量）

1、稀疏图：m<<n^2，选用邻接表。

2、稠密图：m接近n^2，选用邻接矩阵。