《算法》第四章部分程序 part 4
2024-10-13 00:34:23
▶ 书中第四章部分程序，加上自己补充的代码，图的深度优先遍历
● 无向图的深度优先遍历，有向 / 无向图代码仅若干方法名不同，包括递归和非递归版本，去掉了顶点有效性的检查
package package01; import java.util.Iterator; // nonRecursiveDFS 需要
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Stack; // recursiveDFS 不用 public class class01
{
private final int s; // 根顶点，depthFirstPath 需要
private boolean[] marked; // 顶点是否已被遍历
private int count; // 已遍历的顶点数（含后退），即从 s 可达的顶点数，depthFirstPath 不用
private int[] edgeTo; // 每个顶点在 s - v 路径中的父顶点，depthFirstPath 需要 public class01(Graph G, int inputS) // 初始化，开始DFS
{
s = inputS;
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
recursiveDFS(G, s);
} private void recursiveDFS(Graph G, int v)
{
count++;
marked[v] = true;
for (int w : G.adj(v))
{
if (!marked[w])
{
edgeTo[w] = v; // depthFirstPath 需要
recursiveDFS(G, w);
}
}
} public void nonRecursiveDFS(Graph G, int s) // 非递归版本
{
marked = new boolean[G.V()];
Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];// 记录每个顶点处已经遍历到了哪一个链表节点
for (int v = 0; v < G.V(); v++)
adj[v] = G.adj(v).iterator();
Stack<Integer> stack = new Stack<Integer>();
marked[s] = true;
for (stack.push(s); !stack.isEmpty();)
{
int v = stack.peek();
if (adj[v].hasNext())
{
int w = adj[v].next();
if (!marked[w])
{
marked[w] = true;
stack.push(w);
}
}
else
stack.pop();
}
} public boolean marked(int v)
{
return marked[v];
} public int count()
{
return count;
} public Iterable<Integer> pathTo(int v)
{
if (!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) // 从终点向起点压栈，以后吐栈的时候就是从起点到终点
path.push(x);
path.push(s);
return path;
} public static void main(String[] args)
{
In in = new In(args[0]); // 读入图文件和遍历起点
int s = Integer.parseInt(args[1]);
Graph G = new Graph(in);
class01 search = new class01(G, s);
for (int v = 0; v < G.V(); v++) // 通过检查是否所有的点都被遍历来确定图是否连通
{
if (search.marked(v))
{
StdOut.printf("%d to %d: ", s, v);
for (int x : search.pathTo(v))
{
if (x == s)
StdOut.print(x);
else
StdOut.print("-" + x);
}
StdOut.println();
}
else
StdOut.printf("%d to %d: not connected\n", s, v);
}
if (search.count() != G.V())
StdOut.println("\nNot connected.\n");
else
StdOut.println("\nConnected.\n");
}
}
● 有向图的深度优先遍历
package package01; import java.util.Iterator;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.Stack; public class class01
{
private final int s;
private boolean[] marked;
private int count;
private int[] edgeTo; public class01(Digraph G, int inputS)
{
s = inputS;
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
recursiveDirectedDFS(G, s);
} private void recursiveDirectedDFS(Digraph G, int v)
{
count++;
marked[v] = true;
for (int w : G.adj(v))
{
if (!marked[w])
{
edgeTo[w] = v;
recursiveDirectedDFS(G, w);
}
}
} public void nonRecursiveDirectedDFS(Digraph G, int s)
{
marked = new boolean[G.V()];
Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
for (int v = 0; v < G.V(); v++)
adj[v] = G.adj(v).iterator();
Stack<Integer> stack = new Stack<Integer>();
marked[s] = true;
for (stack.push(s); !stack.isEmpty();)
{
int v = stack.peek();
if (adj[v].hasNext())
{
int w = adj[v].next();
if (!marked[w])
{
marked[w] = true;
stack.push(w);
}
}
else
stack.pop();
}
} public boolean marked(int v)
{
return marked[v];
} public int count()
{
return count;
} public Iterable<Integer> pathTo(int v)
{
if (!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
} public static void main(String[] args)
{
In in = new In(args[0]);
int s = Integer.parseInt(args[1]);
Graph G = new Graph(in);
class01 search = new class01(G, s);
for (int v = 0; v < G.V(); v++)
{
if (search.marked(v))
{
StdOut.printf("%d to %d: ", s, v);
for (int x : search.pathTo(v))
{
if (x == s)
StdOut.print(x);
else
StdOut.print("-" + x);
}
StdOut.println();
}
else
StdOut.printf("%d to %d: not connected\n", s, v);
}
if (search.count() != G.V())
StdOut.println("\nNot connected.\n");
else
StdOut.println("\nConnected.\n");
}
}
最新文章
- 使用sublime text 开发node.js
- 关于codeblock中一些常用的快捷键（搬运）
- 深入了解SQL注入绕过waf和过滤机制
- 【GoLang】GoLang 遍历 map、slice、array方法
- centos下配置java环境变量
- STM32的I2C通信
- How To Easily Call WCF Services Properly z
- C++中的仿函数,std::function和bind()的用法
- [GeekBand] C++学习笔记（2）——BigThree、OOP
- hdu1046
- apache的工作模式 和 最大连接数设置
- 20160222.CCPP体系详解(0032天)
- N个整数（数的大小为0-255）的序列，把它们加密为K个整数（数的大小为0-255）.再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法,且要求K<=15*N.
- 折腾Java设计模式之解释器模式
- redis cluster介绍
- centos7 jmeter分布式安装
- C++ vector 使用笔记
- springmvc拦截器实现用户登录权限验证
- python 调用阿里云服务器api创建服务器
- @RequestParam的使用