网站seo排名免费咨询,wordpress软件下载站主题,网页制作考试题及答案,wordpress标签是干什么的文章目录 1. 有向图设计1.1 私有变量标记是否有向1.2 添加边的处理#xff0c;双向变单向1.3 删除边的处理#xff0c;双向变单向1.4 有向图的出度和入度 2 有向图的环检测2.1 普通的算法实现换检测2.2 拓扑排序中的环检测 3 欧拉回路 1. 有向图设计
1.1 私有变量标记是否有… 文章目录 1. 有向图设计1.1 私有变量标记是否有向1.2 添加边的处理双向变单向1.3 删除边的处理双向变单向1.4 有向图的出度和入度 2 有向图的环检测2.1 普通的算法实现换检测2.2 拓扑排序中的环检测 3 欧拉回路 1. 有向图设计
1.1 私有变量标记是否有向
private boolean directed;设计接口来判断是否有向
public boolean isDirected(){return directed;
}1.2 添加边的处理双向变单向
遍历文件给出的相邻顶点时如果邻接表上有节点就添加一条边。
如果是无向图反过来添加边。
adj[a].add(b);// 如果是无向图
if(!directed)adj[b].add(a);1.3 删除边的处理双向变单向
public void removeEdge(int v, int w){validateVertex(v);validateVertex(w);if(adj[v].contains(w)) E --;adj[v].remove(w);if(!directed)adj[w].remove(v);
}1.4 有向图的出度和入度
设计两个数组分别记录对应节点的出度和入度
private int[] indegrees, outdegrees;indegrees new int[V];
outdegrees new int[V];添加边的时候更新相应的度数值
for(int i 0; i E; i ){int a scanner.nextInt();validateVertex(a);int b scanner.nextInt();validateVertex(b);if(a b) throw new IllegalArgumentException(Self Loop is Detected!);if(adj[a].contains(b)) throw new IllegalArgumentException(Parallel Edges are Detected!);adj[a].add(b);if(directed){outdegrees[a] ;indegrees[b] ;}if(!directed)adj[b].add(a);
}度数的接口
public int degree(int v){if(directed)throw new RuntimeException(degree only works in undirected graph.);validateVertex(v);return adj[v].size();
}public int indegree(int v){if(!directed)throw new RuntimeException(indegree only works in directed graph.);validateVertex(v);return indegrees[v];
}public int outdegree(int v){if(!directed)throw new RuntimeException(outdegree only works in directed graph.);validateVertex(v);return outdegrees[v];
}2 有向图的环检测
2.1 普通的算法实现换检测
设计新的数组记录当前路径.
标记当前路径和标记是否访问过的区别标记是否访问过时为了避免在dfs过程中检测环的时候重复检测已经访问过的节点。
0-1-2-4-2-1退回到1 的时候由于2已经标记访问过因此下一个节点访问3. onPath的时候退回到0-1时将2和4重新标记为false因为已经不在当前路径中 0-1-2-4 0-1 访问到3的时候onPath为0-1-3下一个节点访问1由于1已经在onPath中则直接返回环检测结果。
private boolean[] onPath;private boolean dfs(int v){visited[v] true;onPath[v] true;for(int w: G.adj(v))if(!visited[w]){if(dfs(w)) return true;}else if(onPath[w])return true;onPath[v] false;return false;
}2.2 拓扑排序中的环检测
能够进行拓扑排序的图是没有环的否则无法进行拓扑排序。 在拓扑排序的实现过程中如果返回的res数组中的点的数量与图的点的数量不一致则说明有环。因为环上的点由于度数无法为0无法进入队列从而进入res数组返回答案。
if(res.size() ! G.V()){hasCycle true;res.clear();
}3 欧拉回路 判断出度和入度即可
private boolean hasEulerLoop(){for(int v 0; v G.V(); v )if(G.indegree(v) ! G.outdegree(v))return false;return true;
}
