1.邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。

例如：用 $a_{ij}$ 不为0时表示 $i$ 到 $j$ 有一条边（也可以用 $a_{ij}$ 不为0时表示 $i$ 到 $j$ 有一条长度为 $a_{ij}$ 的边）

实现：

int x,y,z;//无向图带权加边 
scanf("%d%d%d",&x,&y,&z);
mp[x][y]=z;
mp[y][x]=z;

int x,y,z;//有向图带权加边 
scanf("%d%d%d",&x,&y,&z);
mp[x][y]=z;

int x,y;//无向图无权加边 
scanf("%d%d%d",&x,&y);
mp[x][y]=1;
mp[y][x]=1;

int x,y;//有向图无权加边 
scanf("%d%d%d",&x,&y);
mp[x][y]=1;

邻接矩阵的好处：

1.直观、简单、好理解

2.方便检查任意一对定点间是否存在边

3.方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

4.方便计算任一顶点的度

对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

邻接矩阵的缺点：

1.浪费空间（特别是在稀疏图中，有大量空余空间）

2.浪费时间（要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。）

所以我们需要下面这两个：

2.邻接表

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

邻接表的特点如下：

1.邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

2.对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。

3.对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。

4.对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。

3.链式前向星

1. 结构

这里用两个东西：

1 结构体数组edge存边，edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)

struct EDGE{
	int next;   //下一条边的存储下标(默认0) 
	int to;     //这条边的终点 
	int w;      //权值 
}edge[500010];

2.增边

若以点i为起点的边新增了一条，在edge中的下标为j.

那么edge[j].next=head[i];然后head[i]=j.

即每次新加的边作为第一条边，最后倒序遍历


void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	//cnt为边的计数，从1开始计 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
}

3. 遍历

遍历以st为起点的边

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

i开始为第一条边，每次指向下一条(以0为结束标志) （若下标从0开始，next应初始化-1）

图的几种存储方式