有向图

在有向图中，边是单向的：每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的。

术语

定义：一幅有方向性的图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
出度：一个顶点的出度为由该顶点指出的边的总数。
入度：一个顶点的入度为指向该顶点的边的总数。
头：一条有向边的第一个顶点称为它的头。
尾：第二个顶点称为它的尾。

除了特殊的图，一幅有向图中的两个顶点的关系可能有4种：

• 没有边相连；
• 存在从v到w的边v->w；
• 存在从w到v的边w->v；
• 即存在v->w也存在w->v，即双向的连接。

有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。
有向环：为一条至少含有一条边且起点和终点相同的有向路径。
简单有向环：是一条不含有重复的顶点和边的环。
长度：路径或环的长度即为其中所包含的边数。

API

邻接表表示有向图

输入：

表示：

代码

Bag.java

package section1_3;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Bag<Item> implements Iterable<Item> {
private Node<Item> first;
private int n;
private class Node<Item> {
Item item;
Node<Item> next;
}
public Bag() {
first = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public void add(Item item) {
Node oldfirst = first;
first = new Node<>();
first.item = item;
first.next = oldfirst;
n++;
}
@Override
public Iterator<Item> iterator() {
return new LinkedIterator(first);
}
private class LinkedIterator implements Iterator<Item> {
private Node<Item> current;
public LinkedIterator(Node<Item> first) {
current = first;
}
public boolean hasNext()
{ return current != null;
}
public void remove()
{ throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}

Digraph.java

package section4_2;
import section1_3.Bag;
public class Digraph {
public final 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(int V, int E, int[][] data) {
this(V);
int e = E;
for (int i = 0;i < e;i++) {
int v = data[i][0];
int w = data[i][1];
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 + " edgesn";
for (int v = 0;v < V;v++) {
s += v + ": ";
for (int w : this.adj(v)) {
s += w + " ";
}
s += "n";
}
return s;
}
}

最后

以上就是土豪汽车为你收集整理的【alg4-图】有向图有向图的全部内容，希望文章能够帮你解决【alg4-图】有向图有向图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。