目录
1无向图
1.1无向图的表示
无向图的API：
实现:
package graphs.undirectedgraph;
import edu.princeton.cs.algs4.In;
import fundamentals.Bag;
public class Graph {
private final int V;//顶点数目
private int E;//边的数目
private Bag<Integer>[] adj;//领接表
public Graph(int V) {//创建一个含有v个顶点但不含有边的图
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];//创建领接表
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
}
public Graph(In in) {//从标准输入流in读入一幅图
this(in.readInt());//读取V并将图初始化
int E = in.readInt();//读取E
for (int i = 0; i < E; i++) {//添加一条边
int v = in.readInt();//读取一个顶点
int w = in.readInt();//读取另一个顶点
addEdge(v, w);//添加一条连接它们的边
}
}
public int V(){//顶点数
return V;
}
public int E(){//边数
return E;
}
public void addEdge(int v,int w){//向图中添加一条边v-w
adj[v].add(w);//将w添加到v的链表中
adj[w].add(v);//将v添加到w的链表中
E++;
}
public Iterable<Integer>adj(int v){//和v相邻的所有顶点
return adj[v];
}
public int degree(int v) {//计算v的度数
return adj[v].size();
}
public String toString() {//对象的字符串表示
StringBuilder s = new StringBuilder();
s.append(V + " vertices, " + E + " edges\n");
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append("\n");
}
return s.toString();
}
/*测试数据 13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3 */
public static void main(String[] args) {
In in = new In();
Graph G = new Graph(in);
System.out.println(G);
}
}
1.2深度优先搜索
原理:
要搜索一幅图，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时：
将它标记为已访问；
递归地访问它的所有没有被标记过得邻居顶点。
实现:
package graphs.undirectedgraph;
import edu.princeton.cs.algs4.In;
public class DepthFirstSearch {
private boolean[] marked;
private int count;//与s连通的顶点总数
public DepthFirstSearch(Graph G, int s){//找到和起点s连通的所有顶点
marked=new boolean[G.V()];
dfs(G,s);
}
private void dfs(Graph G,int v){
marked[v]=true;
count++;
for(int w:G.adj(v)){
if(!marked[w]){
dfs(G,w);
}
}
}
public boolean marked(int w){//v和s是连通的吗？
return marked[w];
}
public int count(){//与s连通的顶点总数
return count;
}
/*测试数据 13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3 9 */
public static void main(String[] args) {
In in = new In();
Graph G = new Graph(in);
int s = in.readInt();
DepthFirstSearch search = new DepthFirstSearch(G, s);
for (int v = 0; v < G.V(); v++) {
if (search.marked(v))
System.out.print(v + " ");
}
System.out.println();
if (search.count() != G.V()) System.out.println("NOT connected");
else System.out.println("connected");
}
}
1.3使用深度优先搜索查找图中的路径
原理：
实现：
package graphs.undirectedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
public class DepthFirstPaths {
private boolean[] marked;//这个顶点上调用过dfs()了吗？
private int[] edgeTo;//从起点到顶点的已知路径上的最后一个顶点
private final int s;//起点
public DepthFirstPaths(Graph G, int s){//在G中找出所有起点为s的路径（非最短路径）
marked=new boolean[G.V()];
edgeTo=new int[G.V()];
this.s=s;
dfs(G,s);
}
private void dfs(Graph G,int v){
marked[v]=true;
for(int w:G.adj(v)){
if(!marked[w]){
edgeTo[w]=v;
dfs(G,w);
}
}
}
public boolean hasPathTo(int v){//是否存在s到v的路径
return marked[v];
}
Iterable<Integer> pathTo(int v){//s到v的路径，如果不存在则返回null
if (!hasPathTo(v)) return null;
Stack<Integer> path=new Stack<>();
for(int x=v;x!=s;x=edgeTo[x]){
path.push(x);
}
path.push(s);
return path;
}
/*测试数据 6 8 0 5 2 4 2 3 1 2 0 1 3 4 3 5 0 2 0 */
public static void main(String[] args) {
In in = new In();
Graph G = new Graph(in);
int s = in.readInt();
DepthFirstPaths dfs = new DepthFirstPaths(G, s);
for (int v = 0; v < G.V(); v++) {
if (dfs.hasPathTo(v)) {
System.out.printf("%d to %d: ", s, v);
for (int x : dfs.pathTo(v)) {
if (x == s) System.out.print(x);
else System.out.print("-" + x);
}
System.out.println();
}
else {
System.out.printf("%d to %d: not connected\n", s, v);
}
}
}
}
1.4广度优先搜索
原理：
广度优先搜索可以解决单点最短路径问题。
实现：
package graphs.undirectedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
public class BreadthFirstPaths {
private boolean[] marked;//到达该顶点的最短路径已知吗？
private int[] edgeTo;//到达该顶点的已知路径上的最后一个顶点
private final int s;//起点
public BreadthFirstPaths(Graph G, int s){//在G中找出所有起点为s的路径（最短路径）
marked=new boolean[G.V()];
edgeTo=new int[G.V()];
this.s=s;
bfs(G,s);
}
private void bfs(Graph G,int s){
Queue<Integer> queue=new Queue<>();
marked[s]=true;//标记起点
queue.enqueue(s);//将它加入队列
while (!queue.isEmpty()){
int v=queue.dequeue();//从队列中删去下一个顶点
for(int w:G.adj(v)){
if(!marked[w]){//对于每个未被标记的相邻顶点
edgeTo[w]=v;//保存最短路径的最后一条边
marked[w]=true;//标记它，因为最短路径已知
queue.enqueue(w);//将它添加到队列中
}
}
}
}
public boolean hasPathTo(int v){//是否存在s到v的路径
return marked[v];
}
Iterable<Integer> pathTo(int v){//s到v的最短路径，如果不存在则返回null
if (!hasPathTo(v)) return null;
Stack<Integer> path=new Stack<>();
for(int x=v;x!=s;x=edgeTo[x]){
path.push(x);
}
path.push(s);
return path;
}
/*测试数据 6 8 0 5 2 4 2 3 1 2 0 1 3 4 3 5 0 2 0 */
public static void main(String[] args) {
In in = new In();
Graph G = new Graph(in);
int s = in.readInt();
BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);
for (int v = 0; v < G.V(); v++) {
if (bfs.hasPathTo(v)) {
System.out.printf("%d to %d: ", s, v);
for (int x : bfs.pathTo(v)) {
if (x == s) System.out.print(x);
else System.out.print("-" + x);
}
System.out.println();
}
else {
System.out.printf("%d to %d: not connected\n", s, v);
}
}
}
}
1.5连通分量
原理：
实现：
package graphs.undirectedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
public class CC {
private boolean[] marked;
private int[] id;//id[v]表示v属于哪个连通分量
private int count;//连通分量个数
public CC(Graph G){//预处理构造函数
marked=new boolean[G.V()];
id=new int[G.V()];
for(int s=0;s<G.V();s++){
if (!marked[s]){
dfs(G,s);
count++;
}
}
}
private void dfs(Graph G,int v){
marked[v]=true;
id[v]=count;
for(int w:G.adj(v)){
if (!marked[w])
dfs(G,w);
}
}
public boolean connected(int v,int w){//v和w连通吗？
return id[v]==id[w];
}
public int id(int v){//v所在的连通分量的标识符（0~count()-1）
return id[v];
}
public int count(){//连通分量数
return count;
}
/*测试数据 13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3 */
public static void main(String[] args) {
In in = new In();
Graph G = new Graph(in);
CC cc = new CC(G);
// number of connected components
int m = cc.count();
System.out.println(m + " components");
// compute list of vertices in each connected component
Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
for (int i = 0; i < m; i++) {
components[i] = new Queue<>();
}
for (int v = 0; v < G.V(); v++) {
components[cc.id(v)].enqueue(v);
}
// print results
for (int i = 0; i < m; i++) {
for (int v : components[i]) {
System.out.print(v + " ");
}
System.out.println();
}
}
}
2有向图
2.1有向图的表示
有向图的API:
实现：
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import fundamentals.Bag;
public class Digraph {
private final int V;//顶点数目
private int E;//边的数目
private Bag<Integer>[] adj;//领接表
private int[] indegree;// indegree[v] = indegree of vertex v ，入度
public Digraph(int V) {//创建一个含有v个顶点但不含有边的有向图
this.V = V;
this.E = 0;
indegree = new int[V];
adj = (Bag<Integer>[]) new Bag[V];//创建领接表
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
}
public Digraph(In in) {//从标准输入流in读入一幅图
this(in.readInt());//读取V并将图初始化
int E = in.readInt();//读取E
for (int i = 0; i < E; i++) {//添加一条边
int v = in.readInt();//读取一个顶点
int w = in.readInt();//读取另一个顶点
addEdge(v, w);//添加一条连接它们的边
}
}
public int V(){//顶点数
return V;
}
public int E(){//边数
return E;
}
public void addEdge(int v,int w){//向有向图中添加一条边v-w
adj[v].add(w);//将w添加到v的链表中
indegree[w]++;
E++;
}
public Iterable<Integer>adj(int v){//和v相邻的所有顶点
return adj[v];
}
public int outdegree(int v) {//v的出度
return adj[v].size();
}
public int indegree(int v) {//v的入度
return indegree[v];
}
public Digraph reverse() {
Digraph reverse = new Digraph(V);
for (int v = 0; v < V; v++) {
for (int w : adj(v)) {
reverse.addEdge(w, v);
}
}
return reverse;
}
public String toString() {//对象的字符串表示
StringBuilder s = new StringBuilder();
s.append(V + " vertices, " + E + " edges\n");
for (int v = 0; v < V; v++) {
s.append(String.format("%d: ", v));
for (int w : adj[v]) {
s.append(String.format("%d ", w));
}
s.append("\n");
}
return s.toString();
}
/*测试数据 13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6 */
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
System.out.println(G);
}
}
2.2有向图的可达性
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
public class DirectedDFS {
private boolean[] marked;
public DirectedDFS(Digraph G, int s){//在G中找到从s可达的所有顶点
marked=new boolean[G.V()];
dfs(G,s);
}
public DirectedDFS(Digraph G,Iterable<Integer> sources){//在G中找到从sources中的所有顶点可达的所有顶点
marked=new boolean[G.V()];
for (int s:sources){
if(!marked[s]) dfs(G,s);
}
}
private void dfs(Digraph G,int v){
marked[v]=true;
for (int w:G.adj(v)){
if (!marked[w]) dfs(G,w);
}
}
public boolean marked(int v){//v是可达的吗
return marked[v];
}
/*测试数据 13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6 2 */
public static void main(String[] args){
In in = new In();
Digraph G=new Digraph(in);
int s = in.readInt();
DirectedDFS rechable=new DirectedDFS(G,s);
for (int v = 0; v < G.V(); v++) {
if (rechable.marked(v))
System.out.print(v + " ");
}
System.out.println();
}
}
2.3有向图的寻路
与无向图中的寻路类似。
使用深度优先搜索解决“从s到给定目的顶点v是否存在一条有向路径？如果有。找出这条路径。”问题。
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
public class DepthFirstDirectedPaths {
private boolean[] marked;//这个顶点上调用过dfs()了吗？
private int[] edgeTo;//从起点到顶点的已知路径上的最后一个顶点
private final int s;//起点
public DepthFirstDirectedPaths(Digraph G, int s){//在G中找出所有起点为s的有向路径（非最短路径）
marked=new boolean[G.V()];
edgeTo=new int[G.V()];
this.s=s;
dfs(G,s);
}
private void dfs(Digraph G,int v){
marked[v]=true;
for(int w:G.adj(v)){
if(!marked[w]){
edgeTo[w]=v;
dfs(G,w);
}
}
}
public boolean hasPathTo(int v){//是否存在s到v的路径
return marked[v];
}
Iterable<Integer> pathTo(int v){//s到v的路径，如果不存在则返回null
if (!hasPathTo(v)) return null;
Stack<Integer> path=new Stack<>();
for(int x=v;x!=s;x=edgeTo[x]){
path.push(x);
}
path.push(s);
return path;
}
/*测试数据 13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6 3 */
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
int s = in.readInt();
DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s);
for (int v = 0; v < G.V(); v++) {
if (dfs.hasPathTo(v)) {
System.out.printf("%d to %d: ", s, v);
for (int x : dfs.pathTo(v)) {
if (x == s) System.out.print(x);
else System.out.print("-" + x);
}
System.out.println();
}
else {
System.out.printf("%d to %d: not connected\n", s, v);
}
}
}
}
使用广度优先搜索解决“从s到给定目的顶点v是否存在一条有向路径？如果有。找出其中最短的那条。”问题。
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
public class BreadthFirstDirectedPaths {
private static final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked;//到达该顶点的最短路径已知吗？
private int[] edgeTo;//到达该顶点的已知路径上的最后一个顶点
private final int s;//起点
private int[] distTo; // distTo[v] = length of shortest s->v path
public BreadthFirstDirectedPaths(Digraph G, int s){//在G中找出所有起点为s的有向路径（最短路径）
marked=new boolean[G.V()];
distTo = new int[G.V()];
edgeTo=new int[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = INFINITY;
this.s=s;
bfs(G,s);
}
private void bfs(Digraph G,int s){
Queue<Integer> queue=new Queue<>();
marked[s]=true;//标记起点
distTo[s] = 0;
queue.enqueue(s);//将它加入队列
while (!queue.isEmpty()){
int v=queue.dequeue();//从队列中删去下一个顶点
for(int w:G.adj(v)){
if(!marked[w]){//对于每个未被标记的相邻顶点
edgeTo[w]=v;//保存最短路径的最后一条边
distTo[w] = distTo[v] + 1;
marked[w]=true;//标记它，因为最短路径已知
queue.enqueue(w);//将它添加到队列中
}
}
}
}
public boolean hasPathTo(int v){//是否存在s到v的路径
return marked[v];
}
public int distTo(int v) {
return distTo[v];
}
Iterable<Integer> pathTo(int v){//s到v的最短路径，如果不存在则返回null
if (!hasPathTo(v)) return null;
Stack<Integer> path=new Stack<>();
for(int x=v;x!=s;x=edgeTo[x]){
path.push(x);
}
path.push(s);
return path;
}
/*测试数据 13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6 3 */
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
int s = in.readInt();
BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(G, s);
for (int v = 0; v < G.V(); v++) {
if (bfs.hasPathTo(v)) {
System.out.printf("%d to %d (%d): ", s, v, bfs.distTo(v));
for (int x : bfs.pathTo(v)) {
if (x == s) System.out.print(x);
else System.out.print("->" + x);
}
System.out.println();
}
else {
System.out.printf("%d to %d (-): not connected\n", s, v);
}
}
}
}
2.4寻找有向环
原理：
实现：
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
public class DirectedCycle {
private boolean[] marked;
private int[] edgeTo;
private boolean[] onStack; // onStack[v] = is vertex on the stack?
private Stack<Integer> cycle; // directed cycle (or null if no such cycle)
public DirectedCycle(Digraph G){//寻找有向环的构造函数
onStack=new boolean[G.V()];
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v] && cycle == null) dfs(G, v);
}
private void dfs(Digraph G,int v){
onStack[v]=true;
marked[v]=true;
for(int w:G.adj(v)){
// short circuit if directed cycle found
if(cycle!=null) return;
// found new vertex, so recur
else if(!marked[w]){
edgeTo[w]=v;
dfs(G,w);
}
// trace back directed cycle
else if(onStack[w]){
cycle=new Stack<>();
for(int x=v;x!=w;x=edgeTo[x]){
cycle.push(x);
}
cycle.push(w);
cycle.push(v);
}
}
onStack[v]=false;
}
public boolean hasCycle() {//G是否含有有向环
return cycle != null;
}
public Iterable<Integer> cycle() {//有向环中的所有顶点
return cycle;
}
/*测试数据 13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6 运行结果：Directed cycle: 3 5 4 3 */
/*测试数据 13 15 2 3 0 6 0 1 2 0 11 12 9 12 9 10 9 11 3 5 8 7 5 4 0 5 6 4 6 9 7 6 运行结果：No directed cycle*/
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
DirectedCycle finder = new DirectedCycle(G);
if (finder.hasCycle()) {
System.out.print("Directed cycle: ");
for (int v : finder.cycle()) {
System.out.print(v + " ");
}
System.out.println();
}
else {
System.out.println("No directed cycle");
}
System.out.println();
}
}
2.5拓扑排序
原理：
实现：
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
import graphs.shortestpaths.DirectedEdge;
import graphs.shortestpaths.EdgeWeightedDigraph;
public class DepthFirstOrder {
private boolean[] marked;
private Queue<Integer> pre;//所有顶点的前序排列,即dfs的调用顺序
private Queue<Integer> post;//所有顶点的后序排列，即顶点遍历完成的顺序
private Stack<Integer> reversePost;//所有顶点的逆后序排列
public DepthFirstOrder(Digraph G){
pre=new Queue<>();
post=new Queue<>();
reversePost=new Stack<>();
marked=new boolean[G.V()];
for(int v=0;v<G.V();v++){
if(!marked[v]) dfs(G,v);
}
}
public DepthFirstOrder(EdgeWeightedDigraph G) {
post = new Queue<Integer>();
pre = new Queue<Integer>();
reversePost=new Stack<>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v]) dfs(G, v);
}
private void dfs(Digraph G,int v){
pre.enqueue(v);
marked[v]=true;
for(int w:G.adj(v)){
if (!marked[w]) dfs(G,w);
}
post.enqueue(v);
reversePost.push(v);
}
private void dfs(EdgeWeightedDigraph G, int v) {
marked[v] = true;
pre.enqueue(v);
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (!marked[w]) {
dfs(G, w);
}
}
post.enqueue(v);
reversePost.push(v);
}
public Iterable<Integer> pre() {
return pre;
}
public Iterable<Integer> post() {
return post;
}
public Iterable<Integer> reversePost() {
return reversePost;
}
/* 13 15 2 3 0 6 0 1 2 0 11 12 9 12 9 10 9 11 3 5 8 7 5 4 0 5 6 4 6 9 7 6 */
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
DepthFirstOrder dfs = new DepthFirstOrder(G);
System.out.print("Preorder: ");
for (int v : dfs.pre()) {
System.out.print(v + " ");
}
System.out.println();
System.out.print("Postorder: ");
for (int v : dfs.post()) {
System.out.print(v + " ");
}
System.out.println();
System.out.print("Reverse postorder: ");
for (int v : dfs.reversePost()) {
System.out.print(v + " ");
}
System.out.println();
}
}
2.6有向图中的强连通性
Kosaraju算法原理：
实现:
package graphs.directedgraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
public class KosarajuSharirSCC {
private boolean[] marked; // marked[v] = has vertex v been visited?
private int[] id; // id[v] = id of strong component containing v
private int count; // number of strongly-connected components
public KosarajuSharirSCC(Digraph G) {
// compute reverse postorder of reverse graph
DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
// run DFS on G, using reverse postorder to guide calculation
marked = new boolean[G.V()];
id = new int[G.V()];
for (int v : dfs.reversePost()) {
if (!marked[v]) {
dfs(G, v);
count++;
}
}
}
// DFS on graph G
private void dfs(Digraph G, int v) {
marked[v] = true;
id[v] = count;
for (int w : G.adj(v)) {
if (!marked[w]) dfs(G, w);
}
}
public int count() {
return count;
}
public boolean stronglyConnected(int v, int w) {
return id[v] == id[w];
}
public int id(int v) {
return id[v];
}
/*测试数据 50 147 0 7 0 34 1 14 1 45 1 21 1 22 1 22 1 49 2 19 2 25 2 33 3 4 3 17 3 27 3 36 3 42 4 17 4 17 4 27 5 43 6 13 6 13 6 28 6 28 7 41 7 44 8 19 8 48 9 9 9 11 9 30 9 46 10 0 10 7 10 28 10 28 10 28 10 29 10 29 10 34 10 41 11 21 11 30 12 9 12 11 12 21 12 21 12 26 13 22 13 23 13 47 14 8 14 21 14 48 15 8 15 34 15 49 16 9 17 20 17 24 17 38 18 6 18 28 18 32 18 42 19 15 19 40 20 3 20 35 20 38 20 46 22 6 23 11 23 21 23 22 24 4 24 5 24 38 24 43 25 2 25 34 26 9 26 12 26 16 27 5 27 24 27 32 27 31 27 42 28 22 28 29 28 39 28 44 29 22 29 49 30 23 30 37 31 18 31 32 32 5 32 6 32 13 32 37 32 47 33 2 33 8 33 19 34 2 34 19 34 40 35 9 35 37 35 46 36 20 36 42 37 5 37 9 37 35 37 47 37 47 38 35 38 37 38 38 39 18 39 42 40 15 41 28 41 44 42 31 43 37 43 38 44 39 45 8 45 14 45 14 45 15 45 49 46 16 47 23 47 30 48 12 48 21 48 33 48 33 49 34 49 22 49 49 */
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
KosarajuSharirSCC scc = new KosarajuSharirSCC(G);
// number of connected components
int m = scc.count();
System.out.println(m + " strong components");
// compute list of vertices in each strong component
Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
for (int i = 0; i < m; i++) {
components[i] = new Queue<>();
}
for (int v = 0; v < G.V(); v++) {
components[scc.id(v)].enqueue(v);
}
// print results
for (int i = 0; i < m; i++) {
for (int v : components[i]) {
System.out.print(v + " ");
}
System.out.println();
}
}
}
3最小生成树
3.1原理
3.2加权无向图的表示
加权边的API:
实现：
package graphs.minimumspanningtrees;
//加权边
public class Edge implements Comparable<Edge> {
private final int v;//顶点之一
private final int w;//另一个顶点
private final double weight;//边的权重
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight() {
return weight;
}
public int either() {//边两端的顶点之一
return v;
}
public int other(int vertex) {//另一个顶点
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new RuntimeException("Inconsistent edge");
}
public int compareTo(Edge that) {
return Double.compare(this.weight, that.weight);
}
public String toString() {
return String.format("%d-%d %.5f", v, w, weight);
}
public static void main(String[] args) {
Edge e = new Edge(12, 34, 5.67);
System.out.println(e);
}
}
加权无向图的API:
实现：
package graphs.minimumspanningtrees;
import edu.princeton.cs.algs4.In;
import fundamentals.Bag;
//加权无向图
public class EdgeWeightedGraph {
private static final String NEWLINE = System.getProperty("line.separator");
private final int V;//顶点总数
private int E;//边的总数
private Bag<Edge>[] adj;//领接表
public EdgeWeightedGraph(int V) {//创建一幅含有V个顶点的空图
if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
}
public EdgeWeightedGraph(In in) {//从输入流中读取图
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public Iterable<Edge> adj(int v) {
return adj[v];
}
public int degree(int v) {
return adj[v].size();
}
public Iterable<Edge> edges() {
Bag<Edge> list = new Bag<>();
for (int v = 0; v < V; v++) {
int selfLoops = 0;
for (Edge e : adj(v)) {
if (e.other(v) > v) {
list.add(e);
}
// add only one copy of each self loop (self loops will be consecutive)
else if (e.other(v) == v) {
if (selfLoops % 2 == 0) list.add(e);
selfLoops++;
}
}
}
return list;
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/*测试数据 8 16 4 5 0.35 4 7 0.37 5 7 0.28 0 7 0.16 1 5 0.32 0 4 0.38 2 3 0.17 1 7 0.19 0 2 0.26 1 2 0.36 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
System.out.println(G);
}
}
3.3最小生成树的Prim算法
原理：
实现：
package graphs.minimumspanningtrees;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Queue;
//最小生成树的Prim算法的延时实现
public class LazyPrimMST {
private double weight; // total weight of MST
private Queue<Edge> mst; // edges in the MST
private boolean[] marked; // marked[v] = true if v on tree
private MinPQ<Edge> pq; // edges with one endpoint in tree
public LazyPrimMST(EdgeWeightedGraph G) {
mst = new Queue<>();
pq = new MinPQ<>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run Prim from all vertices to
if (!marked[v]) prim(G, v); // get a minimum spanning forest
}
// run Prim's algorithm
private void prim(EdgeWeightedGraph G, int s) {
scan(G, s);
while (!pq.isEmpty()) { // better to stop when mst has V-1 edges
Edge e = pq.delMin(); // smallest edge on pq
int v = e.either(), w = e.other(v); // two endpoints
if (marked[v] && marked[w]) continue; // lazy, both v and w already scanned
mst.enqueue(e); // add e to MST
weight += e.weight();
if (!marked[v]) scan(G, v); // v becomes part of tree
if (!marked[w]) scan(G, w); // w becomes part of tree
}
}
// add all edges e incident to v onto pq if the other endpoint has not yet been scanned
private void scan(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v))
if (!marked[e.other(v)]) pq.insert(e);
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
/*测试数据 8 16 4 5 0.35 4 7 0.37 5 7 0.28 0 7 0.16 1 5 0.32 0 4 0.38 2 3 0.17 1 7 0.19 0 2 0.26 1 2 0.36 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
LazyPrimMST mst = new LazyPrimMST(G);
for (Edge e : mst.edges()) {
System.out.println(e);
}
System.out.printf("%.5f\n", mst.weight());
}
}
3.4 最小生成树的Kruskal算法
原理：
实现：
package graphs.minimumspanningtrees;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.UF;
public class KruskalMST {
private double weight; // weight of MST
private Queue<Edge> mst = new Queue<>(); // edges in MST
public KruskalMST(EdgeWeightedGraph G) {
// more efficient to build heap by passing array of edges
MinPQ<Edge> pq = new MinPQ<>();
for (Edge e : G.edges()) {
pq.insert(e);
}
// run greedy algorithm
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.delMin();
int v = e.either();
int w = e.other(v);
if (!uf.connected(v, w)) { // v-w does not create a cycle
uf.union(v, w); // merge v and w components
mst.enqueue(e); // add edge e to mst
weight += e.weight();
}
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
/* 8 16 4 5 0.35 4 7 0.37 5 7 0.28 0 7 0.16 1 5 0.32 0 4 0.38 2 3 0.17 1 7 0.19 0 2 0.26 1 2 0.36 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
KruskalMST mst = new KruskalMST(G);
for (Edge e : mst.edges()) {
System.out.println(e);
}
System.out.printf("%.5f\n", mst.weight());
}
}
4最短路径
4.1加权有向图的表示
加权有向边的API:
实现：
package graphs.shortestpaths;
public class DirectedEdge {//加权有向边
private final int v;//边的起点
private final int w;//边的终点
private final double weight;//边的权重
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int from() {
return v;
}
public int to() {
return w;
}
public double weight() {
return weight;
}
public String toString() {
return v + "->" + w + " " + String.format("%5.2f", weight);
}
public static void main(String[] args) {
DirectedEdge e = new DirectedEdge(12, 34, 5.67);
System.out.println(e);
}
}
加权有向图的API:
实现：
package graphs.shortestpaths;
import edu.princeton.cs.algs4.In;
import fundamentals.Bag;
//加权有向图
public class EdgeWeightedDigraph {
private static final String NEWLINE = System.getProperty("line.separator");
private final int V; // number of vertices in this digraph
private int E; // number of edges in this digraph
private Bag<DirectedEdge>[] adj; // adj[v] = adjacency list for vertex v
private int[] indegree; // indegree[v] = indegree of vertex v
public EdgeWeightedDigraph(int V) {
if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
this.V = V;
this.E = 0;
this.indegree = new int[V];
adj = (Bag<DirectedEdge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<>();
}
public EdgeWeightedDigraph(In in) {
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
addEdge(new DirectedEdge(v, w, weight));
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(DirectedEdge e) {
int v = e.from();
int w = e.to();
adj[v].add(e);
indegree[w]++;
E++;
}
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
}
public int outdegree(int v) {
return adj[v].size();
}
public int indegree(int v) {
return indegree[v];
}
public Iterable<DirectedEdge> edges() {
Bag<DirectedEdge> list = new Bag<DirectedEdge>();
for (int v = 0; v < V; v++) {
for (DirectedEdge e : adj(v)) {
list.add(e);
}
}
return list;
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (DirectedEdge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/*测试数据 8 15 4 5 0.35 5 4 0.35 4 7 0.37 5 7 0.28 7 5 0.28 5 1 0.32 0 4 0.38 0 2 0.26 7 3 0.39 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
System.out.println(G);
}
}
4.2通用算法
基础：边的松弛
通用最短路径算法：
4.3Dijkstra算法（边权重非负的加权有向图）
原理：
实现：
package graphs.shortestpaths;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.Stack;
public class DijkstraSP {//最短路径的Dijkstra算法
private double[] distTo; // distTo[v] = distance of shortest s->v path
private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
private IndexMinPQ<Double> pq; // priority queue of vertices
public DijkstraSP(EdgeWeightedDigraph G, int s) {
for (DirectedEdge e : G.edges()) {
if (e.weight() < 0)
throw new IllegalArgumentException("edge " + e + " has negative weight");
}
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
// relax vertices in order of distance from s
pq = new IndexMinPQ<Double>(G.V());
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
// relax edge e and update pq if changed
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
/*测试数据 8 15 4 5 0.35 5 4 0.35 4 7 0.37 5 7 0.28 7 5 0.28 5 1 0.32 0 4 0.38 0 2 0.26 7 3 0.39 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
int s = in.readInt();
// compute shortest paths
DijkstraSP sp = new DijkstraSP(G, s);
// print shortest path
for (int t = 0; t < G.V(); t++) {
if (sp.hasPathTo(t)) {
System.out.printf("%d to %d (%.2f) ", s, t, sp.distTo(t));
for (DirectedEdge e : sp.pathTo(t)) {
System.out.print(e + " ");
}
System.out.println();
}
else {
System.out.printf("%d to %d no path\n", s, t);
}
}
}
}
4.4无环加权有向图的最短路径算法
原理：
实现：
package graphs.shortestpaths;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
import graphs.directedgraph.DepthFirstOrder;
public class AcyclicSP {//无环加权有向图的最短路径算法
private double[] distTo; // distTo[v] = distance of shortest s->v path
private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
public AcyclicSP(EdgeWeightedDigraph G, int s) {
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
DepthFirstOrder dfs = new DepthFirstOrder(G);
for (int v : dfs.reversePost()) {
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
// relax edge e
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
/*测试数据 8 13 5 4 0.35 4 7 0.37 5 7 0.28 5 1 0.32 4 0 0.38 0 2 0.26 3 7 0.39 1 3 0.29 7 2 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 */
public static void main(String[] args) {
In in = new In();
EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
int s =in.readInt();
// find shortest path from s to each other vertex in DAG
AcyclicSP sp = new AcyclicSP(G, s);
for (int v = 0; v < G.V(); v++) {
if (sp.hasPathTo(v)) {
System.out.printf("%d to %d (%.2f) ", s, v, sp.distTo(v));
for (DirectedEdge e : sp.pathTo(v)) {
System.out.print(e + " ");
}
System.out.println();
}
else {
System.out.printf("%d to %d no path\n", s, v);
}
}
}
}
4.5一般加权有向图中的最短路径问题（不含负权重环）
原理：
京公网安备 11010502036488号