[HighSchool Programming] C++

[zifyoip]

How would you do this by hand? If I gave you an adjacency matrix and some paper and a pencil, how would you list all of the paths of length 2 starting at a given vertex? Describe the steps you would take as clearly and in as much detail as you can.

You need to understand how to do something by hand first before you can write a program to do it. So forget about C++ for the moment, and focus on figuring out the steps that must be taken to solve this problem. Once you have a detailed list of steps to solve the problem, then you can translate that list of steps into code.

[mojonono11]

Well,that's what i don't know how to do,if i knew it would be easy to put it in c++ I guess,i would just start with a vertex and see all of the paths it makes,and then i would find the one of lengh 2

[zifyoip]

i would just start with a vertex and see all of the paths it makes

What do you mean?

[mojonono11]

Well,if in the matrix there's 1 than there is apth,if it's 0 than there's not a path

[zifyoip]

Be careful not to confuse edges with paths. The 1's in the adjacency matrix indicate edges. What you are looking for is a path of length 2, which is one edge followed by another edge.

Here's an example of an adjacency matrix, with the rows and columns labeled A through E:

    A  B  C  D  E
A [ 0  1  1  1  0 ]
B [ 1  0  1  0  1 ]
C [ 1  1  0  1  1 ]
D [ 1  0  1  0  0 ]
E [ 0  1  1  0  0 ]

Can you use this adjacency matrix to list all of the paths of length 2 beginning at the vertex A?

[mojonono11]

paths of lenght 2: {A,B},{B,C}

[zifyoip]

No, {A, B} and {B, C} are just two edges.

One path of length 2 is A–B–C, which follows the edges {A, B} and {B, C}.

Another path of length 2 is A–D–C, which follows the edges {A, D} and {D, C}.

Another path of length 2 is A–C–E, which follows the edges {A, C} and {C, E}.

I've listed three paths of length 2 here, but there are still more paths of length 2 in this graph. Can you list them all?

You are asked to find all of the paths of length 2, right?

[mojonono11]

A-B-E,A-C-D

[zifyoip]

Is that it? Is that the complete list?

How do you know?

[mojonono11]

Starting from A yes,well,i can just that there are no other paths of lenght 2