图的存储和遍历

二维数组邻接矩阵存储

数组定义：int G[101][101]
$G[i][j]$的值，表示从点$i$到点$j$的边的权值，定义如下：

读入方式：

直接给出邻接矩阵

for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++)
		cin>>G[i][j];

给出两点编号和权值(有向图)

比如有$m$条边。

for(int i = 1; i <= m; i++){
	cin>>x>>y>>w;
	G[x][y] = w;
}

给出两点编号和权值(无向图)

for(int i = 1; i <= m; i++){
	cin>>x>>y>>w;
	G[x][y] = G[y][x] = w;
}

邻接矩阵-图的遍历

图的遍历有两种：$DFS$和$BFS$

深搜DFS

void dfs(int x)
{
	vis[x] = 1; //每个顶点只访问一次，所以做好标记
	for(int i = 1; i <= n; i++){ //遍历与x关联的点
		if(G[x][i] && vis[i]==0){           //如果没访问过
			dfs(i);
		}
	}
}

宽搜

q.push(1);
vis[1] = 1;
while(q.size())
{
	int x  = q.front();
	q.pop();
	for(int i = 1; i <= n; i++){
		if(G[x][i] && vis[i]==0){
			q.push(i);
			vis[i] = 1;
		}
	}
}

邻接矩阵练习题
1842:图的遍历
1175:传话游戏

vector动态数组模拟邻接表

定义：vector<int> G[MAXN], $MAXN$表示顶点总数。
利用动态数组特性，模拟链接表。
当邻接矩阵无法创建的时候，就要用邻接表的方式储存图。
读入方式：

给出两点编号(无向图无权值)

表示两点之间有连边。

for(int i = 1; i <= m; i++){
	cin>>x>>y;
	G[x].push_back(y);
	G[y].push_back(x);
}

给出两点编号(无向图有权值)

定义：vecotr<pair<int,int> > G[MAXN]

for(int i = 1; i <= m; i++){
	cin>>x>>y>>w;
	G[x].push_back({y,w});
	G[y].push_back({x,w});
}

如果结构体的话，定义如下：

struct node{
   int v,w; //v表示顶点编号，w表示权值
};
vector<node> G[MAXN];
....
for(int i = 1; i <= m; i++){
	cin>>x>>y>>w;
	G[x].push_back({y,w});
	G[y].push_back({x,w});
}

邻接表-图的遍历

只有顶点编号，无权值

深搜DFS

void dfs(int x)
{
	vis[x] = 1; //每个顶点只访问一次，所以做好标记
	for(auto y: G[x]){           //遍历与x关联的点
		if(vis[y]==0){           //如果没访问过
			dfs(y);
		}
	}
}

宽搜

q.push(1);
vis[1] = 1;
while(q.size())
{
	int x  = q.front();
	q.pop();
	for(auto y : G[x]){
		if(vis[y]==0){
			q.push(y);
			vis[y] = 1;
		}
	}
}

有权值的遍历

深搜(pair<int,int>)

void dfs(int x)
{
	vis[x] = 1;
	for(auto y:G[x]){
		if(vis[y.first]==0){
			dfs(y.first);
		}
	}
}

深搜（struct)，结构体参考 上面

void dfs(int x)
{
	vis[x] = 1;
	for(auto y:G[x]){
		if(vis[y.v]==0){
			dfs(y.v);
		}
	}

}

auto是$c++11$语法，它的作用能够根据目标类型，自动适配。需要在编译参数中增加：$-std=c++11$，例如在DEV-C++中，如下设置。

课后习题

7720-Wand
9708-开车搜集宝物

树是特殊的图

树可以看成$n$个顶点，$n-1$条边组成的图。
如果树以两点连边的方式告诉你，也可以用邻接表的方式保存，因为不知道哪个是父节点，哪个是孩子节点，所以看成无向图，所以读入方式跟无向图一样。

树的遍历

根据树的特点，对一个顶点而言，只搜索它的孩子节点，所以要防止搜父节点，这是因为用无向图方式保存，孩子节点也连着父节点。

void dfs(int x, int fa) //fa为x的父节点编号
{
	for(auto y:G[x]){  //遍历x的孩子节点
		if(y!=fa){     //排除x的父节点
			dfs(y,x);  //y的父亲为x
		}
	}
}

主程序调用：

dfs(1,-1); //根节点没有父节点，所以可以传入非节点编号

课后习题

3383-Transit Tree Path