图的存储方式（邻接矩阵，邻接表，链式前向星）
一、邻接矩阵
一，逻辑部分：
分为两部分：V和E集合。用一个一维数组存放所有顶点数据，用一个二维数组存放顶点间的关系数据，这个二维数组称为邻接矩阵。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。
二，特点：
1),无向图的邻接矩阵一定是对称的，对于有n个顶点的无向图则只存上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+.....+(n-1)=n*(n-1)/2个单元。
2），有向图的邻接矩阵不一定对称，表示图共需n^2个空间。
三，表示法：
1),用邻接矩阵表示顶点间的相邻关系
2)，用一个顺序表来存储顶点信息
图的矩阵
设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
举例：
下图中 无向图G 5 和 有向图G 6 的邻接 矩阵分别为A1 和A 2 。
网络矩阵：
若G是网络，则邻接 矩阵 可定义为：
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
举例：下面带权图的两种邻接矩阵分别为A 3 和A 4 。
代码实现
#include <bits/stdc++.h>
using namespace std;
int s[5000][5000];
int main()
{
int n, m, u, v, q, a, b, i;
while(~scanf("%d %d",&n,&m))
{
memset(s,0,sizeof(s));
for(i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
s[u][v]=1;
}
scanf("%d",&q);
while(q--)
{
scanf("%d %d",&a,&b);
if(s[a][b]==1)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
return 0;
}二、邻接表
对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。
例如图7-4-6就是一个无向图的邻接表结构。
若是有向图，邻接表的结构是类似的，如图7-4-7，以顶点作为弧尾来存储边表容易得到每个顶点的出度，而以顶点为弧头的表容易得到顶点的入度，即逆邻接表。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如图7-4-8所示。
下面示例无向图的邻接表创建：（改编自《大话数据结构》）
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110;//最大定点数；
struct vnode
{
int vex;//顶点域，存储定点信息；
struct arcnode *firstarc;//边表头指针
};
struct arcnode
{
int adj;//存储它的邻接点；
int weight;//边的权值
struct arcnode *next;//链域，指向下一个邻接点；
};
vnode head[N];//顶点数组；
int n,m;//点的数量，边的数量
void createALg()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
head[i].vex=i;
head[i].firstarc=NULL;//初始化；
}
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
arcnode *p=new arcnode;
p->adj=v;//存储邻接点
p->weight=w;//存储权值；
p->next=head[u].firstarc;//连接表头；
head[u].firstarc=p;
arcnode *q=new arcnode;
q->adj=u;
q->weight=w;
q->next=head[v].firstarc;
head[v].firstarc=q;
}
}
int main()
{
createALg();
for(int i=1;i<=n;i++)
{
cout<<i<<"顶点的邻接点：";
arcnode *tmp=head[i].firstarc;
for(;tmp;tmp=tmp->next)
cout<<tmp->adj<<" ";
cout<<endl;
}
return 0;
}
三、链式前向星
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》
链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。
对于下面的数据，第一行5个顶点，7条边。接下来是边的起点，终点和权值。也就是边1 -> 2 权值为
我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：
对于1 2 1这条边：edge[0].to = 2; edge[0].next = -1; head[1] = 0;
对于2 3 2这条边：edge[1].to = 3; edge[1].next = -1; head[2] = 1;
对于3 4 3这条边：edge[2].to = 4; edge[2],next = -1; head[3] = 2;
对于1 3 4这条边：edge[3].to = 3; edge[3].next = 0; head[1] = 3;
对于4 1 5这条边：edge[4].to = 1; edge[4].next = -1; head[4] = 4;
对于1 5 6这条边：edge[5].to = 5; edge[5].next = 3; head[1] = 5;
对于4 5 7这条边：edge[6].to = 5; edge[6].next = 4; head[4] = 6;
第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过edge[ j ].next来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的edge[ j ].next为 -1做为终止条件。
#include <bits/stdc++.h>
#define N 1000//点数最大值
using namespace std;
struct edge
{
int to,w,next;//终点，边权，同起点的上一条边的编号
};
int n,m,cnt;//n个点，m条边
edge e[N];//边集
int head[N];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void addedge(int u,int v,int w)
{
cnt++;
e[cnt].w=w;//权值
e[cnt].to=v;//终点
e[cnt].next=head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
head[u]=cnt;//更新以u为起点上一条边的编号
}
int main()
{
cin>>n>>m;
int u,v,w;
memset(head,-1,sizeof(head));
for(int i=1; i<=m; ++i)
{
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1; i<=n; ++i)
{
cout<<i<<"顶点的邻接点有：";
for(int j=head[i]; j!=-1; j=e[j].next)
cout<<e[j].to<<" ";
cout<<endl;
}
return 0;
}