Help me to find the error in Prim code

[chuong3a]

Help me to find the error in Prim code, thanks.

#include  <iostream.h>
#include  <stdio.h> 
#define  MAX  10

class prims  {
	private: 
 	int cost[MAX][MAX], tree[MAX][MAX];  int n;
	public: 
 	void readmatrix();
	int spanningtree (int src);
	void display (int cost);
};
void prims :: readmatrix()  {
	int i, j, k; n = 3; k = 0; 
	int x[9] = { 9, 19, 21, 11, 8, 17, 15, 10, 5}; 
	for (i = 1; i <= n; i++)  {
	for (j = 1; j <= n; j++)  {
	 	cost[i][j] = x[k];  k++; 
		printf ("A[%d][%d] = %d  ", i, j, cost[i][j]);	} 
		printf ("\n");  }
}
int prims :: spanningtree (int src)  {
	int visited[MAX], d[MAX], parent[MAX];
	int i, j, k, min, u, v, stcost;
	for (i = 1; i <= n; i++)  {
		d[i] = cost[src][i];  visited[i] = 0;
		parent[i] = src; 		}
	visited[src] = 1;  stcost = 0;  k = 1;
	for (i = 1; i < n; i++)  {
		min = 999;
		for (j = 1; j <= n; j++)  {
			if (!visited[j] && d[j] < min)  {
				min = d[j];  u = j; 				}
		}
		visited[u] = 1;
		stcost = stcost + d[u];
		tree[k][1] = parent[u];
		tree[k++][2] = u;
		for (v = 1; v <= n; v++)
			if (!visited[v] && (cost[u][v] < d[v]))  {
				d[v] = cost[u][v];  parent[v] = u; 		}
	}
	return (stcost);
}
void prims :: display (int cost)  {
	int i;
	cout << "\n The Edges of the Mininum Spanning Tree are \n";
	for (i = 1; i < n; i++)
		cout << tree[i][1] << " " << tree[i][2] << endl;
	cout << "\n The Total cost of the Minimum Spanning Tree is : " << cost;
}
int main()  {
	int source, treecost;  prims pri;
	pri.readmatrix();
	cout << "\n Enter the Source : ";  cin  >> source;
	treecost = pri.spanningtree (source);
	pri.display (treecost);  return 0;
}

[Ancient Dragon]

What are the problems with that program? You don't take your car to an auto shop and tell them "My car is broke, please fix it" :) You have to at least tell them what the problem is.

[chuong3a]

the error is: when I type the source node is 9, The Edge of Minimun Spanning Tree are: 9 1 1 2, but 1 and 2 is not the value in my initial Array?

[chuong3a]

Help me to run by step the Prim code, thanks.

#include  <iostream.h>
#include  <stdio.h>
class prims  {
    private:
    int n;      // Number of nodes
    int graph_edge[250][4];  // Edges in the graph
    int g;      // Number of edges in the graph
    int tree_edge[250][4];      // Edges in the tree
    int t;      // Number of edges in the tree
    int s;      // Source node
// Partition the graph into two sets
    int T1[50], t1;  // Set 1
    int T2[50], t2;  // Set 2
    public:
    void input();
    int findset (int x);
    void algorithm();
    void output();
};
void prims :: input()  {
    cout << "This program implements the prims algorithm \n";
    n = 5;  int i, j, k;  g = 0;  k = 0;
    int x[10] = { 3, 21, 29, 31, 17, 13, 18, 19, 23, 27 };
    cout << "Enter the weights for the following edges :: \n";
    for (i = 1; i <= n; i++)  {
        for (j = i+1; j <= n; j++)  {
            if (x[k] != 0)  {
                g++;  graph_edge[g][1] = i;  graph_edge[g][2] = j;
                graph_edge[g][3] = x[k];
                printf ("graph_edge[%d][1] = i = %d \n", g, i);
                printf ("graph_edge[%d][2] = j = %d \n", g, j);
                 printf ("graph_edge[%d][3] = x[k] = %d \n", g, x[k]);
            }
            k++;
        }   }
    // Print the graph edges
    cout << "\n The edges in the given graph are:: \n";
    for (i = 1; i <= g; i++)
        cout << " < " << graph_edge[i][1] << " , " << graph_edge[i][2]
        << " > ::" << graph_edge[i][3] << endl;
}
int prims :: findset (int x)  {
    int i;
        for (i = 1; i <= t1; i++)
            if (x == T1[i])  {
                printf ("x == T1[%d] = %d  return 1 \n", i, x);
                return 1;       }
        for (i = 1; i <= t2; i++)
            if (x == T2[i])  {
                printf ("x == T2[%d] = %d  return 2 \n", i, x);
                 return 2;  }
    return -1;
}
void prims :: algorithm()  {
    t = 0;  t1 = 1;
    T1[1] = 1;  // The source node
    t2 = n - 1;  int i;
    for (i = 1; i <= n-1; i++)  {
        T2[i] = i + 1;  // The reamining nodes
        printf ("T2[%d] = %d \n", i, i+1);  }
    cout << "\n *** The algorithm starts *** \n";
    while (g != 0 && t != n-1)  {
        cout << "g = " << g << " t = " << t << "\n";
        // Find the least cost edge
        int min = 9999;  int u, v, p, w;
        for (i = 1; i <= g; i++)  {
        // If u and v are in different sets
            if (findset (graph_edge[i][1]) != findset (graph_edge[i][2]) )  {
                cout << "if (findset (graph_edge[i][1]) != findset (graph_edge[i][2]) ) \n";
                printf ("graph_edge[%d][1]) = %d \n", i, graph_edge[i][1] );
                printf ("graph_edge[%d][2]) = %d \n", i, graph_edge[i][2] );
                if (min > graph_edge[i][3])  {
                    min = graph_edge[i][3];  u = graph_edge[i][1];
                    v = graph_edge[i][2];  w = graph_edge[i][3];  p = i;
                    cout << "u = graph_edge[i][1] = " << u << "  v = graph_edge[i][2] = " << v
                    << "  min = graph_edge[i][3] = " << min << "\n";
                }   }  
             }
    // Break if there is no such edge
    cout << "The edge included in the tree is ::";
    cout << " < " << u << " , " << v << " > " << endl;
    int k;
    // Delete the edge from graph edges
    for (k = p; k < g; k++)  {
        graph_edge[k][1] = graph_edge[k+1][1];
        graph_edge[k][2] = graph_edge[k+1][2];
        graph_edge[k][3] = graph_edge[k+1][3];
    }  g--;  cout << "g = " << g << "\n";
    // Add the edge to the tree
    t++;  tree_edge[t][1] = u;  cout << "t = " << t << "\n";
    tree_edge[t][2] = v;  tree_edge[t][3] = w;
    /* Alter the set partitions  */
     t1++;  int m;
    if (findset(v) == 2)  {
        printf ("if (findset(v) == 2) \n");
        printf ("T1[t1] = T1[%d] = v = %d \n", t1, v);
        T1[t1] = v;  m = v;     }
    else if (findset(u) == 2)  {
        printf ("if (findset(u) == 2) \n");
        printf ("T1[t1] = T1[%d] = u = %d \n", t1, u);
        T1[t1] = u;  m = u;         }
    int x;
    for (x = 1; T2[x] != m; x++);
    for (; x < t2; x++)
        T2[x] = T2[x+1];
    t2--;
    // Print the sets
    cout << "NOW \n T1 :: ";
    for (k = 1; k <= t1; k++)
        cout << T1[k] << ' ' << "\n" << "T2 :: ";
    for (k = 1; k <= t2; k++)
        cout << T2[k] << ' ' << "\n";  
    cout << "The graph edges are :: \n";
    for (i = 1; i <= g; i++)
        cout << " < " << graph_edge[i][1] << " , " << graph_edge[i][2]
        << " > ::" << graph_edge[i][3] << endl;
    }   }
void prims :: output()  {
    cout << "\n The selected edges are :: \n";
    for (int i = 1; i <= t; i++)
        cout << " < " << tree_edge[i][1] << " , " << tree_edge[i][2]
        << " > ::" << tree_edge[i][3] << endl;
}
int main()  {
    prims obj;  obj.input();
    obj.algorithm();  obj.output();
    return 0;
}

I dont understand how this following code run

/* Alter the set partitions - Thay ??i t?p con */
     t1++;  int m;
    if (findset(v) == 2)  {
        printf ("if (findset(v) == 2) \n");
        printf ("T1[t1] = T1[%d] = v = %d \n", t1, v);
        T1[t1] = v;  m = v;     }
    else if (findset(u) == 2)  {
        printf ("if (findset(u) == 2) \n");
        printf ("T1[t1] = T1[%d] = u = %d \n", t1, u);
        T1[t1] = u;  m = u;         }
    int x;
    for (x = 1; T2[x] != m; x++);
    for (; x < t2; x++)
        T2[x] = T2[x+1];
    t2--;
    // Print the sets
    cout << "NOW \n T1 :: ";
    for (k = 1; k <= t1; k++)
        cout << T1[k] << ' ' << "\n" << "T2 :: ";
    for (k = 1; k <= t2; k++)
        cout << T2[k] << ' ' << "\n";