1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Minimum spanning tree (MST)

Discussão em 'Programação' iniciada por toninho_77, 21 de Maio de 2009. (Respostas: 4; Visualizações: 1207)

  1. toninho_77

    toninho_77 Power Member

    Boas pessoal,
    cá estou eu de volta para vos pedir umas dicas extra!
    Então é assim, tenho que elaborar um trabalho sobre o Minimum spanning tree (MST) em c#, encontro muita coisa na net sobre este algoritmo mas código propriamente dito não arranjo nada:( , só mesmo algum pseudo codigo manhoso!
    Quem me puder dar uma mão por aqui agradecia.
    Cumps.
     
  2. toninho_77

    toninho_77 Power Member

  3. toninho_77

    toninho_77 Power Member

    Bem então é assim:
    Recorrendo ao livro "Data Structures and Algorithms Using C Sharp", para resolver o problema da mininum spanning tree, deparei-me com alguns problemas!
    Talvez me possam ajudar, mas a esperança já é pouca para este trabalho.
    Então é assim, no livro diz para criar uma classe vertex, uma classe graph e depois tem o codigo do algoritmo.

    Código:
    public class Vertex
        {
            public bool wasVisited;
            public string label;
    
            public Vertex(string label)
            {
                this.label = label;
                wasVisited = false;
            }
     
        }
    Código:
       public class Graph
        {
            private const int NUM_VERTICES = 20;
            private Vertex[] vertices;
            private int[,] adjMatrix;
            int numVerts;
    
            public Graph()
            {
                vertices = new Vertex[NUM_VERTICES];
                adjMatrix = new int[NUM_VERTICES, NUM_VERTICES];
                numVerts = 0;
    
                for (int j = 0; j <= NUM_VERTICES; j++)
                {
                    for (int k = 1; k <= NUM_VERTICES - 1; k++)
                    {
                        adjMatrix[j, k] = 0;
                    }
                }
            }
    
            public void AddVertex(string label)
            {
                vertices[numVerts] = new Vertex(label);
                numVerts++;
            }
    
            public void AddEdge(int start, int eend)
            {
                adjMatrix[start, eend] = 1;
                adjMatrix[eend, start] = 1;
            }
    
            public void ShowVertex(int v)
            {
                Console.Write(vertices[v].label + " ");
            }
    
            internal void Mst()
            {
                throw new NotImplementedException();
            }
        }
    Código:
    static void Main(string[] args)
            {
                Graph aGraph = new Graph();
                aGraph.AddVertex("A");
                aGraph.AddVertex("B");
                aGraph.AddVertex("C");
                aGraph.AddVertex("D");
                aGraph.AddVertex("E");
                aGraph.AddVertex("F");
                aGraph.AddVertex("G");
                aGraph.AddEdge(0, 1);
                aGraph.AddEdge(0, 2);
                aGraph.AddEdge(0, 3);
                aGraph.AddEdge(1, 2);
                aGraph.AddEdge(1, 3);
                aGraph.AddEdge(1, 4);
                aGraph.AddEdge(2, 3);
                aGraph.AddEdge(2, 5);
                aGraph.AddEdge(3, 5);
                aGraph.AddEdge(3, 4);
                aGraph.AddEdge(3, 6);
                aGraph.AddEdge(4, 5);
                aGraph.AddEdge(4, 6);
                aGraph.AddEdge(5, 6);
                Console.WriteLine();
                aGraph.Mst();
    
                
    vertices[0].wasVisited = true;
                gStack.Push(0);
    
                int currVertex, ver;
    
                while (gStack.Count > 0)
                {
                    currVertex = gStack.Peek();
                    ver = GetAdjUnvisitedVertex(currVertex);
    
                    if (ver == -1)
                    {
                        gStack.Pop();
                    }
                    else
                    {
                        vertices[ver].WasVisited = true;
                        gStack.Push(ver);
                        ShowVertex(currVertex);
                        ShowVertex(ver);
                        Console.Write(" ");
                    }
                }
    
    
            }
    
        }
    Isto tudo e console aplication, mas não consigo correr a aplicação uma vez que no codigo do algoritmo, ele n reconhece nada, vertices,gstack etc.
    Se me puderem dar umas dicas, agradecia.
    Cumps.
     
    Última edição pelo moderador: 15 de Junho de 2009
  4. toninho_77

    toninho_77 Power Member

    Já descobri, vou ver se surgem novas duvidas!
    Cumps.
     
  5. Kayvlim

    Kayvlim Undefined Moderator
    Staff Member

    Em relação a teres descoberto, é sempre boa prática colocares a resposta que encontraste no tópico, para que outros users possam pesquisar e encontrar ;)

    Em relação ao pseudo-código, geralmente não é muito difícil concretizar pseudo-código numa linguagem qualquer. Sempre é melhor do que encontrar o código numa linguagem diferente.
     

Partilhar esta Página