Quantcast
Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
    1. Welcome to GTAForums!   (85,677 visits to this link)

    2. News

    1. GTA Online

      1. Find Lobbies & Players
      2. Guides & Strategies
      3. Vehicles
      4. Content Creator
      5. Help & Support
    2. Crews

      1. Events
      2. Recruitment
    1. Grand Theft Auto Series

    2. GTA Next

    3. GTA V

      1. PC
      2. Guides & Strategies
      3. Help & Support
    4. GTA IV

      1. Episodes from Liberty City
      2. Multiplayer
      3. Guides & Strategies
      4. Help & Support
      5. GTA Mods
    5. GTA Chinatown Wars

    6. GTA Vice City Stories

    7. GTA Liberty City Stories

    8. GTA San Andreas

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    9. GTA Vice City

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    10. GTA III

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    11. Top Down Games

      1. GTA Advance
      2. GTA 2
      3. GTA
    12. Wiki

      1. Merchandising
    1. GTA Modding

      1. GTA V
      2. GTA IV
      3. GTA III, VC & SA
      4. Tutorials
    2. Mod Showroom

      1. Scripts & Plugins
      2. Maps
      3. Total Conversions
      4. Vehicles
      5. Textures
      6. Characters
      7. Tools
      8. Other
      9. Workshop
    3. Featured Mods

      1. DYOM
      2. OpenIV
      3. GTA: Underground
      4. GTA: Liberty City
      5. GTA: State of Liberty
    1. Red Dead Redemption 2

    2. Red Dead Redemption

    3. Rockstar Games

    1. Off-Topic

      1. General Chat
      2. Gaming
      3. Technology
      4. Programming
      5. Movies & TV
      6. Music
      7. Sports
      8. Vehicles
    2. Expression

      1. Graphics / Visual Arts
      2. GFX Requests & Tutorials
      3. Writers' Discussion
      4. Debates & Discussion
    1. Forum Support

    2. Site Suggestions

Sign in to follow this  
Gian_Yagami

Help me find graph solution

Recommended Posts

Gian_Yagami

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

20180220_184144.jpg
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.

Share this post


Link to post
Share on other sites
K^2

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.

Share this post


Link to post
Share on other sites
Gian_Yagami

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?

Share this post


Link to post
Share on other sites
K^2

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.

Share this post


Link to post
Share on other sites
Gian_Yagami

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 by Gian_Yagami

Share this post


Link to post
Share on other sites
K^2

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;}

Share this post


Link to post
Share on other sites
Gian_Yagami

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.

Share this post


Link to post
Share on other sites
Parik

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 by Parik

Share this post


Link to post
Share on other sites
Gian_Yagami

 

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 :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using GTAForums.com, you agree to our Terms of Use and Privacy Policy.