再谈图的存储方式（邻接矩阵，邻接表，前向星）

1.存图思想

使用一个矩阵来描述一个图，对于矩阵的第i行第j列的值，表示编号为i的顶点到编号为j的顶点的权值。

2.代码实现

// 最大顶点数
const int V = 1000;// 邻接矩阵的定义
// mat[i][j] 表示 顶点'i'到顶点'j'的权值
int mat[V][V];// 邻接矩阵的初始化操作
// 假设权值为零表示没有该边
memset(mat, 0, sizeof(mat))// 增加边
// 新增顶点'i'到顶点'j'的边，权值为w
mat[i][j] = w;//遍历邻接边
for(int i=0;i<n;i++)
{for(int j=0;j<n;j++){if(mat[i][j]!=0)//doing something.}
}

2.邻接表

1.存图思想

邻接矩阵对于每个顶点使用定长的数组来存储以该点出发的边的情况。第i个数组的第j个值存储的是从顶点i到顶点j的边的权值。 
而邻接表则是对于每个顶点使用不定长的链表来存储以该点出发的边的情况。因此对于第i个链表的第j个值实际上存储的是从编号为i的顶点出发的第j条边的情况。

2.代码实现

// 最大顶点数
const int V = 100000;// vector实现的邻接表的定义
// 不考虑边权，存储类型为int型
vector<int> e[V];
// 若考虑边权，则定义一个结构，vector也为结构体类型
struct node{int v,int w};//存储边的终点和边的权值
vector<node> e[V];
//也可以用一个数组或vector单独存边的信息，然后在邻接表vector中记录每个点邻接边的编号// 邻接表的初始化操作
for(int i=0;i<n;i++)
{e[i].clear();
}// 增加边
//不考虑边权
e[i].push_back(j);
//考虑边权
e[i].push_back(node(j,w));//遍历邻接边
for (int j=0; j<(int)e[i].size(); ++j) {int k=e[i][j];//第j条边为[i,k]//ornode &e=e[i][j];//第j条边为[i,e.v,e.w]// do something.
}

3.前向星

4.链式前向星

1.存图思想

struct Edge
{int next;int to;int w;
};

// 最大顶点数
const int V = 1000;
const int E = 10000;struct Edge
{int next;int to;int w;
};
Edge edge[E];
int head[V];//初始化
memset(head,0xff,sizeof(head));
memset(edge,0,sizeof(edge));//增加边
void add(int u,int v,int w) 
{  //cnt为边计数edge[cnt].w = w;  edge[cnt].to = v;  edge[cnt].next = head[u];  head[u] = cnt++;  
} //遍历边
for(int i=1;i<=n;i++)
{for(int k=head[i];k!=-1;k=edge[k].next){//doing something.}
}