c++ - To check if a graph is connected using BFS and print MST -

-

i have stored graph nodes 1,2,3,4,... in adjacency list. wrote code breadth first search (bfs). bfs works perfect don't know procedure find out if graph connected or disconnected , print minimum spanning tree of graph if connected? example of graph stored in adjacency list:

 1 3 4  2 4  3 1 4  4 2 1 3

and code bfs:

 int visit[999] = { 0 };  q.enqueue(0);  while (!q.isempty())      {             y = q.dequeue();              traverse = g[y];              while (traverse->link != 0)             {                  if (visit[traverse->data-1] == 0)                 {                      visit[traverse->data-1] = 1;                     parent = traverse->data;                     q.enqueue(traverse->data-1);                 }                 traverse = traverse->link;               }                 if (visit[traverse->data - 1] == 0)             {                  visit[traverse->data - 1] = 1;                 parent = traverse->data;                 q.enqueue(traverse->data - 1);             }      }

so figured out , put reference others :)

    int parent = 1;     gcounter++;     p = 0;     int visit[999] = { 0 };     int c[999] = { 0 };     int k = 0;     int z = 0;     queue q;     q.enqueue(0);     while (!q.isempty())      {             y = q.dequeue();             traverse = g[y];              while (traverse->link != 0)             {                  if (visit[traverse->data-1] == 0)                 {                      if (y + 1 != traverse->data)                     {                         c[z] = y + 1;z++;                         c[z] = traverse->data; z++;                      }                     p++;                     visit[traverse->data-1] = 1;                     parent = traverse->data;                     q.enqueue(traverse->data-1);                 }                 traverse = traverse->link;               }                 if (visit[traverse->data - 1] == 0)             {                  if (y + 1 != traverse->data)                 {                     c[z] = y + 1; z++;                     c[z] = traverse->data; z++;                 }                 p++;                 visit[traverse->data - 1] = 1;                 parent = traverse->data;                 q.enqueue(traverse->data - 1);             }      }            if (p < lcounter) //lcounter-> lines -> total number of nodes         {             writefile << "the graph disconnected" << endl;           }         else         {             writefile << "the graph connected , it's mst is: ";             (z = 0; c[z+1] != 0; z++)             {                 writefile << "(" << c[z] << "," << c[z + 1] << ") ";                 z++;             }             writefile << endl;          }

Comments

Post a Comment

Popular posts from this blog

c# - Unity IoC Lifetime per HttpRequest for UserStore -

-
i'm trying clean default implementation of accountcontroller.cs comes out of box in new mvc5/owin security implementation. have modified constructor this: private usermanager<applicationuser> usermanager; public accountcontroller(usermanager<applicationuser> usermanager) { this.usermanager = usermanager; } also, have created lifetime manager unity looks this: public class httpcontextlifetimemanager<t> : lifetimemanager, idisposable { private httpcontextbase _context = null; public httpcontextlifetimemanager() { _context = new httpcontextwrapper(httpcontext.current); } public httpcontextlifetimemanager(httpcontextbase context) { if (context == null) throw new argumentnullexception("context"); _context = context; } public void dispose() { this.removevalue(); } public override object get...
Read more

Change the color of an oval at click in Java AWT -

-
i have draw ovals in java, , @ click change color. beginning tried change color after 20 ms, doesn't work. my code is: public class mycomponentnew extends frame { public graphics2d g2d; public mycomponentnew(string title) { super(title); setsize(400, 550); } @override public void paint(graphics g) { this.g2d = (graphics2d) g; this.g2d.setcolor(color.red); this.g2d.filloval(10, 55, 50, 100); } public void changecolor () { this.g2d.setcolor(color.blue); this.g2d.filloval(10, 55, 50, 100); } } and in class main method have: mycomponentnew m; m = new mycomponentnew("fereastra cu baloane"); m.setvisible(true); m.addwindowlistener(new windowadapter() { @override public void windowclosing(windowevent we) { system.exit(0); } }); try { thread.sleep(20); } catch(interruptedexception e) {} m.changecolor(); the color of oval remains red. ...
Read more

I am trying to solve the error message 'incompatible ranks 0 and 1 in assignment' in a fortran 95 program. -

-
i writing program in fortran find velocity of parachuting person in relation time. keep getting error can't fix. new programming , appreciated. the error is v(i+1)=v(i)+[32-((c*v(i)*v(i))/m)]*(h) 1 error: incompatible ranks 0 , 1 in assignment @ (1) and program is program para integer :: real :: v(11) !velocity real :: q !initial velocity real :: h !time step real :: c !drag coefficient real :: m !mass ! gravity equal 32 ft/s^2 write (*,*)'enter time step' read(*,*)h write(*,*)'enter initial velocity' read(*,*)q write(*,*)'enter drag coefficient' read(*,*)c write(*,*)'enter mass' read(*,*)m i=1,10 ! 1 10, 1 being interval. end v(i+1)=v(i)+[32-((c*v(i)*v(i))/m)]*(h) q=v(1) end program you cannot use [] normal parenthesis in expressions. array constructor, [ items ] means array items elements. end do should after line.
Read more