【数据结构】-图-判断一个无向图是否是一棵树

思路：判断一个无向图是否是一棵树，只需要判断该图是否是一个包含n个顶点的连通子图且边数为n-1,只要这两个条件都满足，那么就是一棵树。

因此我们可以采用深度遍历，若图连通，那么只要一次深度遍历就可以遍历出所有的顶点，于是只需要调用一次dfs，并设置两个计数器记录边和顶点的数目即可。

---

编程注意事项：

1.邻接表在存储无向图的时， 每一条边都存储了两次，所以计数器中得到的是两边的边数

2.函数的形式参数要是引用

void DFS_my(ALGraph &G, int v, int &count_vec, int &count_arc, vector<int> &visited) {
	visited[v] = true;
	count_vec++;
	for (ArcNode* p = G.vertices[v].first; p; p = p->next) {
		count_arc++;
		if (!visited[p->adjvex]) DFS_my(G, p->adjvex, count_vec, count_arc, visited);
	}
}

bool isTree(ALGraph G) {
	vector<int> visited(G.vecnum, false);
	int count_vec = 0;
	int count_arc = 0;
	DFS_my(G, 0, count_vec, count_arc,visited);
	//因为无向图在深度遍历的时候，每条边都计算了两次
	if (count_vec == G.vecnum&&count_arc == 2 * (G.vecnum - 1)) return true;
	else return false;
}


inr main() {
	int n, m;
	cout << "请输入有向图顶点数和边数" << endl;
	cin >> n >> m;
	ALGraph G;
	create(&G, n, m);
	//判断无向图是否为一棵树，只要无向图的所有顶点能构成一个边为n-1的连通图即可
	//所有顶点连通，说明只要一次深度搜索即可，用
	if (isTree(G))cout << "是一棵树";
	else cout << "不是一棵树";

}