图的存储和遍历

图的存储

图的存储方式有两种：分别是邻接矩阵和邻接表；

邻接矩阵：

开一个二维数组G[i][j],值为1则说明有边，反之则0说明没有边，其值也可以存放边权。

只适用于顶点数不太大（一般不超过1000）的题目

邻接表：

用vector实现邻接表，在一些顶点数目较大（一般顶点个数在1000以上）的情况下，一般是使用邻接表而不是邻接矩阵才存储图。

图的遍历

图的遍历是指按一定顺序遍历所有顶点， 一般遍历方法有两种，分别是深度优先搜索和广度优先搜索。

深度优先搜索遍历图：

以"深度"为关键词，沿着一条路直到无法继续前进，才退回到路径上离当前顶点最近的且有未遍历分支的岔路口，并前往访问那些未遍历的分支，直到遍历完整个图。

如果是用邻接矩阵存储图，就用以下方法遍历图：
 

//可以相互到达的结点的集合是连同块，无向图又叫做连同分量，有向图又叫做强连通分量； 
const int maxn = 10000;//最大顶点数;
const int INF = 1e6;
//邻接矩阵实现图存储;
int n, G[maxn][maxn];
bool vis[maxn] = {false};//判断该结点是否有访问;
//遍历顶点的分支;
void DFS(int u, int depth) {//顶点编号; 
	vis[u] = true;//当前顶点已被访问; 
	//此处可以对u进行一些操作;
	for(int v = 0; v < n; v++) {//对u的分支顶点进行枚举; 
		if(vis[v] == false && G[u][v] != INF){
			DFS(v, depth+1); 
		}
	} 
} 

//遍历顶点;
void DFSTrave( ) {
	for(int u = 0; u < n; u++) {//遍历图的所有顶点; 
		if(vis[u] == false) {
			DFS(u, 1);//u == 0的顶点是第一层; 
		}
	}
} 

邻接表存储图：
 

//邻接表存储图；
const int maxn = 1010;
const int INF = 1e6 + 10;
bool vis[maxn] = {false};//判断该结点是否有被访问;
 
 vector<int > Adj[maxn];//邻接表，每个vector代表每个顶点，push_back是每个顶点能直到达的顶点：
 void DFS(int u, int depth) {//要遍历的顶点;
 	vis[u] = true; 
 	for(int v = 0; v < Adj[u].size( ); v++) {//遍历u顶点下能直接到达的顶点; 
 		if(vis[v] == false) {
 			DFS(v, depth + 1);
		 }
	 } 
 } 
 
 void DFSTrave( ) {
 	for(int u = 0; u < n; u++) {//遍历图内所有顶点; 
 		if(vis[u] == false) {
 			DFS(u, 1);
		 }
	 } 
 }