The Big Programming Thread - Page 821

1.)remove starting node from "unvisited" set, save it as a temporary vertex "startingVertex"
2.)push it's children onto a stack
3.)pop the top of the stack, remove it from "unvisited", push it's children onto stack
4.)repeat #3 until unvisited is empty
5.)add in the edge from the last visited edge back to "startingVertex", and save this path as temporary solution

//now is where things get fuzzy for me

6.)somehow put the last "visited" vertex (not counting startingVertex) back into the "unvisited" set - how do I do this??
7.)go back to #4
8.)now when the last 2 levels of vertexes have been fully visited I am now going to somehow put 2 steps worth of vertexes back into "unvisited" set, again - I don't know how to mark my vertexes as unvisited
9.)back to #4, eventually having to put 3 steps worth of nodes as unvisited, and then finally 4 steps
10.)all done?  I think this does every pathway?  If I can figure out how to do that?  I don't know how to backtrack.

1.)remove starting node from "unvisited" set, save it as a temporary vertex "startingVertex"
2.)push it's children onto a stack
3.)pop the top of the stack, remove it from "unvisited", push it's children onto stack
4.)repeat #3 until unvisited is empty
5.)add in the edge from the last visited edge back to "startingVertex", and save this path as temporary solution

//now is where things get fuzzy for me

6.)somehow put the last "visited" vertex (not counting startingVertex) back into the "unvisited" set - how do I do this??
7.)go back to #4
8.)now when the last 2 levels of vertexes have been fully visited I am now going to somehow put 2 steps worth of vertexes back into "unvisited" set, again - I don't know how to mark my vertexes as unvisited
9.)back to #4, eventually having to put 3 steps worth of nodes as unvisited, and then finally 4 steps
10.)all done?  I think this does every pathway?  If I can figure out how to do that?  I don't know how to backtrack.

1. add start node to visited set
2. push start node to stack
3. pop off an element in stack
4. for each child of element
    a. if child is not in visited set
        i. add child to visited set
        ii. push child on stack
        iii. set child's parent to element
    b. if child is node to find, go to step 6 // if searching for the path to a node
5. if stack is not empty go to step 3
6. if child has parent, return list of parents up to starting node // if searching for the path to a node

// This is pythony, but shouldn't be too complicated to make into Java
permutations = all permutations of [0...n-1] // each element is a list with 0 to n-1 in a different order
minLength = a gajillion // or some upper bound on TSP solution
minWalk = None
for perm in permutations:
    walkLength = sum([adjMatrix[perm[i]][perm[i+1]] for i in range(n-1)])
    if walkLength < minLength:
        minLength = walkLength
        minWalk = perm
return minWalk

function permute($ary, $it, $len) {
    if ($it === $len) {
        print implode($ary) . PHP_EOL;
    }

    for ($i = $it; $i < $len; $i++) {
        swap($ary, $it, $i);
        permute($ary, $it + 1, $len);
        swap($ary, $it, $i); // backtrack
    }
}

function swap(&$ary, $x, $y) {
    $temp = $ary[$x];
    $ary[$x] = $ary[$y];
    $ary[$y] = $temp;
}

$letters = ['a', 'b', 'c', 'd'];

echo permute($letters, 0, count($letters));

// => abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc 

// This assumes you have at least one node on the stack.  All nodes on stack are marked and all off stack are unmarked.
void dfs(void)
{
    Node *node = peek();
    Node *otherNode;
    bool found = false;

    forEachAdjacentNode(node, otherNode) {
        if(otherNode->marked == false) {
            found = true;
            otherNode->marked = true; //This can be part of push if you like
            push(otherNode);  //If you want all paths from starting node to any node then do something in push or here.
            dfs();
            pop();
            otherNode->marked = false; // This can be part of pop if you like.
    }
    if(found == false) {
        //Your stack now contains one of the paths from your starting node to a node with no unreached adjacent nodes.
    }
}

//This calls dfs from each node.
void alldfs(void)
{
    Node *node;

    forEachNode(node) {
        node->marked = true;
        push(node);
        dfs();
        pop();
        node->marked = false;
    }
}