liuxs981001 2018-02-07 09:27 采纳率: 0%
浏览 1241
已结题

Java图的强连通分量与最短路径

如何实现 下面两个类中的强连通分量(SCC)与最短路径（shortestPath)

 package graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

public class AdjacencyListGraph<T> extends Graph<T> {
    Map<T, Vertex> keyToVertex;

    private class Vertex {
        T key;
        List<Vertex> successors;
        List<Vertex> predecessors;

        Vertex(T key) {
            this.key = key;
            this.successors = new ArrayList<Vertex>();
            this.predecessors = new ArrayList<Vertex>();
        }
    }

    AdjacencyListGraph(Set<T> keys) {
        this.keyToVertex = new HashMap<T, Vertex>();
        for (T key : keys) {
            Vertex v = new Vertex(key);
            this.keyToVertex.put(key, v);
        }
    }

    @Override
    public int size() {
        return this.keyToVertex.size();
    }

    @Override
    public int numEdges() {
        int count = 0;
        for (Vertex v : this.keyToVertex.values()) {
            count += v.successors.size();
        }
        return count;
    }

    @Override
    public boolean addEdge(T from, T to) {
        if (!this.keyToVertex.containsKey(from)) {
            throw new NoSuchElementException("Could not find vertex with key " + from.toString());
        }
        if (!this.keyToVertex.containsKey(to)) {
            throw new NoSuchElementException("Could not find vertex with key " + to.toString());
        }
        Vertex fromV = this.keyToVertex.get(from);
        Vertex toV = this.keyToVertex.get(to);
        List<Vertex> fromSuccs = fromV.successors;
        List<Vertex> toPreds = toV.predecessors;
        if (fromSuccs.contains(toV)) {
            return false;
        }
        fromSuccs.add(toV);
        toPreds.add(fromV);
        return true;
    }

    @Override
    public boolean hasVertex(T key) {
        return this.keyToVertex.containsKey(key);
    }

    @Override
    public boolean hasEdge(T from, T to) throws NoSuchElementException {
        if (!this.keyToVertex.containsKey(from)) {
            throw new NoSuchElementException("Could not find vertex with key " + from.toString());
        }
        if (!this.keyToVertex.containsKey(to)) {
            throw new NoSuchElementException("Could not find vertex with key " + to.toString());
        }
        Vertex fromV = this.keyToVertex.get(from);
        Vertex toV = this.keyToVertex.get(to);
        List<Vertex> fromSuccs = fromV.successors;
        List<Vertex> toPreds = toV.predecessors;
        if (fromSuccs.contains(toV)) {
            return true;
        }
        return false;
    }

    @Override
    public boolean removeEdge(T from, T to) throws NoSuchElementException {
        if (!this.keyToVertex.containsKey(from)) {
            throw new NoSuchElementException("Could not find vertex with key " + from.toString());
        }
        if (!this.keyToVertex.containsKey(to)) {
            throw new NoSuchElementException("Could not find vertex with key " + to.toString());
        }
        Vertex fromV = this.keyToVertex.get(from);
        Vertex toV = this.keyToVertex.get(to);
        if (!this.hasEdge(from, to)) {
            return false;
        }
        List<Vertex> fromSuccs = fromV.successors;
        List<Vertex> toPreds = toV.predecessors;
        fromSuccs.remove(toV);
        toPreds.remove(fromV);
        if (!fromSuccs.contains(toV)) {
            return true;
        }
        return false;
    }

    @Override
    public int outDegree(T key) {
        return this.keyToVertex.get(key).successors.size();
    }

    @Override
    public int inDegree(T key) {
        return this.keyToVertex.get(key).predecessors.size();
    }

    @Override
    public Set<T> vertexSet() {
        Set<T> vertexSet = new HashSet<T>();
        for (T v : this.keyToVertex.keySet()) {
            vertexSet.add(v);
        }
        return vertexSet;
    }

    @Override
    public List<T> successorList(T key) {
        List<T> successorList = new ArrayList<T>();
        for (Vertex v : this.keyToVertex.get(key).successors) {
            successorList.add(v.key);
        }
        return successorList;
    }

    @Override
    public List<T> predecessorList(T key) {
        List<T> predecessorList = new ArrayList<T>();
        for (Vertex v : this.keyToVertex.get(key).predecessors) {
            predecessorList.add(v.key);
        }
        return predecessorList;
    }

    @Override
    public Iterator<T> successorIterator(T key) {
        return new theIterator(this.successorList(key));
    }

    @Override
    public Iterator<T> predecessorIterator(T key) {
        return new theIterator(this.predecessorList(key));
    }

    private class theIterator implements Iterator<T> {

        List<T> target;
        int index = 0;

        public theIterator(List<T> theList) {
            this.target = theList;
        }

        @Override
        public boolean hasNext() {
            return this.index < this.target.size();
        }

        @Override
        public T next() {
            if (hasNext()) {
                this.index += 1;
                return this.target.get(this.index - 1);
            }
            return null;
        }
    }

    @Override
    public Set<T> stronglyConnectedComponent(T key) {
        this.keyToVertex.get(key);
        // TODO
        return null;
    }

    @Override
    public List<T> shortestPath(T startLabel, T endLabel) {
        // TODO
        return null;
    }
}

以及

 package graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

public class AdjacencyMatrixGraph<T> extends Graph<T> {
    Map<T, Integer> keyToIndex;
    List<T> indexToKey;
    int[][] matrix;

    AdjacencyMatrixGraph(Set<T> keys) {
        int size = keys.size();
        this.keyToIndex = new HashMap<T, Integer>();
        this.indexToKey = new ArrayList<T>();
        this.matrix = new int[size][size];
        // need to populate keyToIndex and indexToKey with info from keys
        for (T each : keys) {
            this.indexToKey.add(each);
        }
        for (int i = 0; i < size; i++) {
            this.keyToIndex.put(this.indexToKey.get(i), i);
        }
    }

    @Override
    public int size() {
        return this.keyToIndex.size();
    }

    @Override
    public int numEdges() {
        int count = 0;
        for (int i = 0; i < this.matrix.length; i++) {
            for (int j = 0; j < this.matrix[i].length; j++) {
                count += this.matrix[i][j];
            }
        }
        return count;
    }

    @Override
    public boolean addEdge(T from, T to) {
        if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
            throw new NoSuchElementException();
        }
        int iFrom = this.keyToIndex.get(from);
        int iTo = this.keyToIndex.get(to);
        if (this.matrix[iFrom][iTo] == 1) {
            return false;
        }
        this.matrix[iFrom][iTo] = 1;
        return true;
    }

    @Override
    public boolean hasVertex(T key) {
        return this.keyToIndex.containsKey(key);
    }

    @Override
    public boolean hasEdge(T from, T to) throws NoSuchElementException {
        if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
            throw new NoSuchElementException();
        }
        int iFrom = this.keyToIndex.get(from);
        int iTo = this.keyToIndex.get(to);
        return this.matrix[iFrom][iTo] == 1;
    }

    @Override
    public boolean removeEdge(T from, T to) throws NoSuchElementException {
        if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
            throw new NoSuchElementException();
        }
        int iFrom = this.keyToIndex.get(from);
        int iTo = this.keyToIndex.get(to);
        if (this.matrix[iFrom][iTo] == 0) {
            return false;
        }
        this.matrix[iFrom][iTo] = 0;
        return true;
    }

    @Override
    public int outDegree(T key) {
        int iFrom = this.keyToIndex.get(key);
        int l = this.matrix[iFrom].length;
        int out = 0;
        for (int i = 0; i < l; i++) {
            out += this.matrix[iFrom][i];
        }
        return out;
    }

    @Override
    public int inDegree(T key) {
        int iTo = this.keyToIndex.get(key);
        int l = this.matrix.length;
        int in = 0;
        for (int i = 0; i < l; i++) {
            in += this.matrix[i][iTo];
        }
        return in;
    }

    @Override
    public Set<T> vertexSet() {
        Set<T> vertexSet = new HashSet<T>();
        for (T v : this.indexToKey) {
            vertexSet.add(v);
        }
        return vertexSet;
    }

    @Override
    public List<T> successorList(T key) {
        int iFrom = this.keyToIndex.get(key);
        List<T> successorList = new ArrayList<T>();
        for (int i = 0; i < this.matrix[iFrom].length; i++) {
            if (this.matrix[iFrom][i] == 1) {
                successorList.add(this.indexToKey.get(i));
            }
        }
        return successorList;
    }

    @Override
    public List<T> predecessorList(T key) {
        int iTo = this.keyToIndex.get(key);
        List<T> predecessorList = new ArrayList<T>();
        for (int i = 0; i < this.matrix.length; i++) {
            if (this.matrix[i][iTo] == 1) {
                predecessorList.add(this.indexToKey.get(i));
            }
        }
        return predecessorList;
    }

    @Override
    public Iterator<T> successorIterator(T key) {
        return new successorIterator(this.keyToIndex.get(key));
    }

    private class successorIterator implements Iterator<T> {

        int iFrom;
        int index = 0;

        public successorIterator(int iFrom) {
            this.iFrom = iFrom;
        }

        @Override
        public boolean hasNext() {
            while (true) {
                if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iFrom].length) {
                    return false;
                }
                if (AdjacencyMatrixGraph.this.matrix[this.iFrom][this.index] == 1) {
                    return true;
                }
                this.index++;
            }
        }

        @Override
        public T next() {
            if (hasNext()) {
                this.index++;
                return AdjacencyMatrixGraph.this.indexToKey.get(this.index - 1);
            }
            return null;
        }
    }

    @Override
    public Iterator<T> predecessorIterator(T key) {
        return new predecessorIterator(this.keyToIndex.get(key));
    }

    private class predecessorIterator implements Iterator<T> {

        int iTo;
        int index = 0;

        public predecessorIterator(int iTo) {
            this.iTo = iTo;
        }

        @Override
        public boolean hasNext() {
            while (true) {
                if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iTo].length) {
                    return false;
                }
                if (AdjacencyMatrixGraph.this.matrix[this.index][this.iTo] == 1) {
                    return true;
                }
                this.index++;
            }
        }

        @Override
        public T next() {
            if (hasNext()) {
                this.index += 1;
                return AdjacencyMatrixGraph.this.indexToKey.get(this.index);
            }
            return null;
        }
    }

    boolean[] visited = new boolean[this.size()];

    @Override
    public Set<T> stronglyConnectedComponent(T key) {
        // TODO
        return null;
    }

    @Override
    public List<T> shortestPath(T startLabel, T endLabel) {
        // TODO
        return null;
    }

}
  • 写回答

2条回答 默认 最新

报告相同问题？

悬赏问题

  • ¥20 fluent无法启动
  • ¥15 孟德尔随机化r语言运行问题
  • ¥15 pyinstaller编译的时候出现No module named 'imp'
  • ¥15 nirs_kit中打码怎么看(打码文件是csv格式)
  • ¥15 怎么把多于硬盘空间放到根目录下
  • ¥15 Matlab问题解答有两个问题
  • ¥15 LCD12864中文显示
  • ¥15 在使用CH341SER.EXE时不小心把所有驱动文件删除了怎么解决
  • ¥15 gsoap生成onvif框架
  • ¥15 有关sql server business intellige安装，包括SSDT、SSMS。