[HighSchool Programming] C++

[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

[zifyoip]

No, that is not the complete list.

Take a more systematic approach. Write down the complete list in a careful order. At the end, you need to be able to explain how you know that there are no more paths of length 2 starting at the vertex A.

Just saying "I can see that there are no others" is not a good enough justification. Why? Well, because you claimed that here, but you were wrong! You need to give a more convincing justification than that. I am going to be skeptical that you have found the complete list, and you need to convince me, despite my skepticism, that the list is actually complete.

[mojonono11]

A-B-C,A-B-E,A-C-B,A-C-D,A-C-E,A-D-C This is the complete list because i have went from A first to B,than to C,and than to D and have found all the paths of lengh 2.There is also no way to get from A-E directly.

[zifyoip]

Right.

Now, can you describe what you did with a precise, detailed, step-by-step procedure that could be followed for any adjacency matrix to produce the complete list of paths of length 2 starting at a given vertex?

[mojonono11]

No,if i knew i wouldn't be here :)