Need help to fix my program to find MST using Kruskal Algorithm

How does the output your program produces differ from the output you expect?

Are your data structures holding the information in the way you expect? Does your sort work?

It looks like you are reading from an input file. Is that correct? If so, don't you want to have the flexibility to incorporate the number of vertices and edges in creating your data structures [using dynamic memory since you won't know these values at compile time]?

How have you planned your data structures? How are you representing your graph?

I understand how Kruskal's works. Have you mapped out how you are going to do all of the "sorting" and "checking" and "adding" and record keeping needed to implement the algorithm?

I was prompting you to put into writing how you are storing the data you are reading in from "input.txt". This is the start for understanding how you intend to sort edges, then build your MST.

There are two basic structures used to store graph data: adjacency list and adjacency matrix. Are you using either of these, or one of your own creation?

There are straightforward structures for storing items in sorted order according to a priority. Are you using such a structure?

Heap is a very good structure to back up a priority queue. You should be able to find all sorts of code on this - in books or on line.

Hi, I need to convert the following program from JAVA to C++ code. Does anyone have a tool for this conversion? Or can anyone convert for me please?
================================
Find a Maxflow using Ford-Fulkerson Method

import java.applet.*;
import java.awt.*;
import java.io.*;
import java.net.URL;

class Node {
int x;
int y;
int delta_plus; /* edge starts from this node */
int delta_minus; /* edge terminates at this node */
int dist; /* distance from the start node */
int prev; /* previous node of the shortest path */
int p_edge;
int l;
int w;
int h;
String name;
}

class Edge {
int rndd_plus; /* initial vertex of this edge */
int rndd_minus; /* terminal vertex of this edge */
int delta_plus; /* edge starts from rndd_plus */
int delta_minus; /* edge terminates at rndd_minus */
int capacity; /* capacity */
int flow; /* flow */
int st;
String name;
}

public class Maxflow extends Applet {
int n,m;
int snode,tnode; /* start node, terminate node */
int step;
Node v[] = new Node[100];
Edge e[] = new Edge[200];

int findNode(String name) {
for (int i=0; i<n; i++)
if (v[i].name.equals(name))
return i;
return -1;
}

void input_graph(InputStream is) throws IOException {
int x,y,l;
String s;

StreamTokenizer st = new StreamTokenizer(is);
st.commentChar('#');
st.nextToken(); n = (int)st.nval;
st.nextToken(); m = (int)st.nval;
st.nextToken(); s = st.sval;
for (int i = 0; i<n; i++) {
Node node = new Node();
st.nextToken(); node.name = st.sval;
st.nextToken(); node.x = (int)st.nval;
st.nextToken(); node.y = (int)st.nval;
v[i] = node;
}
for (int i = 0; i<m; i++) {
Edge edge = new Edge();
st.nextToken(); edge.name = st.sval;
switch (st.nextToken()) {
case StreamTokenizer.TT_NUMBER:
edge.rndd_plus = (int)st.nval;
break;
case StreamTokenizer.TT_WORD:
edge.rndd_plus = findNode(st.sval);
break;
default:
break;
}
switch (st.nextToken()) {
case StreamTokenizer.TT_NUMBER:
edge.rndd_minus = (int)st.nval;
break;
case StreamTokenizer.TT_WORD:
edge.rndd_minus = findNode(st.sval);
break;
default:
break;
}
st.nextToken(); edge.capacity = (int)st.nval;
edge.flow = 0;
e[i] = edge;
}
step = 1;
}

void rdb() {
int i,k;

for (i=0; i<n; i++)
v[i].delta_plus = v[i].delta_minus = -1;
for (i=0; i<m; i++)
e[i].delta_plus = e[i].delta_minus = -1;
for (i=0; i<m; i++) {
k = e[i].rndd_plus;
if (v[k].delta_plus == -1)
v[k].delta_plus = i;
else {
k = v[k].delta_plus;
while(e[k].delta_plus >= 0)
k = e[k].delta_plus;
e[k].delta_plus = i;
}
k = e[i].rndd_minus;
if (v[k].delta_minus == -1)
v[k].delta_minus = i;
else {
k = v[k].delta_minus;
while(e[k].delta_minus >= 0)
k = e[k].delta_minus;
e[k].delta_minus = i;
}
}
}

void stpath() { /* find an s-t path */
int u[] = new int[100], ni, no;
int i,j,d;

for (i=0; i<n; i++) {
v[i].prev = v[i].dist = -1;
v[i].l = 0;
}
for (i=0; i<m; i++)
e[i].st = -1;
ni = no = 0;
d = 0;
u[ni] = snode;
v[snode].dist = 0;
j = v[snode].delta_plus;
i = 0;
while (j>=0) {
if (i<e[j].capacity)
i = e[j].capacity;
j = e[j].delta_plus;
}
v[snode].l = i;

for (; no<=ni; no++) {
d = v[u[no]].dist;
for (j=v[u[no]].delta_plus; j>=0; j=e[j].delta_plus) {
if (e[j].capacity-e[j].flow == 0)
continue;
i = e[j].rndd_minus;
if (v[i].dist<0) {
v[i].dist = d+1;
v[i].prev = u[no];
v[i].p_edge = j;
v[i].l = Math.min(v[u[no]].l,
e[j].capacity-e[j].flow);
e[j].st++;
u[++ni] = i;
}
}
for (j=v[u[no]].delta_minus; j>=0; j=e[j].delta_minus) {
if (e[j].flow == 0)
continue;
i = e[j].rndd_plus;
if (v[i].dist<0) {
v[i].dist = d+1;
v[i].prev = u[no];
v[i].p_edge = j;
v[i].l = Math.min(v[u[no]].l,e[j].flow);
e[j].st++;
u[++ni] = i;
}
}
}
}

void step0() { /* initialize */
for (int i=0; i<m; i++)
e[i].flow = 0;
stpath();
}

void step1() { /* mark an s-t path */
int i;

if (v[tnode].dist<0)
return;
for (i = tnode; v[i].prev>=0; i=v[i].prev )
e[v[i].p_edge].st++;
}

void step2() { /* augment the flow */
int i,j,a,f;

f = v[tnode].l;
for (i = tnode; (j=v[i].prev)>=0; i = j) {
a = v[i].p_edge;
if (e[a].rndd_minus==i)
e[a].flow += f;
else if (e[a].rndd_plus==i)
e[a].flow -= f;
}
stpath();
}

public void init() {
String mdname = getParameter("inputfile");
try {
InputStream is;

is = new URL(getDocumentBase(),mdname).openStream();
input_graph(is);
try {
if (is != null)
is.close();
} catch(Exception e) {
}
} catch (FileNotFoundException e) {
System.err.println("File not found.");
} catch (IOException e) {
System.err.println("Cannot access file.");
}

String s = getParameter("s");
if (s != null)
snode = Integer.parseInt(s);
else
snode = 0;

s = getParameter("t");
if (s != null)
tnode = Integer.parseInt(s);
else
tnode = n-1;

setBackground(Color.white);
rdb();
step0();
}

public void paintNode(Graphics g, Node n, FontMetrics fm) {
String s;
int x = n.x;
int y = n.y;
int w = fm.stringWidth(n.name) + 10;
int h = fm.getHeight() + 4;
n.w = w;
n.h = h;
Color c;

if (n.dist<0)
c = Color.gray;
else
c = Color.blue;
g.setColor(c);
g.drawRect(x-w/2,y-h/2,w,h);

g.setColor(getBackground());
g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);

g.setColor(c);
g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());
}

int [] xy(int a, int b, int w, int h) {
int x[] = new int[2];

if (Math.abs(w*b)>=Math.abs(h*a)) {
x[0] = ((b>=0)?1:-1)*a*h/b/2;
x[1] = ((b>=0)?1:-1)*h/2;
} else {
x[0] = ((a>=0)?1:-1)*w/2;
x[1] = ((a>=0)?1:-1)*b*w/a/2;
}
return x;
}

void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {
int a = x1-x2;
int b = y1-y2;

double aa = Math.sqrt(a*a+b*b)/16.0;
double bb = b/aa;
aa = a/aa;
g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),
y2+(int)((-aa*5+bb*12)/13));
g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),
y2+(int)((aa*5+bb*12)/13));
g.drawLine(x1,y1,x2,y2);
}

public void paintEdge(Graphics g, Edge e, FontMetrics fm) {
Node v1 = v[e.rndd_plus];
Node v2 = v[e.rndd_minus];
Color c;

int a = v1.x-v2.x;
int b = v1.y-v2.y;

int x1[] = xy(-a,-b,v1.w,v1.h);
int x2[] = xy(a,b,v2.w,v2.h);

if (e.st>0)
c = Color.red;
else if ((v1.dist>=0)&&(v2.dist>=0))
c = Color.blue;
else
c = Color.gray;
g.setColor(c);
drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);

int w = fm.stringWidth(""+e.flow+"/"+e.capacity);
int h = fm.getHeight();

g.setColor(getBackground());
g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);
g.setColor(Color.black);
g.drawString(""+e.flow+"/"+e.capacity,
(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());
}

public void paint(Graphics g) {
FontMetrics fm = g.getFontMetrics();
for (int i=0; i<n; i++)
paintNode(g,v[i],fm);
for (int i=0; i<m; i++)
paintEdge(g,e[i],fm);
Residue p = (Residue)getAppletContext().getApplet("residue");
if (p!=null)
p.set(1,n,m,snode,tnode,v,e);
}

public void update(Graphics g) {
paint(g);
}

public boolean mouseDown(Event ev, int x, int y)
{
if (step==1) {
step1();
if (v[tnode].dist<0)
step = 0;
else
step = 2;
} else if (step==2){
step2();
step = 1;
} else {
step0();
step = 1;
}
repaint();
return true;
}
}