Help me find graph solution

[Gian_Yagami 31]

I have a homework, I must write program or algorithm for this case:

photo upload

This is a graph which written in two dimensional matrix, I must print all possible path from A point to E point to the console screen. The problem is I can not make the computer remember which path pattern has been printed.

[K^2 2,011]

You don't need to. You just need to make sure that you don't visit any vertex twice. That guarantees that you couldn't have printed the same path twice. Easiest way to do that is to keep track of vertices visited on a stack. Start by placing first vertex, A, on the stack. Then try all vertices A-E, testing the edge matrix for each, and skipping any vertices that are already on the stack. If you find a vertex that works, push it on the stack. If you found E at the top of the stack, print the contents of the stack from bottom up. That's a valid path. If you found that there are no more vertices you can add, you should pop from the top, but keep that element as the starting point for considering which vertex to push on the stack next.

 

If you do all of this correctly, your stack will change like this.

 

A

AB

ABC

ABCD

ABCDE -> Print path.

[stack popped twice, last element popped D]

ABCE -> Print path.

[stack popped twice, last element popped C]

ABE -> Print path.

[stack popped twice, last element popped B]

AD

ADC

ADCE -> Print path.

[stack popped twice, last element popped C]

ADE -> Print path.

[stack popped three times, empty stack - program terminates]

 

Give it a try, and see if you can make this work. If you still have problems, I'll try to give you more pointers.

[Gian_Yagami 31]

You don't need to. You just need to make sure that you don't visit any vertex twice. That guarantees that you couldn't have printed the same path twice. Easiest way to do that is to keep track of vertices visited on a stack. Start by placing first vertex, A, on the stack. Then try all vertices A-E, testing the edge matrix for each, and skipping any vertices that are already on the stack. If you find a vertex that works, push it on the stack. If you found E at the top of the stack, print the contents of the stack from bottom up. That's a valid path. If you found that there are no more vertices you can add, you should pop from the top, but keep that element as the starting point for considering which vertex to push on the stack next.

 

If you do all of this correctly, your stack will change like this.

 

A

AB

ABC

ABCD

ABCDE -> Print path.

[stack popped twice, last element popped D]

ABCE -> Print path.

[stack popped twice, last element popped C]

ABE -> Print path.

[stack popped twice, last element popped B]

AD

ADC

ADCE -> Print path.

[stack popped twice, last element popped C]

ADE -> Print path.

[stack popped three times, empty stack - program terminates]

 

Give it a try, and see if you can make this work. If you still have problems, I'll try to give you more pointers.

That's a nice way. After Stack is popped twice, how can I swich to new path and make sure they won't repeat it?

[K^2 2,011]

That's a nice way. After Stack is popped twice, how can I swich to new path and make sure they won't repeat it?

When you pop a vertex off the stack, you use that as a starting point to continue the search. So if you have ABC on the stack and you just popped C, you'll be checking to see if you can place D after B. Since there is no edge, you try next one, which is E. There is a BE edge, so you place it on the stack, macking ABE. And so on.

 

Basically, you're trying to resume the loop over the vertices at particular depth on the stack. Since you try each vertex at each depth only once, and you avoid repeating vertices on the stack, you're guaranteed unique paths.

[Gian_Yagami 31]

Yes I understand what you mean, I just don't get it "stack popped twice, last element D"

 

 

my code:

import java.util.*;import java.lang.*;import java.io.*;public class Main{    static int[][] A= new int[][]{        {0,1,0,1,0},        {1,0,1,0,1},        {0,1,0,1,1},        {1,0,1,0,1},        {0,1,1,1,0}    };    static String[] paths={"", "","","",""};    static int pathsCount=0;    static boolean isFirst=true;    	public static void main (String[] args) throws java.lang.Exception	{	    int J=0;		for(int I=0; I<5; I++){		    for(J=I; J<5; J++){		        if(A[i][J]==1){		            if(isFirst==true){		                switch(I){		                    case 0: paths[pathsCount]= paths[pathsCount]+"A";		                    break;		                    case 1: paths[pathsCount]= paths[pathsCount]+"B";		                    break;		                    case 2: paths[pathsCount]= paths[pathsCount]+"C";		                    break;		                    case 3: paths[pathsCount]= paths[pathsCount]+"D";		                    break;		                    case 4: paths[pathsCount]= paths[pathsCount]+"E";		                    break;		                }		            }		            switch(J){	                    case 0: paths[pathsCount]= paths[pathsCount]+"A";		                break;		                case 1: paths[pathsCount]= paths[pathsCount]+"B";		                break;		                case 2: paths[pathsCount]= paths[pathsCount]+"C";		                break;		                case 3: paths[pathsCount]= paths[pathsCount]+"D";		                break;		                case 4: paths[pathsCount]= paths[pathsCount]+"E";		                break;		            }		            isFirst=false;		            I=J;		            if(J==4){		                for(J=0; J<=pathsCount; J++){		                    if(paths[J]==paths[pathsCount]){		                        System.out.println(paths[pathsCount]);		                        pathsCount++;		                        isFirst=true;		                        J=0;		                        break;		                    }		                }		            }		        }		    }		}	}}

Edited February 25 by Gian_Yagami

[K^2 2,011]

I suck at explaining this without whiteboard, so maybe this will work. I've written up the solution in C++. You'd probably end up writing this completely differently in Java, but I can't come up with a better way to explain the idea behind solution than present it as code, and if you still have to figure out how to convert this to Java, it still seems to me like your homework. Anyways, if you want to see it run, you can use ideone.com (Make sure to select C++14, not just C++).

 

Oh, and I'm only using C++ vector instead of actual stack because C++ stacks kind of suck. Fortunately, vectors still support push and pop concepts, but you have to specify push_back and pop_back to modify the last element. Likewise, vector::back() works just like peek on stacks.

 

 

#include <algorithm>#include <iostream>#include <vector>static int edges[5][5] = {    {0,1,0,1,0},    {1,0,1,0,1},    {0,1,0,1,1},    {1,0,1,0,1},    {0,1,1,1,0}};void print_stack(const std::vector<int>& stack){    for (const int& vertex : stack)    {        std::cout << static_cast<char>('A' + vertex);    }    std::cout << std::endl;}bool stack_has_vertex(const std::vector<int>& stack, const int vertex){    return std::find(stack.begin(), stack.end(), vertex) != stack.end();}int main(){    std::vector<int> stack;    stack.push_back(0);    int vertex = 0;    while (!stack.empty())    {        if (vertex > 4)        {            vertex = stack.back() + 1;            stack.pop_back();            continue;        }        if (stack.back() == 4) // 'E'        {            print_stack(stack);            vertex = stack.back() + 1;            stack.pop_back();            continue;        }        if (!edges[vertex][stack.back()] || stack_has_vertex(stack, vertex))        {            ++vertex;            continue;        }        stack.push_back(vertex);        vertex = 0;    }        return 0;}

[Gian_Yagami 31]

Your code works perfectly but I can't understand stack.back() and stack.push_back() because I never uses stack function. Usually just array based stack.

[Parik 2,525]

Your code works perfectly but I can't understand stack.back() and stack.push_back() because I never uses stack function. Usually just array based stack.

stack.back() - returns the last element of the stack.

stack.push_back() - this adds an element to the end of the stack.

 

so if stack is {0 , 3 , 2 , 1 , 3}

stack.back() gives 3.

after calling stack.push_back(7),

stack becomes {0 , 3 , 2 , 1 , 3 , 7}

Edited February 28 by Parik

[Gian_Yagami 31]

 

Your code works perfectly but I can't understand stack.back() and stack.push_back() because I never uses stack function. Usually just array based stack.

stack.back() - returns the last element of the stack.

stack.push_back() - this adds an element to the end of the stack.

 

so if stack is {0 , 3 , 2 , 1 , 3}

stack.back() gives 3.

after calling stack.back(7),

stack becomes {0 , 3 , 2 , 1 , 3 , 7}

 

Cool man, now I get it. Thanks for help me