图的简单介绍

定义及术语

G(V,E)：图G的顶点集为V，边集为E。分为有向图和无向图两类。
顶点的度：与该结点相连的边的条数。
出度：顶点的出边条数
入度：顶点的入边条数
顶点的权值称为点权，边的权值称为边权。

存储

1.邻接矩阵
用一个二维数组G[ i ][ j ]实现存储顶点 i 与顶点 j 之间的关系，可以是存储两顶点之间的边权，也可以仅表示两顶点之间是否有关系。
它其实是一个对称矩阵，相当于一个无向图。
但不适合顶点数目较多的题目。

2.邻接表
为每个顶点建立一个邻接表，用来存储与之有关的出边的信息，包括边的顶点与边的大小。
那么n个顶点就会有n个邻接表。对于每个邻接表可以用数组存储，也可以用链表存储。

此处示范用vector容器存储

//只存边的编号情况
vector<int> node;
node[i].push_back(index);//向编号为i的顶点加入一个编号为index的顶点

//存边的编号与大小的情况
struct node{int num;int value;
};
vector<node> v;
void insert(int x,int y){node n;n.num=x;n.value=y;v.push_back(n);
}

//存边的编号与大小的情况
struct node{//可实现定义的同时初始化int num;int value;node(int n,int v){//构造函数-初始化num=n;value=v;}
};
vector<node> v;
void insert(int x,int y){v.push_back(node(x,y));
}