内容简介：《Algorithm》（Sedgewick）笔记：有向图一幅有称一条有向边由第一个顶点
《Algorithm》（Sedgewick）笔记：有向图
术语
一幅有 方向性的图 （或 有向图 ）是由一组 顶点 和一组 有方向的边 组成的，每条有方向的边都连接着有序的一对顶点。
称一条有向边由第一个顶点 指出 并 指向 第二个顶点。
一个顶点的 出度 为由该顶点指出的边的总数，一个顶点的 入度 为指向该顶点的边的总数。
一条有向边的第一个顶点成为它的 头 ，第二个顶点称为它的 尾 。
在一幅有向图中， 有向路径 由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。
有向环为一条至少含有一条边且起点和终点相同的有向路径。 简单有向环 是一条除了起点和终点必须相同之外，不含有重复的顶点和边的环。
路径或环的 长度 即为其中所包含的边数。
图示
表示
使用邻接表表示
数据类型
public class DiGraph {
private int V;
private int E;
private Bag<Integer>[] adj;
public DiGraph(int 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 DiGraph() {
Scanner in = new Scanner(System.in);
V = in.nextInt();
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<Integer>();
int e = in.nextInt();
for (int i = 0; i < e; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
public DiGraph reverse() {
DiGraph R = new DiGraph(V);
for (int v = 0; v < V; v++)
for (int w : adj[v])
R.addEdge(w, v);
return R;
}
public String toString() {
String s = V + " vertices, " + E + " edges\n";
for (int v = 0; v < V; v++) {
s += v + ": ";
for (int w : this.adj[v])
s += w + " ";
s += "\n";
}
return s;
}
}
源代码
有向图的深度优先搜索
图示
使用
使用DFS可以检测有向图的可达性，即解决“是否存在一条从s到达给定顶点v的有向路径”或“是否存在一条从结合中的任意顶点到达给定顶点v的有向路径”等问题。
递归代码
public class DiDFS {
private boolean[] marked;
//单源
public DiDFS(DiGraph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
//多源
public DiDFS(DiGraph G, Iterable<Integer> 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) {
return marked[v];
}
}
非递归代码
public class DiDFS_Nonrecur {
private boolean[] marked;
public DiDFS_Nonrecur(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<>();
marked[s] = true;
stack.push(s);
while (!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 DiDFS_Nonrecur(DiGraph G,Iterable<Integer> sources) {
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();
}
for (int s : sources) {
Stack<Integer> stack = new Stack<>();
marked[s] = true;
stack.push(s);
while (!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 class DiDFSPath {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DiDFSPath(DiGraph G, int 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) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> stack = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
stack.push(x);
}
stack.push(s);
Queue<Integer> queue = new LinkedList<>();
while (!stack.isEmpty()) {
queue.offer(stack.pop());
}
return queue;
}
}
源代码
广度优先搜索路径
代码
public class DiBFSPath {
private final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked;
private int [] edgeTo;
private int[] distTo;
private int s;
public DiBFSPath(DiGraph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
distTo = new int[G.V()];
this.s = s;
for (int v = 0; v < G.V(); v++) {
distTo[v] = INFINITY;
}
bfs(G, s);
}
private void bfs(DiGraph G, int s) {
Queue<Integer> q = new LinkedList<>();
q.offer(s);
marked[s] = true;
distTo[s] = 0;
while (!q.isEmpty()) {
int v = q.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
marked[w] = true;
distTo[w] = distTo[v] + 1;
edgeTo[w] = v;
q.offer(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public int distTo(int v) {
return distTo[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> stack = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
stack.push(x);
}
stack.push(s);
Queue<Integer> queue = new LinkedList<>();
while (!stack.isEmpty()) {
queue.offer(stack.pop());
}
return queue;
}
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
