邻接矩阵：是直接利用一个二维数组对边的关系进行存储，矩阵的第i行第j列的值 表示 i -> j 这条边的权值；特殊的，如果不存在这条边，用一个特殊标记来表示；如果i == j，则权值为0。它的优点是实现非常简单，而且很容易理解；缺点也很明显，如果这个图是一个非常稀疏的图，图中边很少，但是点很多，就会造成非常大的内存浪费，点数过大的时候根本就无法存储。
邻接表：是图中常用的存储结构之一，每个顶点都有一个链表，这个链表的数据表示和当前顶点直接相邻的顶点（如果边有权值，还需要保存边权信息）。邻接表的优点是对于稀疏图不会有数据浪费，缺点就是实现相对麻烦，需要自己实现链表，动态分配内存.（当然也可以使用vector来实现邻接表的存储，不过时间效率会下降）
前向星：是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相等的边就能够在数组中进行连续访问了。它的优点是实现简单，容易理解，缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差，只适合离线算法。
链式前向星：链式前向星和邻接表类似，也是链式结构和线性结构的结合，每个结点i都有一个链表，链表的所有数据是从i出发的所有边的集合（对比邻接表存的是顶点集合）。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。具体实现看下面的代码
/* 采用链式前向星存储边 */ #include<iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int MAXN=30005; struct Edge { int to,cost;// edge[i].to表示编号为i的边所连接下个点 ，edge[i].cost表示编号为i的边 的权值 int next;//edge[i].next表示与编号为i的边同起点的上一条边的编号 }edge[MAXN];//存放边 int tol; int head[MAXN];//head[i]存储当前以i点为起点的边的编号 void addedge(int u,int v,int w)//添加边 { edge[tol].to=v; edge[tol].cost=w; edge[tol].next=head[u]; head[u]=tol++; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF)//点数n，边数m { tol=0; memset(head,-1,sizeof(head)); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c);//a到b花费c addedge(a,b,c); } for(int i=1;i<=n;i++)//输出与节点i相连的边 { for(int j=head[i];j!=-1;j=edge[j].next) { printf("%d->%d cost:%d\n",i,edge[j].to,edge[j].cost); } } } return 0; }vector来实现邻接表的存储
/* 采用vector存储边 */ #include<iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int MAXN=30005; struct Edge { int to,cost; }; vector<Edge> G[MAXN];//G[i]代表从i出发的边，vector里存的是边 int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF)//点数n，边数m { Edge e; int from; while(m--) { scanf("%d%d%d",&from,&e.to,&e.cost);//a到b花费c G[from].push_back(e); } for(int i=1;i<=n;i++)//输出与节点i相连的边 { for(int j=0;j<G[i].size();j++) { Edge e=G[i][j]; printf("%d->%d cost:%d\n",i,e.to,e.cost); } } } return 0; }