How do I change 2 for loops into 1 while loop without loosing funtionality

Question

1.00/5 (1 vote)

See more:

Hello,

I need to change the following code (which contains 3 FOR Loops)
to 1 'WHILE' and '2 FOR loops'. My code, (located in "what have you tried") works but not correct. ¬
I'm getting garbage in some of the edges. I have isolated the problem to the i and k process.
Please help.

Thanks in advance.

Original Code Segment

C++

mstv[source] = true;
edgeWeights[source] = 0;

for (int i = 0; i < gSize - 1; i++)
{
	minWeight = DBL_MAX;

	for (int j = 0; j < gSize; j++)
		if (mstv[j])
		for (int k = 0; k < gSize; k++)
		if (!mstv[k] && weights[j][k] < minWeight)
		{
			endVertex = k;
			startVertex = j;
			minWeight = weights[j][k];
			cout << " endVertex K " << endVertex << endl;
			cout << " start J " << startVertex << endl;
			cout << " minweight " << minWeight << endl;
		}
	
		mstv[endVertex] = true;
		edges[endVertex] = startVertex;
		edgeWeights[endVertex] = minWeight;
	} //end for
} //end minimalSpanning

The Problem Definition

Write a definition of the new function (Prim2) to implement this algorithm

Input: A connected weighted graph G = (V, E) of N vertices, numbered 0, 1, 2,,,, n-1;
starting with vertex s, with a weight matrix of W.
Output: The minimal spanning tree.

C++

Prim2 (G, W, n, s)
Let T = (V, E), where E = 0
for ( j = 0; j < n; j ++) to n
{
	edgeWeights [ j ] = W(s, j);
	edges [ j ] = s;
	visited [ s ] = false;
}
edgeWeights [ s ] = 0;
visited [ s ] = true
while (not all nodes are visited)
{
	Choose the node that is not visited and has the smallest weight, and call it k.
	visited [ k ] = true;
	E = E U { ( k, edges [ k ] ) }
	V = V U { k }
	for each node j that is not visited
	if (W ( k, j ) < edgeWeights [ j ])
	{
		edgeWeights [ j ] = W ( k, j );
		edges[ j ] = k;
	}
	return T;

My Code Segment

C++

visited[source] = true; edgeWeights[source] = 0; int i = 0, int k = 0 // choose node that's not visited and has the smallest weight

while (! visited[i] && (k < gSize)) { // nodes have not been visited
	visited[k] = true; k++;

	for (int j = 0; j < gSize; j++) // for each node 'j' that is not visited
		if (weights[k][j] < 	edgeWeights[j]) {
			(edgeWeights[j] = weights[k][j]);
			edges[j] = k;
			cout << " Edge Weight " <<
			edgeWeights[j] << endl; cout << " Edges K " << edges[j] << endl;
	
		} } // end while } // end prim2 Function

Posted 1-May-16 10:40am

mzgerry

Updated 1-May-16 21:05pm

Patrice T

v7

Add a Solution

Comments

Patrice T 1-May-16 17:06pm

I did some formatting, hope I didn't destroy anything ( many things got destroy on first edit).

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Jochen Arndt · Accepted Answer · 2016-05-01T21:05:00

Just imagine what a for loop - cppreference.com[^] is doing and when the parts are executed:

for (init_statement; condition; iteration_expression)

is executed as

init_statement;
while (condition)
{
    // Body
    iteration_expression;
}

So the iteration_expression is executed after the body has been executed. But in your code it is executed at the wrong place and you are using two array indexes where i is never used again (changed):

int i = 0;
int k = 0;
while (! visited[i] && (k < gSize)) 
{ 
    visited[k] = true; 
    // This is wrong here!
    // Move it below the body block.
    //k++;

    // Body

    // Insert iteration_expression(s) here.
    k++;
    // Incrementing i is absent in your code.
    i++;
}

In your case you may omit one iteration variable. I have not checked your algorithm but it looks like the usage of your visited array is useless here. Maybe you want to do something like this (but again: I don't know if this breaks the algorithm):

C++

memset(visited, 0, sizeof(visited));
int k = 0;
while (k < gSize)
{
    if (!visited[k])
    {
        for (int j = 0; j < gSize; j++)
        {
            if (weights[k][j] < edgeWeights[j]) 
            {          
                // Calculation
                visited[j] = true;  
            }
    }
    k++;
}