拓扑排序不用解释了。
下面的代码用的是DFS的思路来做,稍微修改也可以用作判断是否有环。
int c[N]; int topo[N],t; bool dfs(int u) { c[u]=-1; for(int v=0;v<n;v++) if ( graph[u][v]==1 ) { if ( c[v]==-1 ) return false; // circle else if ( c[v]==0 && !dfs(v) ) return false; } c[u]=1; topo[--t]=u; //sequence return true; } bool toposort() { t=n; memset(c,0,sizeof(c)); for(int u=0;u<n;u++) if ( c[u]==0 ) if ( dfs(u)== false ) return false; return true; }
欧拉回路:从图的某一个顶点出发,图中每条边走且仅走一次,最后回到出发点;如果这样的回路存在,则称之为欧拉回路。
欧拉路径:从图的某一个顶点出发,图中每条边走且仅走一次,最后到达某一个点;如果这样的路径存在,则称之为欧拉路径。
无向图欧拉回路存在条件:所有顶点的度数均为偶数。
无向图欧拉路径存在条件:至多有两个顶点的度数为奇数,其他顶点的度数均为偶数。
有向图欧拉回路存在条件:所有顶点的入度和出度相等。
有向图欧拉路径存在条件:至多有两个顶点的入度和出度绝对值差1(若有两个这样的顶点,则必须其中一个出度大于入度,另一个入度大于出度),其他顶点的入度与出度相等。
void dfs(int u) { for(int v = 1; v <= n; v++) { if(!graph[u][v]) continue; graph[u][v] = graph[v][u] = false; dfs(v); edgeTrail.add(u, v); nodeTrail.add(u); } }