邻接表
单源路径问题
上面的问题只能从根节点0出发才能找到原来的路径
Java实现单源路径问题
Graph类
import java.io.File;
import java.io.IOException;
import java.util.TreeSet;
import java.util.Scanner;
/// 暂时只支持无向无权图
public class Graph {
private int V;
private int E;
private TreeSet<Integer>[] adj;
public Graph(String filename){
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be non-negative");
adj = new TreeSet[V];
for(int i = 0; i < V; i ++)
adj[i] = new TreeSet<Integer>();
E = scanner.nextInt();
if(E < 0) throw new IllegalArgumentException("E must be non-negative");
for(int i = 0; i < E; i ++){
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if(a == b) throw new IllegalArgumentException("Self Loop is Detected!");
if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected!");
adj[a].add(b);
adj[b].add(a);
}
}
catch(IOException e){
e.printStackTrace();
}
}
private void validateVertex(int v){
if(v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + "is invalid");
}
public int V(){
return V;
}
public int E(){
return E;
}
public boolean hasEdge(int v, int w){
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
public Iterable<Integer> adj(int v){
validateVertex(v);
return adj[v];
}
public int degree(int v){
validateVertex(v);
return adj[v].size();
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n", V, E));
for(int v = 0; v < V; v ++){
sb.append(String.format("%d : ", v));
for(int w : adj[v])
sb.append(String.format("%d ", w));
sb.append('\n');
}
return sb.toString();
}
public static void main(String[] args){
Graph g = new Graph("g.txt");
System.out.print(g);
}
}
import java.io.File;
import java.io.IOException;
import java.util.TreeSet;
import java.util.Scanner;
/// 暂时只支持无向无权图
public class Graph {
private int V;
private int E;
private TreeSet<Integer>[] adj;
public Graph(String filename){
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be non-negative");
adj = new TreeSet[V];
for(int i = 0; i < V; i ++)
adj[i] = new TreeSet<Integer>();
E = scanner.nextInt();
if(E < 0) throw new IllegalArgumentException("E must be non-negative");
for(int i = 0; i < E; i ++){
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if(a == b) throw new IllegalArgumentException("Self Loop is Detected!");
if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected!");
adj[a].add(b);
adj[b].add(a);
}
}
catch(IOException e){
e.printStackTrace();
}
}
public void validateVertex(int v){
if(v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + "is invalid");
}
public int V(){
return V;
}
public int E(){
return E;
}
public boolean hasEdge(int v, int w){
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
public Iterable<Integer> adj(int v){
validateVertex(v);
return adj[v];
}
public int degree(int v){
validateVertex(v);
return adj[v].size();
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n", V, E));
for(int v = 0; v < V; v ++){
sb.append(String.format("%d : ", v));
for(int w : adj[v])
sb.append(String.format("%d ", w));
sb.append('\n');
}
return sb.toString();
}
public static void main(String[] args){
Graph g = new Graph("g.txt");
System.out.print(g);
}
}
Python实现单源路径问题
无权图的最短路径问题
USSSPath
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
// 无权图最短路径
// Unweighted Single Source Shortest Path
public class USSSPath {
private Graph G;
private int s;
private boolean[] visited;
private int[] pre;
private int[] dis;
public USSSPath(Graph G, int s){
this.G = G;
this.s = s;
visited = new boolean[G.V()];
pre = new int[G.V()];
dis = new int[G.V()];
for(int i = 0; i < G.V(); i ++) {
pre[i] = -1;
dis[i] = -1;
}
bfs(s);
for(int i = 0; i < G.V(); i ++)
System.out.print(dis[i] + " ");
System.out.println();
}
private void bfs(int s){
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
pre[s] = s;
dis[s] = 0;
while(!queue.isEmpty()){
int v = queue.remove();
for(int w: G.adj(v))
if(!visited[w]){
queue.add(w);
visited[w] = true;
pre[w] = v;
dis[w] = dis[v] + 1;
}
}
}
public boolean isConnectedTo(int t){
G.validateVertex(t);
return visited[t];
}
public int dis(int t){
G.validateVertex(t);
return dis[t];
}
public Iterable<Integer> path(int t){
ArrayList<Integer> res = new ArrayList<Integer>();
if(!isConnectedTo(t)) return res;
int cur = t;
while(cur != s){
res.add(cur);
cur = pre[cur];
}
res.add(s);
Collections.reverse(res);
return res;
}
public static void main(String[] args){
Graph g = new Graph("g.txt");
USSSPath ussspath = new USSSPath(g, 0);
System.out.println("0 -> 6 : " + ussspath.path(6));
System.out.println("0 -> 6 : " + ussspath.dis(6));
}
}
网友评论