Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Archivierte Version vom 2015-11-03T20:26:25+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Graphen in Java

Graphen in Java

Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm

import java.util.InputMismatchException;
import java.util.Scanner;
 
public class Prims
{
    private final boolean unsettled[];
    private final boolean settled[];
    private final int numberofvertices;
    private final int adjacencyMatrix[][];
    private final int key[];
    public static final int INFINITE = 999;
    private final int parent[];
 
    public Prims(int numberofvertices)
    {
        this.numberofvertices = numberofvertices;
        unsettled = new boolean[numberofvertices + 1];
        settled = new boolean[numberofvertices + 1];
        adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
        key = new int[numberofvertices + 1];
        parent = new int[numberofvertices + 1];
    }
 
    public int getUnsettledCount(boolean unsettled[])
    {
        int count = 0;
        for (int index = 0; index < unsettled.length; index++)
        {
            if (unsettled[index])
            {
                count++;
            }
        }
        return count;
    }
 
    public void primsAlgorithm(int adjacencyMatrix[][])
    {
        int evaluationVertex;
        for (int source = 1; source <= numberofvertices; source++)
        {
            for (int destination = 1; destination <= numberofvertices; destination++)
            {
                this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
            }
        }
 
        for (int index = 1; index <= numberofvertices; index++)
        {
            key[index] = INFINITE;
        }
        key[1] = 0;
        unsettled[1] = true;
        parent[1] = 1;
 
        while (getUnsettledCount(unsettled) != 0)
        {
            evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
            unsettled[evaluationVertex] = false;
            settled[evaluationVertex] = true;
            evaluateNeighbours(evaluationVertex);
        }
    } 
 
    private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
    {
        int min = Integer.MAX_VALUE;
        int node = 0;
        for (int vertex = 1; vertex <= numberofvertices; vertex++)
        {
            if (unsettled[vertex] == true && key[vertex] < min)
            {
                node = vertex;
                min = key[vertex];
            }
        }
        return node;
    }
 
    public void evaluateNeighbours(int evaluationVertex)
    {
 
        for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
        {
            if (settled[destinationvertex] == false)
            {
                if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
                {
                    if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
                    {
                        key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
                        parent[destinationvertex] = evaluationVertex;
                    }
                    unsettled[destinationvertex] = true;
                }
            }
        }
    }
 
    public void printMST()
    {
        System.out.println("SOURCE  : DESTINATION = WEIGHT");
        for (int vertex = 2; vertex <= numberofvertices; vertex++)
        {
            System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
        }
    }
 
    public static void main(String... arg)
    {
        int adjacency_matrix[][];
        int number_of_vertices;
        Scanner scan = new Scanner(System.in);
 
        try
        {
            System.out.println("Enter the number of vertices");
            number_of_vertices = scan.nextInt();
            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
 
            System.out.println("Enter the Weighted Matrix for the graph");
            for (int i = 1; i <= number_of_vertices; i++)
            {
                for (int j = 1; j <= number_of_vertices; j++)
                {
                    adjacency_matrix[i][j] = scan.nextInt();
                    if (i == j)
                    {
                        adjacency_matrix[i][j] = 0;
                        continue;
                    }
                    if (adjacency_matrix[i][j] == 0)
                    {
                        adjacency_matrix[i][j] = INFINITE;
                    }
                }
            }
 
            Prims prims = new Prims(number_of_vertices);
            prims.primsAlgorithm(adjacency_matrix);
            prims.printMST();
 
        } catch (InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input Format");
        }
        scan.close();
    }
}

Lösung

//This is a java program to insert elements in a Binary Search Tree
import java.util.Scanner;
 
class BSTNode
{
    BSTNode left, right;
    int     data;
 
    public BSTNode()
    {
        left = null;
        right = null;
        data = 0;
    }
 
    public BSTNode(int n)
    {
        left = null;
        right = null;
        data = n;
    }
 
    public void setLeft(BSTNode n)
    {
        left = n;
    }
 
    public void setRight(BSTNode n)
    {
        right = n;
    }
 
    public BSTNode getLeft()
    {
        return left;
    }
 
    public BSTNode getRight()
    {
        return right;
    }
 
    public void setData(int d)
    {
        data = d;
    }
 
    public int getData()
    {
        return data;
    }
}
 
class BSTree
{
    private BSTNode root;
 
    public BSTree()
    {
        root = null;
    }
 
    public boolean isEmpty()
    {
        return root == null;
    }
 
    public void insert(int data)
    {
        root = insert(root, data);
    }
 
    private BSTNode insert(BSTNode node, int data)
    {
        if (node == null)
            node = new BSTNode(data);
        else
        {
            if (data <= node.getData())
                node.left = insert(node.left, data);
            else
                node.right = insert(node.right, data);
        }
        return node;
    }
 
    public void inorder()
    {
        inorder(root);
    }
 
    private void inorder(BSTNode r)
    {
        if (r != null)
        {
            inorder(r.getLeft());
            System.out.print(r.getData() + " ");
            inorder(r.getRight());
        }
    }
 
    public void preorder()
    {
        preorder(root);
    }
 
    private void preorder(BSTNode r)
    {
        if (r != null)
        {
            System.out.print(r.getData() + " ");
            preorder(r.getLeft());
            preorder(r.getRight());
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    private void postorder(BSTNode r)
    {
        if (r != null)
        {
            postorder(r.getLeft());
            postorder(r.getRight());
            System.out.print(r.getData() + " ");
        }
    }
}
 
public class Insertion_BST
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        BSTree bst = new BSTree();
        System.out.println("Binary Search Tree Insertion Test\n");
        int N = 10;
        for (int i = 0; i < N; i++)
        {
            bst.insert(scan.nextInt());
            System.out.print("\nPost order : ");
            bst.postorder();
            System.out.print("\nPre order  : ");
            bst.preorder();
            System.out.print("\nIn order   : ");
            bst.inorder();
        }
        scan.close();
    }
}

https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv

UBUNG

Grundidee: Die Adjazenzmatrix wird mit Hilfe einer zweidimensionalen Reihung dargestellt.

	AZ	BI	FT	KL	KO	MZ	RB	SP	TR
AZ	Details	Details 35	Details 36	Details 48	Details	Details 33	Details	Details	Details
BI	Details 35	Details	Details	Details	Details	Details 35	Details 28	Details	Details
FT	Details 36	Details	Details	Details 48	Details	Details	Details	Details 31	Details
KL	Details 48	Details	Details 48	Details	Details	Details	Details	Details	Details 116
KO	Details	Details	Details	Details	Details	Details	Details 54	Details	Details 128
MZ	Details 33	Details 35	Details	Details	Details	Details	Details	Details	Details
RB	Details	Details 28	Details	Details	Details 54	Details	Details	Details	Details 98
SP	Details	Details	Details 31	Details	Details	Details	Details	Details	Details
TR	Details	Details	Details	Details 116	Details 128	Details	Details 98	Details	Details

U2

Der folgende gerichtete Graph sei durch seine Kantenliste gegeben:
7, 10, 1, 7, 1, 4, 1, 5, 2, 1, 2, 3, 3, 6, 6, 5, 4, 5, 5, 2, 7, 4
Geben Sie die Adjazenzmatrix des Graphen an.

Ergänzung zum Graph-Interface:

public interface Graph{
public int addNode();
   public boolean addEdge(int orig, int dest);
   public Collection<Integer> getChildren(int node);!
}

Breitendurchlauf als Iterator:

public class BfsIterator implements Iterator<Integer>{
   private Graph g; 
   private Queue<Integer> q;
   private Set<Integer> visited;

   public BfsIterator(Graph g, int s){
      this.g = g;
      this.q = new LinkedList<Integer>();
      q.add(s);
      this.visited = new HashSet<Integer>();
   }

   public boolean hasNext() { return !this.q.isEmpty(); }

   public Integer next() {
      Integer n = this.q.poll();
      for(Integer m: this.g.getChildren(n))
           if(!this.visited.contains(m) && !this.q.contains(m))
             this.q.add(m);
      this.visited.add(n);
      return n;
   }
}

Übung zu Gozinto-Graphen

Zur Produktion eines Endproduktes A werden 4 Teile vom Typ B, 2 Teile Typ C, 3Teile Typ D und 1Teil vom Typ E benötigt. Typ E fließt mit je 1Teil auch noch in die Produktion von D und C ein. Ein weiterer Bautyp F fließt zu je 2Stk in die Produktion von C und mit je 1Stk in die Produktion von B ein.
1.Zeichne einen Gozinto-Graphen zu dem beschriebenen Sachverhalt.
2.Wir erhalten einen Auftrag und sollen 150A, 400B, 50C, 100D, 200E und 300F bereitstellen. Ermitteln sie den Gesamtbedarf für alle Teile der Produktionskette!

Übung Grundbegriffe der Graphentheorie 2

Inhaltsverzeichnis

Graphen in Java

Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm

UBUNG

U2

Ergänzung zum Graph-Interface:

Übung zu Gozinto-Graphen

Suche