邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服但是我 们也发现，对于边数相对顶点较少的图，这种结构无疑是存在对存储空间的极大浪费。 因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方 式在图结构也适用，我们称为邻接表 (AdjacencyList) 。 基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。 每一个单链表设一个表头结点。 第 i 个单链表表示依附于顶点 Vi 的边 ( 对有向图是以顶点 Vi 为头或尾的弧 ) 。 图的邻接表存储法，又叫链式存储法。本来是要用链表实现的，但大多数情况下只要用 数组模拟即可。 l 邻接表（有向图） l 邻接表的处理方法是这样： l 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。 l 图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。 但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆 邻接表： 此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很 容易实现。 对于带权值的网图，可以在边表结点定义中再增加一个 数据域来存储权值即可：
代码实现：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int E=5;//E为最大边数 5 const int N=3;//n为最大定点数 6 struct Edge { 7 int u,v,w,next;//两顶点，权值，下一条边； 8 } edge[E]; 9 int head[N];//表头； 10 int num;//内存指针； 11 void chushi() 12 { 13 for(int i=1; i<=N; i++) 14 head[i]=-1; 15 num=0; 16 } 17 void add_edge(int b,int e,int w) 18 { 19 edge[num].u=b; 20 edge[num].v=e; 21 //edge[num].w=w; 22 edge[num].next=head[b]; 23 head[b]=num++; 24 } 25 int main() 26 { 27 int n,m,a,b,x; 28 chushi(); 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=m;i++) 31 { 32 scanf("%d %d %d",&a,&b/*,&x*/); //a、b之间有一条长度为x的边 33 add_edge(a,b,x); 34 } 35 cout<<1; 36 for(int i=head[1];i!=-1;i=edge[i].next) //遍历从点1开始的所有边 37 { 38 cout<<"-->"<<edge[i].v; 39 } 40 return 0; 41 }
转载于:https://www.cnblogs.com/sssy/p/6682747.html
相关资源：数据库课程设计(数组，邻接表)