?
Solved

graph connectivity

Posted on 2003-03-25
2
Medium Priority
?
681 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

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

If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
This article will show, step by step, how to integrate R code into a R Sweave document
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

777 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