图
2019-01-20 本文已影响10人
低吟浅唱1990
一、基本概念
图是由一组顶点和一组能够将两个顶点相连的边组成的
- 度数表示某个顶点边的总数
- 路径是由边顺序连接的一系列顶点。
- 简单路径是一条没有重复顶点的路径
- 环是一条至少含有一条边且起点和终点相同的路径。
- 简单环是一条不含有重复顶点和边的环。
二、图的几种表示方法
- 邻接矩阵
我们可以使用一个V乘V的布尔矩阵。当顶点v和顶点w之间有相连接的边时，定义v行和w列的额元素值为true，否则为false。
image.png
- 邻接表
使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。
image.png
下面采用 邻接表来执行相关操作
public class Graph {
private static final String NEWLINE = System.getProperty("line.separator");
private int V;
private int E;
private Bag<Integer>[] adj; //邻接表数组 一个Bag对象一个链表
public Graph(int V) {
if (V<0)throw new IllegalArgumentException("Numbers of V must be > 0");
this.V = V;
this.E = 0;
this.adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0;v<V;v++){
adj[v] = new Bag<>();
}
}
public Graph(In in){ //输入输出流
this(in.readInt());
try {
int E = in.readInt();
if (E<0)throw new IllegalArgumentException("number of edges in a Grapha must be >0");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
System.out.println(v+"-->"+w);
addEdge(v,w);
}
}catch (NoSuchElementException e){
}
}
public int V(){
return V;
}
public int E(){
return E;
}
private void validateVertex(int v) {
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
public void addEdge(int v,int w){
validateVertex(v);
validateVertex(w);
E++;
((Bag<Integer>)adj[v]).add(w);
((Bag<Integer>)adj[w]).add(v);
}
public Iterable<Integer>adj(int v){
validateVertex(v);
return adj[v];
}
public int degree(int v){
validateVertex(v);
return adj[v].size();
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " vertices, " + E + " edges " + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
}
Graph graph = new Graph(4);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(0,3);
graph.addEdge(2,1);
graph.addEdge(2,3);
System.out.println(graph.toString());
>>>
4 vertices, 5 edges
0: 3 2 1
1: 2 0
2: 3 1 0
3: 2 0
三、深度优先搜索
image.png
首先我们从顶点A开始，坐上表示走过的记号后，面前有两条路，通向B和F，在领接表中规定选在最前面的顶点B点（或者使用向右），走到B点发现有三个路通向C，I和G。根据规则选择C点，.... 知道走到F点。在F点的时候，根据规则会选择A点，但是A点已经被标记了。所以回退，在选择G点。
public class DepthFirstSearch {
private boolean[] marked;
private int count;
public DepthFirstSearch(Graph G,int s){
marked = new boolean[G.V()];
dfs(G,s);
}
private void dfs(Graph G,int v){
count++;
marked[v] = true;
System.out.println("marked: "+v);
for (int w : G.adj(v)) {
if (!marked[w]){
dfs(G,w);
}
}
}
public boolean marked(int v){
return marked[v];
}
public int getCount(){
return count;
}
}
//
DepthFirstSearch search = new DepthFirstSearch(graph, 2);
for (int v = 0; v < graph.V(); v++) {
if (search.marked(v)){
System.out.print(v + " ");
}
}
marked: 2
marked: 3
marked: 0
marked: 1
0 1 2 3
四、广度优先搜索
public class BreadthFirstPaths {
private static final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked;
private int[] edgeTo;
private int[] distTo;
public BreadthFirstPaths(Graph graph,int s){
marked = new boolean[graph.V()];
distTo = new int[graph.V()];
edgeTo = new int[graph.V()];
bfs(graph,s);
}
private void bfs(Graph graph,int s){
Queue<Integer> q = new Queue<>();
for (int i = 0; i < graph.V(); i++) {
distTo[i] = INFINITY;
}
distTo[s] = 0;
marked[s] = true; // 0 被标记
q.enqueue(s);
while (!q.isEmpty()){ // 队列中就是上一个顶点里没有被标记的顶点
int v = q.dequeue();
for (int w : graph.adj(v)) { //遍历某个顶点的一条邻接表上的元素 把没有标记的放入队列中
if (!marked[w]){
edgeTo[w] = v;
distTo[w] = distTo[v]+1;
marked[w] = true; // 第一遍 2 1 5 被标记
System.out.println(w);
q.enqueue(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>path = new Stack<>();
int x;
for (x = v;distTo[x]!=0;x=edgeTo[x]){
path.push(x);
}
path.push(x);
System.out.println(path.toString());
return path;
}
}
Queue 和Stack前文中的队列和栈
BreadthFirstPaths bfs = new BreadthFirstPaths(graph,0);
for (int v = 0; v < graph.V(); v++) {
if (bfs.hasPathTo(v)) {
System.out.printf("%d to %d (%d): ", 0, v, bfs.distTo(v));
for (int x : bfs.pathTo(v)) {
if (x == 0) System.out.print(x);
else System.out.print("-" + x);
}
System.out.println();
}else {
System.out.printf("%d to %d (-): not connected\n", 0, v);
}
}
//构建图
6 vertices, 8 edges
0: 2 1 5
1: 0 2
2: 0 1 3 4
3: 2 4 5
4: 2 3
5: 0 3
//遍历图
0
2
1
5
3
4
//输出保存的路径
0 to 0 (0): 0
0
0 to 1 (1): 0 1
0-1
0 to 2 (1): 0 2
0-2
0 to 3 (2): 0 2 3
0-2-3
0 to 4 (2): 0 2 4
0-2-4
0 to 5 (1): 0 5
0-5
