CODEWITHSUNDEEP
c#algorithm
Nick
Nick

Reputation: 465

Undirected graph, check if path exists between nodes

I am trying to check if there is path from one vertex to any from several other vertices (in my particular case, i need to check if there is way from top of the wall to the any other brick that is on the ground, and every brick is a vertex).

I have found some algorithms, but i need simplified version just to check if the path exists. (it'd be good if i also could have number of the possible paths. )

I'm new to the graphs and searched a lot about these search algorithms before asking here, but i couldn't figure out how to implement them in my situation.

Edit 1: I forgot to add that i can have hundreds of bricks (vertices) and need fastest way of checking if path exists. I have searched Dijkstra's algorithm and it looks too complicated. And for some reason there are more tutorials and explanations for Directed graphs, so that's the reason why i am writing question here.

for now i have vertex class:

public class Vertex : MonoBehaviour {

public string id;

public float x; // Horizontal coord
public float y; // Vertical coord

public Vertex(string id, float x, float y)
{
    this.id = id;
    this.x = x;
    this.y = y;
}
}

and edge class:

public class Edge : MonoBehaviour {

public Vertex Vertex1; // Vertex one
public Vertex Vertex2; // Vertex two

public Edge(Vertex Vertex1, Vertex Vertex2)
{
    this.Vertex1 = Vertex1;
    this.Vertex2 = Vertex2;
}
}

Dont really know how to represent them in graph, because as input i have 3 dimensional wall and after some bricks are destroyed i need to check if top brick has path to any of the bottom bricks that are on floor, because if not wall will basically collapse. So looks like I have to check in 3 dimensions for all paths.

Edit 2:

in vertex class i added neighbors list public List<Vertex> Neighbours; but still can't figure out how to represent graph in 3d so at least you could tell me how it'd be represented in 2d.

ps(thank you all for comments and answers I really appreciate them).

Upvotes: 1

Views: 8521

Answers (5)

J. Michael Wuerth
J. Michael Wuerth

Reputation: 292

Since you are seeking a simple solution, I would use a breadth-first search. A less-simple solution would involve something like the All-Pairs shortest path algorithm to determine the shortest path between every pair of nodes in a graph.

Upvotes: 0

Rerito
Rerito

Reputation: 6086

You only want to test for a path existence, so your best bet from a graph theory perspective is to use a BFS.

You have a source vertex src and a set Stgt of target vertices.

Since your graph is undirected when the BFS is over you will have the set of vertices of the connected component containing src. Just check if Stgt is a subset of that set.

To sum up:

  1. Let Sbfs be an empty hashset of vertices
  2. Perform a BFS starting from src:
    1. When you discover a vertex v, insert it into Sbfs
  3. Perform the intersection of Sbfs and Stgt to get all the target vertices that are reachable from src

Upvotes: 1

user555045
user555045

Reputation: 64913

With a bit of pre-processing, you can answer those queries in near-constant time, which is useful when you have to test several pairs of nodes (it seems like you do).

The pre-processing is simple: initialize a disjoint set with V items (V is the number of vertices), then for every edge (x,y) call union(x, y). This is almost linear in the number of edges ("almost" meaning it differs by an inverse Ackerman factor, which is so close to constant that it might as well be actually constant).

To find whether there is a path between x and y, test find(x) == find(y).

You could find the number of possible paths between any pair by raising the adjacency matrix to the V'th power (using any fast exponentiation algorithm, but it will still be relatively slow).

Upvotes: 3

Patrick87
Patrick87

Reputation: 28322

To find any path, you can use depth-first search. To find a shortest path, you can use breadth-first search. To find all paths (hence the number of paths), you can use either of the above and modify to (a) continue after finding the target node and (b) see if other paths can reach the target node (though it may have been reached previously). To find the path of least weight to the node (in a weighted graph), you can use Dijkstra's algorithm (no negative edges), Bellman-Ford (negative edges OK) or Floyd-Warshall (no negative cycles).

Upvotes: 3

Arsen Mkrtchyan
Arsen Mkrtchyan

Reputation: 50752

It is simple

  1. Put source vertex into queue
  2. check if queue is empty, you are done, no path if not
  3. check if it is one of the vertexes from the destination set, if yes you are done, path exists, if not, put all neighbors of that vertex to queue repeat steep 2

Upvotes: 2

Related Questions