Is this a proper algorithm that would accept graph G if it's connected?

Question

I wanted to ask and see if this suffices in creating a polynomial time algorithm given a Graph P? Just want to double check.

On input (P,u,v) where P is an undirected graph with nodes u and v:

1. Create a list D of every edge in graph P with numbers from x_0 to x_k.

2. Select node u as the starting node. Utilizing BFS, traverse through the graph until the current node is the initial u value.

3. Repeat with using x_0 onwards through the list until x_k is used.

4. If BFS completes, accept. Otherwise, reject.

I believe my problem lets with the accept/rejection condition but what would it be in this case?

Answer 1

Your question doesn't make sense in a lot of ways, but from what I can tell, no.

Your step 2 will (slowly) find a cycle, which is not useful.

I have no clue what step 3 is supposed to be and your variable v is unused (and having u as as parameter doesn't make sense).

For an directed graph, you need to specify whether you want to check for weak connectivity (like a undirected graph) or strong connectivity.

For weak connectivity, you need to:

1. Take as input a graph G

2. Create a local, empty, set S for seen nodes.

3. Do a depth first search (including backwards links - watch your algorithmic complexity with how you look them up!) from some node, adding each node to S as you visit it, and skipping edges that lead from the current node to a node in S during iteration. (You can use a breadth-first search if you allocate an additional data set for the frontier)

4. Check whether S has the same number of nodes as G.

For strong connectivity, you need to check that the graph is connected regardless of which node you set at. There's probably a way to do this more efficiently than repeating the above for every node.

An example graph (consider this from any starting node):

1 -> 2
2 -> 3
3 -> 1
3 -> 4
4 -> 5
5 -> 6
6 -> 4