Реализация алгоритмов теории графов - PullRequest
0 голосов
/ 27 февраля 2019

Как создать и реализовать алгоритм генерации случайных графов.Повышение квалификации должно осуществляться сверху вниз, чтобы предоставить больше информации о соседях K-max.Числа K-min и K-max также указываются пользователем.Используйте, например, список смежности или аналогичный массив только в одном измерении, в котором хранится сгенерированный граф.Граф должен быть направлен ациклично.Номер вершины графа вставляется пользователем.Далее я приведу мой пример кода, который не является корректным для данного условия выше и может ли он быть переписан в соответствии с данными условиями?

import java.io.*; 
import java.util.*; 

class ShortestPath { 
    static final int INF=Integer.MAX_VALUE; 
    class AdjListNode { 
        private int v; 
        private int weight; 
        AdjListNode(int _v, int _w) { v = _v;  weight = _w; } 
        int getV() { return v; } 
        int getWeight()  { return weight; } 
    } 

    // Class to represent graph as an adjcency list of 
    // nodes of type AdjListNode 
    class Graph { 
        private int V; 
        private LinkedList<AdjListNode>adj[]; 
        Graph(int v) { 
            V=v; 
            adj = new LinkedList[V]; 
            for (int i=0; i<v; ++i) 
                adj[i] = new LinkedList<AdjListNode>(); 
        }

        void addEdge(int u, int v, int weight) { 
            AdjListNode node = new AdjListNode(v,weight); 
            adj[u].add(node);// Add v to u's list 
        } 

        // A recursive function used by shortestPath. 
        // See below link for details 
        void topologicalSortUtil(int v, Boolean visited[], Stack stack) { 
            // Mark the current node as visited. 
            visited[v] = true; 
            Integer i; 

            // Recur for all the vertices adjacent to this vertex 
            Iterator<AdjListNode> it = adj[v].iterator(); 
            while (it.hasNext()) { 
                AdjListNode node =it.next(); 
                if (!visited[node.getV()]) 
                    topologicalSortUtil(node.getV(), visited, stack); 
            } 
            // Push current vertex to stack which stores result 
            stack.push(new Integer(v)); 
        } 

        // The function to find shortest paths from given vertex. It 
        // uses recursive topologicalSortUtil() to get topological 
        // sorting of given graph. 
        void shortestPath(int s) { 
            Stack stack = new Stack(); 
            int dist[] = new int[V]; 

            // Mark all the vertices as not visited 
            Boolean visited[] = new Boolean[V]; 
            for (int i = 0; i < V; i++) 
                visited[i] = false; 

            // Call the recursive helper function to store Topological 
            // Sort starting from all vertices one by one 
            for (int i = 0; i < V; i++) 
                if (visited[i] == false) 
                    topologicalSortUtil(i, visited, stack); 

            // Initialize distances to all vertices as infinite and 
            // distance to source as 0 
            for (int i = 0; i < V; i++) 
                dist[i] = INF; 
            dist[s] = 0; 

            // Process vertices in topological order 
            while (stack.empty() == false) { 
                // Get the next vertex from topological order 
                int u = (int)stack.pop(); 

                // Update distances of all adjacent vertices 
                Iterator<AdjListNode> it; 
                if (dist[u] != INF) { 
                    it = adj[u].iterator(); 
                    while (it.hasNext()) { 
                        AdjListNode i= it.next(); 
                        if (dist[i.getV()] > dist[u] + i.getWeight()) 
                            dist[i.getV()] = dist[u] + i.getWeight(); 
                    } 
                } 
            } 

            // Print the calculated shortest distances 
            for (int i = 0; i < V; i++) { 
                if (dist[i] == INF) 
                    System.out.print( "INF "); 
                else
                    System.out.print( dist[i] + " "); 
            } 
        } 
    } 

    // Method to create a new graph instance through an object 
    // of ShortestPath class. 
    Graph newGraph(int number) { 
        return new Graph(number); 
    } 

    public static void main(String args[]) { 
        // Create a graph given in the above diagram.  Here vertex 
        // numbers are 0, 1, 2, 3, 4, 5 with following mappings: 
        // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z 
        ShortestPath t = new ShortestPath(); 
        Graph g = t.newGraph(6); 
        g.addEdge(0, 1, 5); 
        g.addEdge(0, 2, 3); 
        g.addEdge(1, 3, 6); 
        g.addEdge(1, 2, 2); 
        g.addEdge(2, 4, 4); 
        g.addEdge(2, 5, 2); 
        g.addEdge(2, 3, 7); 
        g.addEdge(3, 4, -1); 
        g.addEdge(4, 5, -2); 

        int s = 1; 
        System.out.println("Following are shortest distances "+ 
                            "from source " + s ); 
        g.shortestPath(s); 
    } 
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...