【数据结构实验】图的基本操作（图的存储&拓扑排序）

熟悉图的基本定义，有向图、无向图的存储方式及相关基本操作，能够根据实际情况选择合适的存储结构。

1、 输入有向图，并存储

2、实现拓扑排序算法或最短路径算法

图的定义：点和边的集合G=（V，E）

把每个边分成正反两个边就可以用有向图的方式表示无向图。

存储图有一种很朴素的方法就是将所有的边存储起来。（纯边集）

邻接矩阵存图是一种比较高效的存图方法。具体方法就是建立一个二维数组，每个点对应一个数字，一个数字对另一个数字若有出边，则对应记上1，否则记为0。

优点：O(1)的时间复杂度去查找给定的两点之间的边。

缺点：存图的空间复杂度为O（V的平方）遍历任意点的出边的空间复杂度略大，为O（V的个数）。

而邻接表存图则是每个点用链表存所有出边（有向边）

优点：利用O(V的个数+E的个数)的空间复杂度存图，遍历任意点的出边需要的时间就是出边个数。

邻接表存图C++模板：

#include
#include
using namespace std;
int N, M;//N为点的个数，M为边的个数
int etop; //EDGE中内存池中用到了哪个地方

用邻接表构建图
//构建边结构体
struct EDGE {
	int u, v, len;//u为起点，v为终点，len为边的长度
	EDGE* nex;//指向EDGE
}epool[100001];//开辟一个内存池 

//构建点结构体
struct NODE {
	EDGE* fir;//出边链表的第一个 指向EDGE
}nodes[10001];//内存池


stack ansstack;
//添加边的函数
void addedge(int u, int v,int len) {
	epool[etop].u = u;
	epool[etop].v = v;
	epool[etop].nex = nodes[u].fir;//第u个点的出边的集合的链表的开头
	nodes[u].fir = &epool[etop];
	etop++;
}

int main()
{
	int i,u,v,len;//几条边 起点 终点 长度
	cin >> N >> M;
	for (i = 1; i <= M; i++)//M条边
	{
		cin >> u >> v >> len;
		addedge(u, v, len);
		//无向图再加这行
		//addedge(v,u,len);
	}
	这样遍历id号点的出边
	//EDGE* e = nodes[id].fir;
	//while (e!=NULL) {
	//	//e->v
	//	//e->u

	//	e = e->nex;
	//}

	system("pause");
	return 0;
}

给一个有向图，找出一种将所有节点排序的方法，满足所有有向边的起点都排在终点之前。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gv1rVQbb-1652100285684)(https://gitee.com/arashi0414/drawing-bed/raw/master/img/image-20220508104630712.png)]

有向图的拓扑排序不一定唯一，也不一定存在。（有环一定不能拓扑排序，无环必定可以拓扑排序）

拓扑排序可行的充分必要条件：给定有向图是一个有向无环图。

直观思想：从一个点x开始搜索全图，把x出边指向的点排在x后面，但是存在一个问题就是边x→y不能保证y紧排在x后是可行的，因为可能存在没探索到的x→z→y结构。

所以只有确定点x之下的所有点已经排完位置了才能把x紧密的排在x之下的所有点的前面。所以正确的策略是顺着有向边进行搜索，但从后往前依次排搜完的点。

如果在DFS的操作过程中找到了正在进行DFS的点，则证明有环。

我们用一个数组去记录每个点的状态：①还没有遇到②DFS进行中③DFS已完成

每个DFS完成的点要排在最靠后的空位上，也就是所有已经排过的点的前面。

最后，要从每个点开始尝试DFS，保证给每个点都排过。

#include
#include
using namespace std;
int N, M;//N为点的个数，M为边的个数
int etop; //EDGE中内存池中用到了哪个地方
bool valid = true;//在dfs过程中是否遇到环

stack ansstack;//整个拓扑排序用int的stack存起来

用邻接表构建图
//构建边结构体
struct EDGE {
	int u, v, len;//u为起点，v为终点，len为边的长度
	EDGE* nex;//指向EDGE
}epool[100001];//开辟一个内存池 

//构建点结构体
struct NODE {
	int mark;//存状态，0：没有遇到 1：已经完成dfs -1：正在进行dfs
	EDGE* fir;//出边链表的第一个 指向EDGE
}nodes[10001];//内存池



//添加边的函数
void addedge(int u, int v) {
	epool[etop].u = u;
	epool[etop].v = v;
	epool[etop].nex = nodes[u].fir;//第u个点的出边的集合的链表的开头
	nodes[u].fir = &epool[etop];
	etop++;
}

//搜索函数
void dfs(int id) {
	if (nodes[id].mark == -1) //如果正在dfs（即有环）
	{
		valid = false;
		return;
	}
	if (nodes[id].mark == -1)//已经完成dfs
		return;
	nodes[id].mark = -1;
	//遍历整个图
	EDGE* e = nodes[id].fir;
	while (e!=NULL) {
		dfs(e->v);
		e = e->nex;
	}
	//完成所有的dfs之后 将图存起来
	ansstack.push(id);
	nodes[id].mark = 1;//恢复现场
}

int main()
{
	int i, x, y;///循环变量、输入有向边x指向y
	cout << "请输入点和边的个数" << endl;
	cin >> N >> M;
	for (i = 1; i <= M; i++) {
		cout << "请输入第"<> x >> y;
		addedge(x, y);
	}
	for (i = 1; i <= N; i++) dfs(i); //每一个点都进行搜索
	//进行检验
	if (valid) {
		cout << "拓扑排序为：" << endl;
		while (!ansstack.empty()) //栈如果不为空
		{
			cout << ansstack.top() << ' ';
			ansstack.pop();
		}
		cout << endl;
	}
	else cout << "INVALID!" << endl;
	system("pause");
	return 0;
}