数据结构：图（Java实现）


/**
 * 定义接口：Graph<V>
 * 定义所有类型的图的方法
 */
import java.util.List;

public interface Graph<V>{

    //返回图中的顶点数
    public int getSize();
    //返回图中的顶点（列表）
    public List<V> getVertices();
    //返回指定下标的顶点
    public V getVertex(int index);
    //返回指定顶点的下标
    public int getIndex(V v);
    //返回指定下标顶点的邻居（列表）----邻接顶点线性表的元素
    public List<Integer> getNeighbors(int index);
    //返回指定下标的度
    public int getDegree(int index);
    //打印边
    public void printEdges();
    //清除图
    public void clear();
    //增加顶点
    public boolean addVertex(V v);
    //增加边
    public boolean addEdge(int u, int v);
    //得到一个从指定下标v开始的深度优先搜索树
    public AbstractGraph<V>.Tree dfs(int v);
    //得到一个从指定下标v开始的广度优先搜索树
    public AbstractGraph<V>.Tree bfs(int v);

}

/**
 * 定义抽象类：AbstractGraph<V>
 * 部分实现接口中定义的方法
 */
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public abstract class AbstractGraph<V> implements Graph<V>{

    protected List<V> vertices = new ArrayList<>();//顶点集
    protected List<List<Edge>> neighbors = new ArrayList<>();//邻接边线性表存储边集
    
    /**构造方法 */
    protected AbstractGraph(){}
    protected AbstractGraph(V[] vertices,int[][] edges){
        for(int i=0; i<vertices.length; i++){
            addVertex(vertices[i]); //遍历顶点数组，将顶点加到顶点集中
        }
        createAdjacencyLists(edges,vertices.length);//创建邻接边线性表
    }
    protected AbstractGraph(List<V> vertices,List<Edge> edges){
        for(int i=0; i<vertices.size(); i++){
            addVertex(vertices.get(i));
        }
        createAdjacencyLists(edges, vertices.size());
    }
    
    /**创建邻接边线性表 */
    private void createAdjacencyLists(int[][] edges,int numberOfVertex){
        for(int i=0; i<edges.length; i++){
            addEdge(edges[i][0], edges[i][1]);
        }
    }
    private void createAdjacencyLists(List<Edge> edges,int numberOfVertex){
        for(int i=0; i<edges.size(); i++){
            addEdge(edges.get(i));
        }
    }

    /**返回图中的顶点数 */
    @Override 
    public int getSize() {
        return vertices.size();
    }
    /**返回图中的顶点（列表） */
    @Override
    public List<V> getVertices(){
        return vertices;
    }
    /**返回指定下标的顶点 */
    @Override
    public V getVertex(int index){
        return vertices.get(index);
    }
    /**返回指定顶点的下标 */
    @Override
    public int getIndex(V v) {
        return vertices.indexOf(v);
    }
    /**返回指定下标顶点的邻居（列表）----邻接顶点线性表的元素 */
    @Override
    public List<Integer> getNeighbors(int index){
        ArrayList<Integer> result = new ArrayList<>();
        for(Edge e: neighbors.get(index)){
            result.add(e.v);
        }
        return result;
    }
    /**返回指定下标的度 */
    @Override
    public int getDegree(int index) {
        return neighbors.get(index).size();
    }
    /**打印边 */
    @Override
    public void printEdges() {
        for(int i=0; i<vertices.size(); i++){
            System.out.print(vertices.get(i)+"("+i+"):");
            for(Edge e: neighbors.get(i)){
                System.out.print("("+e.u+","+e.v+") ");
            }
            System.out.println();
        }
    }
    /**清除图 */
    @Override
    public void clear() {
        vertices.clear();
        neighbors.clear();
    }
    /**增加顶点 */
    @Override
    public boolean addVertex(V v){
        if(vertices.contains(v)){
            return false;
        }
        else{
            vertices.add(v);
            neighbors.add(new ArrayList<>());
            return true;
        }
    }
    /**增加边 */
    @Override
    public boolean addEdge(int u,int v){
        return addEdge(new Edge(u,v));
    }
    public boolean addEdge(Edge e){
        if(e.u<0 || e.u>vertices.size()-1)throw new IllegalArgumentException("no such index:"+e.u);
        if(e.v<0 || e.v>vertices.size()-1)throw new IllegalArgumentException("no such index:"+e.v);
        if(neighbors.get(e.u).contains(e)){
            return false;
        }
        else{
            neighbors.get(e.u).add(e);
            return true;
        }
    }

    /**得到一个从指定下标v开始的深度优先搜索树 */
    @Override
    public Tree dfs(int v){
        int root = v;
        int[] parent = new int[vertices.size()];  
        List<Integer> searchOrder = new ArrayList<>();
        //创建追踪数组
        boolean[] isVisited = new boolean[vertices.size()];//检查该节点是否已被访问
        for(int i=0; i<vertices.size(); i++)    isVisited[i] = false;//初始化追踪数组
        for(int i=0; i<parent.length; i++)  parent[i] = -1;//初始化父节点数组

        dfs(v,parent,searchOrder,isVisited);

        return new Tree(root,parent,searchOrder);
    }
    public void dfs(int v,int[] parent, List<Integer> searchOrder,boolean[] isVisited){
        //遍历到下标为v的节点
        searchOrder.add(v);
        isVisited[v] = true;
        
        for(Integer w: getNeighbors(v)){
            if(! isVisited[w]){
                parent[w] = v;
                dfs(w, parent, searchOrder, isVisited);//递归搜索w的邻居节点
            }
        }
    }

    /**得到一个从指定下标v开始的广度优先搜索树 */
    @Override
    public Tree bfs(int v){
        int root = v;
        int[] parent = new int[vertices.size()];
        List<Integer> searchOrder = new ArrayList<>();

        boolean[] isVisited = new boolean[vertices.size()];//检查该节点是否已被访问
        for(int i=0; i<vertices.size(); i++)    isVisited[i] = false;//初始化追踪数组
        for(int i=0; i<parent.length; i++)  parent[i] = -1;//初始化父节点数组
        
        LinkedList<Integer> queue = new LinkedList<>();//创建一个空的队列
        //拜访根节点
        queue.offer(v); 
        isVisited[v] = true;

        //循环和队列实现按照由内到外的顺序 广度优先搜索
        while(!queue.isEmpty()){
            Integer u = queue.poll();
            searchOrder.add(u);
            for(Integer w: getNeighbors(u)){
                if(! isVisited[w]){
                    queue.offer(w);
                    parent[w] = u;
                    isVisited[w] = true;
                }
            }
        }

        return new Tree(root,parent,searchOrder);
    }

                /**定义内部类：Edge, 
                 * 将边定义为对象
                 * 根据首尾顶点下标创建  */
    public static class Edge{
        public int u;
        public int v;
        
        public Edge(int u,int v){
            this.u = u; this.v = v;
        }
        public boolean equals(Edge e){
            return u==e.u && v==e.v;
        }
    }
                /**定义内部类：Tree, 
                 * 描述节点的父子关系 
                 * 根据根、边、搜索顺序创建*/
    public class Tree{
        private int root;
        private int[] parent;
        private List<Integer> searchOrder;

        public Tree(int root,int[] parent,List<Integer> searchOrder){
            this.root = root;
            this.parent = parent;
            this.searchOrder = searchOrder;
        }
        public int getRoot(){
            return root;
        }
        public int getParent(int index){
            return parent[index];
        }
        public List<Integer> getSearchOrder(){
            return searchOrder;
        }
        //返回搜索到的顶点个数
        public int getNumberOfVerticesFound(){
            return searchOrder.size();
        }
        //返回一个从指定下标的顶点到根节点的顶点线性表(存储节点的列表)
        public List<V> getPath(int index){
            ArrayList<V> path = new ArrayList<>();

            while(index != -1){
                path.add(vertices.get(index));
                index = parent[index];
            }
            return path;
        }
        //显示一条从根节点到指定节点的路径(打印点)
        public void printPath(int index){
            List<V> path = getPath(index);
            System.out.println("A path from "+vertices.get(root)+
                                "to "+vertices.get(index)+":");

            for(int i=path.size()-1; i>=0 ;i--){
                System.out.print(path.get(i)+" ");
            }
        }
        //显示树的根节点和所有的边(打印根节点和边)
        public void printTree(){
            System.out.println("Root is:"+vertices.get(root));
            System.out.print("Edges is:");

            for(int i=0; i<parent.length; i++){
                if(parent[i] != -1){
                    System.out.print("("+vertices.get(parent[i])+","+
                                    vertices.get(i)+") ");
                }
            }
        }
    }
}

/**
 * 定义具体类：UnweightedGraph
 * 具体实现
 */
import java.util.List;

public class UnweightedGraph<V> extends AbstractGraph<V>{
    
    public UnweightedGraph(){}
    public UnweightedGraph(V[] vertices,int[][] edges){
        super(vertices, edges);
    }
    public UnweightedGraph(List<V> vertices,List<Edge> edges){
        super(vertices, edges);
    }
}

/**
 * 定义一个接口：Displayable
 * 定义获取x、y坐标以及顶点名字的方法
 */
public interface Displayable{
    public int getX();
    public int getY();
    public String getName();
}

/**
 * 定义一个展示Graph模型的面板类
 */
import java.util.*;

import javafx.scene.layout.Pane;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;

public class GraphView extends Pane{
    /**全局变量 */
    private Graph<? extends Displayable> graph;
    /**构造方法 */
    public GraphView(Graph<? extends Displayable> g){
        this.graph = g;

        //可视化顶点
        List<? extends Displayable> vertices = graph.getVertices();
        for(int i=0; i<graph.getSize(); i++){
            int x = vertices.get(i).getX();
            int y = vertices.get(i).getY();
            String name = vertices.get(i).getName();

            getChildren().add(new Circle(x, y, 16));
            getChildren().add(new Text(x-8, y-18, name));
        }

        //可视化边
        for(int i=0; i<graph.getSize(); i++){
            List<Integer> neighbor = graph.getNeighbors(i);
            int x1 = vertices.get(i).getX();
            int y1 = vertices.get(i).getY();
            for(Integer v: neighbor){
                int x2 = vertices.get(v).getX();
                int y2 = vertices.get(v).getY();

                getChildren().add(new Line(x1, y1, x2, y2));
            }
        }
    }
}

/**
 * 定义一个模型和视图的控制器类：DisplayUSMap
 */
import java.util.*;

import javafx.application.Application;
import javafx.stage.Stage;
import javafx.scene.Scene;

public class DisplayUSMap extends Application{
    @Override
    public void start(Stage primaryStage){
        City[] vertices = 
                {
                    new City(75, 50, "Seattle"),new City(50, 210, "San Francisco"),
                    new City(75, 275, "Los Angeles"),new City(275, 175, "Denver"),
                    new City(400, 245, "Kansas City"),new City(450, 100, "Chicago" ),
                    new City(700, 80, "Boston"),new City(675, 120, "New York"),
                    new City(575, 295, "Atlanta"),new City(600, 400, "Miami"),
                    new City(408, 325, "Dallas"),new City(450, 360, "Houston"),
                };
        int[][] edges = 
                {
                    {0,1},{0,3},{0,5},
                    {1,0},{1,2},{1,3},
                    {2,1},{2,3},{2,4},{2,10},
                    {3,0},{3,1},{3,2},{3,4},{3,5},
                    {4,2},{4,3},{4,5},{4,7},{4,8},{4,10},
                    {5,0},{5,3},{5,4},{5,6},{5,7},
                    {6,5},{6,7},
                    {7,4},{7,5},{7,6},{7,8},
                    {8,4},{8,7},{8,9},{8,10},{8,11},
                    {9,8},{9,11},
                    {10,2},{10,4},{10,8},{10,11},
                    {11,8},{11,9},{11,10},
                };

        Graph<City> mapGraph = new UnweightedGraph<>(vertices,edges);

        Scene scene = new Scene(new GraphView(mapGraph), 750, 450);
        primaryStage.setTitle("DisplayUSMap");
        primaryStage.setScene(scene);
        primaryStage.show();
    }
    /**
     * 定义一个内部类：City
     * 属性：位置和名字
     */
    public static class City implements Displayable{
        private int x,y;
        private String name;

        public City(int x,int y,String name){
            this.x = x;
            this.y = y;
            this.name = name;
        }
        @Override
        public int getX() {
            return x;
        }
        @Override
        public int getY() {
            return y;
        }
        @Override
        public String getName() {
            return name;
        }
     }
    // public static void main(String[] args) {
    //     launch(args);
    // }
}

图的可视化.png

/**
 *  定义类：加权边 
 */
public class WeightedEdge extends AbstractGraph.Edge
    implements Comparable<WeightedEdge>{
        public double weight;

        public WeightedEdge(int u,int v,double weight){
            super(u, v);
            this.weight = weight;
        }

        @Override 
        public int compareTo(WeightedEdge e){
            if(e.weight > weight)return -1;
            else if(e.weight == weight)return 0;
            else return 1;
        }
    }

/**
 * 定义类：有权图
 * 继承自 AbstractGraph<V>
 * 实现边对象具有权重属性
 */

import java.util.ArrayList;
import java.util.List;

public class WeightedGraph<V> extends AbstractGraph<V>{
    /**构造方法 */
    public WeightedGraph(){}
    public WeightedGraph(V[] vertices, int[][] edges){
        createWeightedGraph(vertices,edges);
    }
    public WeightedGraph(List<V> vertices,List<WeightedEdge> edges){
        createWeightedGraph(vertices, edges);
    }
    
    /**构建顶点线性表和邻接边线性表 */
    public void createWeightedGraph(V[] vertices, int[][] edges){
        for(int i=0; i<vertices.length; i++){
            addVertex(vertices[i]);
        }

        for(int i=0; i<edges.length; i++){
            addEdge(edges[i][0],edges[i][1],edges[i][2]);
        }
    }
    public void createWeightedGraph(List<V> vertices, List<WeightedEdge> edges){
        for(int i=0; i<vertices.size(); i++){
            addVertex(vertices.get(i));
        }

        for(int i=0; i<edges.size(); i++){
            addEdge(edges.get(i));
        }
    }
    /**得到指定边的权重 */
    public double getWeight(int u,int v)throws Exception{
        for(Edge e: neighbors.get(u)){
            if(e.v == v){
                return ((WeightedEdge)e).weight;
            }
        }

        throw new Exception("Edge doesn't exist!");
    }
    /**打印有权边 */
    public void printWeightedEdge(){

        for(int i=0; i<vertices.size(); i++){
            System.out.print(vertices.get(i)+"("+i+"):");
            for(Edge e: neighbors.get(i)){
                System.out.print("("+e.u+","+e.v+","+
                                ((WeightedEdge)e).weight+") ");
            }
            System.out.println();
        }
    }
    /**增加一条有权边 */
    public boolean addEdge(int u,int v,double weight){
        return addEdge(new WeightedEdge(u,v,weight));
    }

    public boolean addEdge(WeightedEdge e){
        if(e.u<0 || e.u>vertices.size()-1)throw new IllegalArgumentException("no such index:"+e.u);
        if(e.v<0 || e.v>vertices.size()-1)throw new IllegalArgumentException("no such index:"+e.v);
        if(e.weight < 0 )throw new IllegalArgumentException("no such weight:"+e.weight);
        if(neighbors.get(e.u).contains(e)){
            return false;
        }
        else{
            int key = 0;
            for(Edge edge: neighbors.get(e.u)){
                if(edge.equals(e))
                    {((WeightedEdge)edge).weight = e.weight;key=1;}
            }
            if(key == 0) neighbors.get(e.u).add(e);
            return true;
        }
    }

    /**得到有权图的最小生成树 */
    public MST getMinimumSpanningTree(){//默认节点
        return getMinimumSpanningTree(0);
    }
    public MST getMinimumSpanningTree(int startingVertex){//指定节点

        //初始化
        List<Integer> T = new ArrayList<>();//已加入生成树的节点线性表
        int[] parent = new int[getSize()];
            for(int i=0; i<parent.length; i++)parent[i] = -1;
        double totalWeight = 0;
        double[] cost = new double[getSize()];//每个节点的开销
            //注意：这里的开销指的是：这个顶点邻接到T中某个顶点具有的最小开销
            for(int i=0; i<cost.length; i++)cost[i] = Double.POSITIVE_INFINITY;
        cost[startingVertex] = 0;

        //从T以外的节点向T加入新节点，贪婪算法，局部最优使得整体最优
        while(T.size() < getSize()){
            double minimumCost = Double.POSITIVE_INFINITY;
            int u = -1;
            for(int i=0; i<cost.length; i++){   //找到不在T中且开销最小的节点
                if(!T.contains(i) && minimumCost > cost[i]){
                    minimumCost = cost[i]; u = i;
                }
            }
            T.add(u);   totalWeight+=minimumCost;//将该节点移入T中
            // parent[u] = -1;

            for(Edge e: neighbors.get(u)){//更新节点的开销和在最小生成树中的父节点
                if(cost[e.v] > ((WeightedEdge)e).weight){
                    cost[e.v] = ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        }

        return new MST(startingVertex,parent,T,totalWeight);
    }

    /**
     * 得到源到所有顶点的最短路径树 
     * 贪婪算法和动态编程的结合
    */
    public ShortestPathTree getShortestPath(){
        return getShortestPath(0);
    }
    public ShortestPathTree getShortestPath(int sourceVertex){
        //初始化
        List<Integer> T = new ArrayList<>();//已得到最短路径的节点
        int[] parent = new int[getSize()];
            for(int i=0; i<parent.length; i++)parent[i] = -1;
        double[] cost = new double[getSize()];//源到每个节点的开销
            //注意：这里的开销指的是：这个顶点邻接到T中某个顶点，并具有到源顶点的最小开销
            for(int i=0; i<cost.length; i++)cost[i] = Double.POSITIVE_INFINITY;
        cost[sourceVertex] = 0;

        //从T以外的节点向T加入新节点
        while(T.size() < getSize()){
            double minimumCost = Double.POSITIVE_INFINITY;
            int u = -1;
            for(int i=0; i<cost.length; i++){   //找到不在T中且开销最小的节点
                if(!T.contains(i) && minimumCost > cost[i]){
                    minimumCost = cost[i]; u = i;
                }
            }
            T.add(u);//将该节点移入T中

            for(Edge e: neighbors.get(u)){//更新节点的开销和在最小生成树中的父节点
                if(cost[e.v] > cost[u] + ((WeightedEdge)e).weight){
                    cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
                    parent[e.v] = u;
                }
            }
        }

        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

                    /**定义内部类：MST,
                     * 继承自AbstractGraph.Tree
                     * 用于描述最小生成树
                     */
    public class MST extends Tree{
        private double totalWeight;

        public MST(int root,int[] parent, List<Integer> searchOrder,double totalWeight){
            super(root, parent, searchOrder);
            this.totalWeight = totalWeight;
        }

        public double getTotalWeight(){
            return totalWeight;
        }
    }

                    /**定义内部类：ShortestPathTree
                     * 继承自AbstractGraph.Tree
                     * 用于描述最短路径
                     */
    public class ShortestPathTree extends Tree{
        private double[] cost;//存储从源到目的的开销

        public ShortestPathTree(int source,int[] parent, List<Integer> searchOrder,double[] cost){
            super(source, parent, searchOrder);
            this.cost = cost;
        }
        //得到从源到目的的开销
        public double getCost(int v){
            return cost[v];
        }
        //显示从源顶点开始的所有路径
        public void printAllPaths(){
            for(int i=0; i<vertices.size(); i++){
                printPath(i);//单条路径
                System.out.println("(cost: "+cost[i]+")");
            }
        }
    }
}

数据结构：图 （Java实现）

数据结构：图（Java实现）