Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Archivierte Version vom 2015-11-04T11:34:34+00:00. Aktuelle Version

Inhaltsverzeichnis

1 '''Graphen in Java'''
2 ''' Aufgaben'''
- 2.1 '''Aufgabe1'''
- 2.1 Übung zu Gozinto-Graphen

Sie sollen diese JAVA-Klasse in Netbeans oder Eclipse benutzen. Sie sollen nur richtige Eingaben im Konsole (oben) schreiben :)
Wenn Sie die Fragen haben , probiere ich verschaffen . Viel Erfolg!

Graphen in Java

Algorithmus =

https://www.youtube.com/embed/6hfOvs8pY1k

Algorithmus von Prim

Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.
https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv

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

Zusätzliche Informationen

https://www.youtube.com/watch?v=Pn874kEc3IA

Create a Balanced Binary Tree of the Incoming Data

//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();
    }
}

2. MOEGLICHKEIT

//This is a java program to make a self balancing binary tree for the input data
import java.util.Scanner;
 
class SBBSTNodes
{
    SBBSTNodes left, right;
    int        data;
    int        height;
 
    public SBBSTNodes()
    {
        left = null;
        right = null;
        data = 0;
        height = 0;
    }
 
    public SBBSTNodes(int n)
    {
 
        left = null;
        right = null;
        data = n;
        height = 0;
    }
}
 
class SelfBalancingBinarySearchTrees
{
    private SBBSTNodes root;
 
    public SelfBalancingBinarySearchTrees()
    {
        root = null;
    }
 
    public boolean isEmpty()
    {
        return root == null;
    }
 
    public void clear()
    {
        root = null;
    }
 
    public void insert(int data)
    {
        root = insert(data, root);
    }
 
    private int height(SBBSTNodes t)
    {
 
        return t == null ? -1 : t.height;
    }
 
    private int max(int lhs, int rhs)
    {
        return lhs > rhs ? lhs : rhs;
    }
 
    private SBBSTNodes insert(int x, SBBSTNodes t)
    {
        if (t == null)
            t = new SBBSTNodes(x);
        else if (x < t.data)
        {
            t.left = insert(x, t.left);
            if (height(t.left) - height(t.right) == 2)
                if (x < t.left.data)
                    t = rotateWithLeftChild(t);
                else
                    t = doubleWithLeftChild(t);
        } else if (x > t.data)
        {
            t.right = insert(x, t.right);
            if (height(t.right) - height(t.left) == 2)
                if (x > t.right.data)
                    t = rotateWithRightChild(t);
                else
                    t = doubleWithRightChild(t);
        } else
            ;
        t.height = max(height(t.left), height(t.right)) + 1;
        return t;
    }
 
    private SBBSTNodes rotateWithLeftChild(SBBSTNodes k2)
    {
        SBBSTNodes k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;
    }
 
    private SBBSTNodes rotateWithRightChild(SBBSTNodes k1)
    {
        SBBSTNodes k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;
        return k2;
    }
 
    private SBBSTNodes doubleWithLeftChild(SBBSTNodes k3)
    {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }
 
    private SBBSTNodes doubleWithRightChild(SBBSTNodes k1)
    {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }
 
    public int countNodes()
    {
        return countNodes(root);
    }
 
    private int countNodes(SBBSTNodes r)
    {
        if (r == null)
            return 0;
        else
        {
            int l = 1;
            l += countNodes(r.left);
            l += countNodes(r.right);
            return l;
        }
    }
 
    public boolean search(int val)
    {
        return search(root, val);
    }
 
    private boolean search(SBBSTNodes r, int val)
    {
        boolean found = false;
        while ((r != null) && !found)
        {
            int rval = r.data;
            if (val < rval)
                r = r.left;
            else if (val > rval)
                r = r.right;
            else
            {
                found = true;
                break;
            }
            found = search(r, val);
        }
        return found;
    }
 
    public void inorder()
    {
        inorder(root);
    }
 
    private void inorder(SBBSTNodes r)
    {
        if (r != null)
        {
            inorder(r.left);
            System.out.print(r.data + " ");
            inorder(r.right);
        }
    }
 
    public void preorder()
    {
 
        preorder(root);
    }
 
    private void preorder(SBBSTNodes r)
    {
        if (r != null)
        {
            System.out.print(r.data + " ");
            preorder(r.left);
            preorder(r.right);
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    private void postorder(SBBSTNodes r)
    {
        if (r != null)
        {
            postorder(r.left);
            postorder(r.right);
            System.out.print(r.data + " ");
        }
    }
}
 
public class Balanced_B_Tree
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
 
        SelfBalancingBinarySearchTrees sbbst = new SelfBalancingBinarySearchTrees();
        System.out.println("Self Balancing Tree\n");
 
        int N = 10;
        for (int i = 0; i < N; i++)
            sbbst.insert(scan.nextInt());
 
        System.out.println("\nPre-order  :");
        sbbst.preorder();
        System.out.println("\nIn-order   :");
        sbbst.inorder();
        System.out.println("\nPost-order :");
        sbbst.postorder();
        scan.close();
    }
}

Implement Binary Tree

/*
 *  Java Program to Implement Binary Tree
 */
 
 import java.util.Scanner;
 
 /* Class BTNode */
 class BTNode
 {    
     BTNode left, right;
     int data;
 
     /* Constructor */
     public BTNode()
     {
         left = null;
         right = null;
         data = 0;
     }
     /* Constructor */
     public BTNode(int n)
     {
         left = null;
         right = null;
         data = n;
     }
     /* Function to set left node */
     public void setLeft(BTNode n)
     {
         left = n;
     }
     /* Function to set right node */ 
     public void setRight(BTNode n)
     {
         right = n;
     }
     /* Function to get left node */
     public BTNode getLeft()
     {
         return left;
     }
     /* Function to get right node */
     public BTNode getRight()
     {
         return right;
     }
     /* Function to set data to node */
     public void setData(int d)
     {
         data = d;
     }
     /* Function to get data from node */
     public int getData()
     {
         return data;
     }     
 }
 
 /* Class BT */
 class BT
 {
     private BTNode root;
 
     /* Constructor */
     public BT()
     {
         root = null;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty()
     {
         return root == null;
     }
     /* Functions to insert data */
     public void insert(int data)
     {
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private BTNode insert(BTNode node, int data)
     {
         if (node == null)
             node = new BTNode(data);
         else
         {
             if (node.getRight() == null)
                 node.right = insert(node.right, data);
             else
                 node.left = insert(node.left, data);             
         }
         return node;
     }     
     /* Function to count number of nodes */
     public int countNodes()
     {
         return countNodes(root);
     }
     /* Function to count number of nodes recursively */
     private int countNodes(BTNode r)
     {
         if (r == null)
             return 0;
         else
         {
             int l = 1;
             l += countNodes(r.getLeft());
             l += countNodes(r.getRight());
             return l;
         }
     }
     /* Function to search for an element */
     public boolean search(int val)
     {
         return search(root, val);
     }
     /* Function to search for an element recursively */
     private boolean search(BTNode r, int val)
     {
         if (r.getData() == val)
             return true;
         if (r.getLeft() != null)
             if (search(r.getLeft(), val))
                 return true;
         if (r.getRight() != null)
             if (search(r.getRight(), val))
                 return true;
         return false;         
     }
     /* Function for inorder traversal */
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(BTNode r)
     {
         if (r != null)
         {
             inorder(r.getLeft());
             System.out.print(r.getData() +" ");
             inorder(r.getRight());
         }
     }
     /* Function for preorder traversal */
     public void preorder()
     {
         preorder(root);
     }
     private void preorder(BTNode r)
     {
         if (r != null)
         {
             System.out.print(r.getData() +" ");
             preorder(r.getLeft());             
             preorder(r.getRight());
         }
     }
     /* Function for postorder traversal */
     public void postorder()
     {
         postorder(root);
     }
     private void postorder(BTNode r)
     {
         if (r != null)
         {
             postorder(r.getLeft());             
             postorder(r.getRight());
             System.out.print(r.getData() +" ");
         }
     }     
 }
 
 /* Class BinaryTree */
public class BinaryTree
 {
     public static void main(String[] args)
    {            
        Scanner scan = new Scanner(System.in);
        /* Creating object of BT */
        BT bt = new BT(); 
        /*  Perform tree operations  */
        System.out.println("Binary Tree Test\n");          
        char ch;        
        do    
        {
            System.out.println("\nBinary Tree Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. search");
            System.out.println("3. count nodes");
            System.out.println("4. check empty");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                bt.insert( scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("Enter integer element to search");
                System.out.println("Search result : "+ bt.search( scan.nextInt() ));
                break;                                          
            case 3 : 
                System.out.println("Nodes = "+ bt.countNodes());
                break;     
            case 4 : 
                System.out.println("Empty status = "+ bt.isEmpty());
                break;            
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /*  Display tree  */ 
            System.out.print("\nPost order : ");
            bt.postorder();
            System.out.print("\nPre order : ");
            bt.preorder();
            System.out.print("\nIn order : ");
            bt.inorder();
 
            System.out.println("\n\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
 }

Find Number of Spanning Trees in a Complete Bipartite Graph

1. Import Scanner
2. Implementieren Sie eine Klasse NumOfSpanningBipartite,die folgende Anforderungen erfuellt:

- Die integer Zahlen "firstSetSize" und "secondSetSize" werden werden im Konstruktor als Parameter erwartet und in privaten Attributen abgespeichert.
- return (this.firstSetSize^(this.secondSetSize - 1)) *(this.secondSetSize ^ (this.firstSetSize -1));
3. Implementieren Sie eine main- Klasse nur mit String[args] Parameter
- Deklarieren Sie m und n als Zahlvariable(int)
- Benutzen Sie die Scanner Prozedure.
- Drucken Sie " Enter the size of the bipartite graph(m and n)
- Benutzen Sie eine Methode Scanner fuer m und n (next...())
- Erzeugen Sie ein neues Objekt bipartite.
- Benutzen Sie System.out.println(...+bipartite.numerOfSpanningTree(m,n)))
- Schliessen Sie Scanner Methode.

Details

$javac NumOfSpanningBipartite.java
$java NumOfSpanningBipartite
enter the size of the bipartite graph (m and n)
2 2

the number of spanning trees are  9

Aufgaben

Aufgabe1

Wieviele Zusammenhangskomponenten hat der Graph?

Ist der Graph bipartit?

dG(x,y) =?

dG(x,z)

Wieviel Kreise gibt es im Graphen ?

Wieviele Wege gibt es von x nach y?

Ü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

Algorithmus =

Algorithmus von Prim

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

Create a Balanced Binary Tree of the Incoming Data

Implement Binary Tree

Find Number of Spanning Trees in a Complete Bipartite Graph

Aufgaben

Aufgabe1

Übung zu Gozinto-Graphen

Suche