Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

graph connectivity

Posted on 2003-03-25
2
Medium Priority
?
692 Views
Last Modified: 2006-11-17
I am looking for source code to determine the connectivity of a graph,
which has several mobile stations in it. Assume connect[no_ms][no_ms]
indicates the connectivity of a pair of two ms. 1 means connected,
0 means not.
0
Comment
Question by:rlin1
2 Comments
 
LVL 1

Expert Comment

by:keitha1
ID: 8213008
If you are looking for optimal (most efficient) connectivity check out the Minimum Spanning Tree algorithm.

If it's just 'are two nodes' connected there are all kinds of algorithms. Which algorithm you choose depends on things like 'does the graph have cycles in it'.
0
 
LVL 11

Accepted Solution

by:
bcladd earned 150 total points
ID: 8218273
Actually, MST is overkill. A depth-first (breadth-first) traversal of the graph (with cycle detection) will suffice. Assuming an undirected graph:

Push start node on stack.

while (stack not empty) {
  curr = stack.pop
  for (each child of curr) {
    if not child in stack already
       push child
}

if any unvisited node NOTCONNECTED
else CONNECTED

Assumption: No "mobile nodes" move during traversal. Connectivity cannot change DURING execution.

-bcl
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The purpose of this article is to demonstrate how we can use conditional statements using Python.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

578 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question