由于要面试的缘故，在看算法导论的图算法一节，决定把基本的算法都用java代码实现出来。
1. 图的表示，使用链接表的形式。
class TreeNode{
int nodeNum ; //节点编号
TreeNode parent = null; //遍历时的父节点
int dis = Integer.MAX_VALUE;// 距离源节点的路径
int discoverTime =0; //在DFS遍历时发现的时间
int finishTime =0;//DFS遍历时结束的时间
Color color = Color.White;//初始时的颜色标记
List<Integer> edges = new ArrayList<Integer>();//节点的边集合
public TreeNode(int i) {
nodeNum = i;
}
public int getNodeNum() {
return nodeNum;
}
public void setNodeNum(int nodeNum) {
this.nodeNum = nodeNum;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getDis() {
return dis;
}
public void setDis(int dis) {
this.dis = dis;
}
public int getDiscoverTime() {
return discoverTime;
}
public void setDiscoverTime(int discoverTime) {
this.discoverTime = discoverTime;
}
public int getFinishTime() {
return finishTime;
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
}
2. 图的构建：
TreeNode[] heads = null;
final int NODENUM ;
public GraphicModelII(int nodeNum) {
NODENUM = nodeNum;
heads = new TreeNode[NODENUM+1];
for(int i=1;i<=nodeNum;i++){
heads[i] = new TreeNode(i);
}
}
public void addEdge(int src,int des){
heads[src].edges.add(des);
}
3. 广度优先搜索
public void BFS(int src){
Queue<TreeNode> searchs = new LinkedList<TreeNode>();
heads[src].color = Color.Gray;
heads[src].dis= 0;
searchs.add(heads[src]);
while(!searchs.isEmpty()){
TreeNode cur = searchs.poll();
System.out.println("Node : "+cur.nodeNum);
for(Integer des:cur.edges){
TreeNode now = heads[des];
if(now.color == Color.White){
now.color = Color.Gray;
now.dis = cur.dis+1;
now.parent = cur;
searchs.add(now);
}
}
cur.color = Color.Black;
}
}
4. 深度优先搜索
public void DFS(){
systemTime = 0;
for(int i=1;i <=NODENUM;i++){
TreeNode node = heads[i];
if(node.color==Color.White){
DFS_Visit(node);
}
}
}
public void DFS_Visit(TreeNode node){
node.color = Color.Gray;
systemTime++;
node.discoverTime = systemTime;
for(Integer des:node.edges){
TreeNode now = heads[des];
if(now.color==Color.White){
now.parent = node;
DFS_Visit(now);
}
}
node.color = Color.Black;
systemTime++;
node.finishTime = systemTime;
topoSortUtil.push(node);
System.out.println(node.nodeNum+"start:\t"+node.discoverTime+" end:\t"+node.finishTime);
}
5. topo 排序：
topo 排序的算法
使用DFS来完成，对于每一个发现的节点，压入栈中
Stack<TreeNode> topoSortUtil = new Stack<TreeNode>();
对应DFS中 黄色标记代码
public void topoSort(){
topoSortUtil.clear();
DFS();
while(!topoSortUtil.isEmpty()){
System.out.println(topoSortUtil.pop().nodeNum);
}
}
6. 求强连通分支SCC。
第一步 使用DFS算法，把每个节点遍历完成时写入到topoSortUtil 中，栈顶的元素是最后才遍历结束的节点。
第二步，求原图G的转置， 把原图中 u -v的边 变为 v-u.
见reverTopo 函数，遍历之后的图用heads_reverse 表示
第三步 使用DFS算法，求SCC。需要注意的是，在原始的DFS中
public void DFS(){
systemTime = 0;
for(int i=1;i <=NODENUM;i++){
TreeNode node = heads[i];
if(node.color==Color.White){
DFS_Visit(node);
}
}
}
for 循环 的节点顺序无要求，但是在求SCC时，需要使用topoSortUtil，最晚结束遍历的元素作为第二次遍历的第一个元素，并依此类推。
public void SCC(){
DFS();
List<TreeNode> scc = new ArrayList<TreeNode>();
reverTopo();
while(!topoSortUtil.isEmpty()){
TreeNode cur = heads_reverse[topoSortUtil.pop().nodeNum];
if(cur.color==Color.White){
DFS_Visit_Scc(cur,scc);
}
for(TreeNode node:scc){
System.out.print(node.nodeNum);
}
System.out.println();
scc.clear();
}
}
public void DFS_Visit_Scc(TreeNode node,List<TreeNode> scc){
node.color = Color.Gray;
systemTime++;
node.discoverTime = systemTime;
for(Integer des:node.edges){
TreeNode now = heads_reverse[des];
if(now.color==Color.White){
now.parent = node;
DFS_Visit_Scc(now,scc);
}
}
node.color = Color.Black;
systemTime++;
node.finishTime = systemTime;
scc.add(node);
}
private void reverTopo(){
for(int i=1;i <=NODENUM;i++){
TreeNode node = heads[i];
int src = node.nodeNum;
for(Integer des:node.edges){
TreeNode reverNode = heads_reverse[des];
reverNode.edges.add(src);
}
}
}
完整代码
package graphic;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
public class GraphicModelII {
TreeNode[] heads = null;
final int NODENUM ;
static int systemTime = 0;
Stack<TreeNode> topoSortUtil = new Stack<TreeNode>();
TreeNode[] heads_reverse = null;
public GraphicModelII(int nodeNum) {
NODENUM = nodeNum;
heads = new TreeNode[NODENUM+1];
heads_reverse =new TreeNode[NODENUM+1];
for(int i=1;i<=nodeNum;i++){
heads[i] = new TreeNode(i);
heads_reverse[i] = new TreeNode(i);
}
}
public void addEdge(int src,int des){
heads[src].edges.add(des);
}
public void BFS(int src){
Queue<TreeNode> searchs = new LinkedList<TreeNode>();
heads[src].color = Color.Gray;
heads[src].dis= 0;
searchs.add(heads[src]);
while(!searchs.isEmpty()){
TreeNode cur = searchs.poll();
System.out.println("Node : "+cur.nodeNum);
for(Integer des:cur.edges){
TreeNode now = heads[des];
if(now.color == Color.White){
now.color = Color.Gray;
now.dis = cur.dis+1;
now.parent = cur;
searchs.add(now);
}
}
cur.color = Color.Black;
}
}
public void DFS(){
systemTime = 0;
for(int i=1;i <=NODENUM;i++){
TreeNode node = heads[i];
if(node.color==Color.White){
DFS_Visit(node);
}
}
}
public void DFS_Visit(TreeNode node){
node.color = Color.Gray;
systemTime++;
node.discoverTime = systemTime;
for(Integer des:node.edges){
TreeNode now = heads[des];
if(now.color==Color.White){
now.parent = node;
DFS_Visit(now);
}
}
node.color = Color.Black;
systemTime++;
node.finishTime = systemTime;
topoSortUtil.push(node);
System.out.println(node.nodeNum+"start:\t"+node.discoverTime+" end:\t"+node.finishTime);
}
public void topoSort(){
topoSortUtil.clear();
DFS();
while(!topoSortUtil.isEmpty()){
System.out.println(topoSortUtil.pop().nodeNum);
}
}
public void SCC(){
DFS();
List<TreeNode> scc = new ArrayList<TreeNode>();
reverTopo();
while(!topoSortUtil.isEmpty()){
TreeNode cur = heads_reverse[topoSortUtil.pop().nodeNum];
if(cur.color==Color.White){
DFS_Visit_Scc(cur,scc);
}
for(TreeNode node:scc){
System.out.print(node.nodeNum);
}
System.out.println();
scc.clear();
}
}
public void DFS_Visit_Scc(TreeNode node,List<TreeNode> scc){
node.color = Color.Gray;
systemTime++;
node.discoverTime = systemTime;
for(Integer des:node.edges){
TreeNode now = heads_reverse[des];
if(now.color==Color.White){
now.parent = node;
DFS_Visit_Scc(now,scc);
}
}
node.color = Color.Black;
systemTime++;
node.finishTime = systemTime;
scc.add(node);
}
private void reverTopo(){
for(int i=1;i <=NODENUM;i++){
TreeNode node = heads[i];
int src = node.nodeNum;
for(Integer des:node.edges){
TreeNode reverNode = heads_reverse[des];
reverNode.edges.add(src);
}
}
}
public static void main(String[] args) {
// GraphicModelII graph = new GraphicModelII(5);
// graph.addEdge(1, 2);
// graph.addEdge(1, 5);
// graph.addEdge(2, 1);
// graph.addEdge(2, 5);
// graph.addEdge(2, 4);
// graph.addEdge(2, 3);
// graph.addEdge(3, 2);
// graph.addEdge(3, 4);
// graph.addEdge(4, 2);
// graph.addEdge(4, 5);
// graph.addEdge(5, 4);
// graph.addEdge(5, 2);
// graph.addEdge(5, 1);
// graph.BFS(1);
//graph.DFS();
// GraphicModelII graph = new GraphicModelII(9);
// graph.addEdge(1, 2);
// graph.addEdge(1, 8);
// graph.addEdge(2, 3);
// graph.addEdge(2, 8);
// graph.addEdge(3, 6);
// graph.addEdge(4, 3);
// graph.addEdge(4, 5);
// graph.addEdge(5, 6);
// graph.addEdge(7, 8);
// graph.topoSort();
//test scc
GraphicModelII graph = new GraphicModelII(8);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 3);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
graph.addEdge(3, 7);
graph.addEdge(4, 8);
graph.addEdge(5, 1);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(7, 6);
graph.addEdge(7,8);
graph.addEdge(8,8);
//graph.topoSort();
graph.SCC();
}
}
class TreeNode{
int nodeNum ;
TreeNode parent = null;
int dis = Integer.MAX_VALUE;
int discoverTime =0;
int finishTime =0;
Color color = Color.White;
List<Integer> edges = new ArrayList<Integer>();
public TreeNode(int i) {
nodeNum = i;
}
public int getNodeNum() {
return nodeNum;
}
public void setNodeNum(int nodeNum) {
this.nodeNum = nodeNum;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getDis() {
return dis;
}
public void setDis(int dis) {
this.dis = dis;
}
public int getDiscoverTime() {
return discoverTime;
}
public void setDiscoverTime(int discoverTime) {
this.discoverTime = discoverTime;
}
public int getFinishTime() {
return finishTime;
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
}
相关推荐
ALGraph DFS BFS DIJ toposort keyPath
基本图算法（bfs与dfs）1
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业： 定义采用邻接矩阵存储的图结构
定义采用邻接矩阵存储的图结构封装DFS、BFS算法
算法之BFS与DFS
深度优先遍历和广度优先遍历算法实现从定点开始的遍历序列。
这是山东大学可视化课程项目，用js实现的BFS和DFS，详细的展示了BFS和DFS的运行过程，网页可交互。
acm-ICPC 搜索算法DFS和BFS文件格式（ppt）经典算法“剪枝”等算法，深度优先搜索和广度优先搜索。
基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项：使用matlab2021a或者更高版本测试，运行里面的Runme.m文件，不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...
数据结构中重要的部分之一——图，这里主要完成一个无向无环图的建立，然后进行DFS BFS的遍历，输出结果，初学图和DFS BFS的小伙伴可以来看看噢
实现了图的DFS和BFS算法，实现语言C++
图的遍历方式包括DFS BFS,这个工程文件是俩种遍历方式的实现，适合学习用，工程实践还得加工，具体分析 在我的博客 数据结构练习 10
一些常用的排序算法，dfs bfs
DFS和BFS DFS（Depth-First-Search）深度优先搜索算法，是搜索算法的一种。是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法...
代码中包括了图的BFS和DFS遍历还包括了寻找最短路径，给定路长寻找路径，生成图，添加结点，删除节点
dfsbfs深度搜索.exe
从最基础的迷宫问题看深搜和宽搜的内涵，理解最基础的穷举搜索。
DFS（深度优先搜索）和BFS（广度优先搜索）是两种用于遍历或搜索树或图的算法。它们的主要区别在于访问节点的顺序。 1. **深度优先搜索（DFS）** 深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能...
基于邻接表存储的图的dfs与bfs遍历，对学习数据结构很有帮助