图是一种非线性表数据结构。

图中的元素我们就叫作顶点（vertex）。
一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边（edge）。
跟顶点相连接的边的条数，叫作顶点的度（degree）。

无向图

边没有方向的图就叫作“无向图”。

有向图

边有方向的图叫作“有向图”。

有向图中，把度分为入度（In-degree）和出度（Out-degree）。

顶点的入度，表示有多少条边指向这个顶点；
顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。

带权图

带权图中，每条边都有一个权重 （weight），可以通过这个权重来表示 QQ 好友间的亲密度。

存储方法

邻接矩阵 Adjacency Matrix

邻接矩阵的底层依赖一个二维数组，

• 无向图
  如果顶点 i 与顶点 j 之间有边，我们就 将 A[i][j] 和 A[j][i] 标记为 1；
• 有向图
  如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，就将 A[i][j] 标记为 1；
  如果有一条箭头从顶点 j 指向顶点 i 的 边，就将 A[j][i] 标记为 1；
• 带权图，数组中就存储相应的权重。
  

优点： 简单、直观、获取关系时高效、运算方便
缺点： 浪费空间

首先，无向图中，如果 A[i][j] 等于 1，那 A[j][i] 也肯定等于 1，对角线上下两部分相等，浪费一半空间；
其次，存储的矩阵大都是稀疏矩阵，比如微信有好几亿的用户，对应到图上就是好几亿的顶点。但矩阵中绝大部分都是0。

邻接表 Adjacency List

结构类似于散列表，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

对于无向图类似，不过每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。

这种方法节省空间，但是使用起来就比较耗时间。

若想判断是否存在一条从顶点 2 到顶点 4 的边，就要遍历 顶点 2 对应的那条链表，看链表中是否存在顶点 4。

可以将链表改成红黑树或跳表，以增加查找速度。

逆邻接表

以微博关注为例，
使用邻接表查找某个用户关注了哪些用户容易（某个顶点指向哪些其他顶点），
但是如果想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。

这时，需要一个逆邻接表，来存储指向这个顶点的顶点。

存储下方图信息：

【邻接矩阵存图】

 
#include<iostream>
using namespace std;
int r[105][105];//邻接矩阵，用于储存图的信息 , r[v][u] = 0 表示不存在边(v,u) , r[v][u] = 1 表示存在边(v,u)； 
int main(){
	int n;//顶点个数
	int m;//边数 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int v,u;// (v,u):表示 v->u 的边;
		cin>>v>>u;//输入边信息 
		r[v][u] = 1; //储存边信息 
	} 
	for(int i=1;i<=n;i++){ // 输出每个顶点 i 相连的顶点 
		cout<<"顶点"<<i<<"："; 
		for(int j=1;j<=n;j++){
			if( r[i][j] == 1){ 
				cout<<j<<' ';
			}
		}
		cout<<endl;
	}
	return 0;
}

【邻接表存图】（使用数组模拟链表）

#include<iostream>
using namespace std;
const int MAX = 10005; 
int n,m;
int vex[MAX];
typedef struct nodeEdge{ // 边类型 
	int to;//指向顶点u
	int next;//指向上一条边的位置 
}; 
nodeEdge arrPath[2*MAX];

//构建边
void creat_graph(int v1,int v2,int curPos){
	arrPath[curPos].to = v2;
	arrPath[curPos].next = vex[v1];
	vex[v1] = curPos;
} 

//输出图信息
void print_Graph(int n){
	for(int i=1;i<=n;i++){
		cout<<"顶点"<<i<<':';
		int index = vex[i];//获取与顶点i相连的边的编号
		while(index!=-1){
			cout<<arrPath[index].to<<' '; 
			index = arrPath[index].next;
		} 
		cout<<endl;
	}	
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		vex[i] = -1;
	}
	for(int i=1;i<=m;i++){
		int v1,v2;
		cin>>v1>>v2;
		creat_graph(v1,v2,i);
	}
	print_Graph(n);
	return 0;
}

输入数据： 第一行输入顶点个数n,边数m,接下来m行，每行为 v,u, 表示从顶点v到顶点u的一条有向边；
【输入数据】
7 12
1 3
1 2
1 4
2 4
2 5
3 6
4 3
4 6
4 7
5 4
5 7
7 6

【输出结果】