Задача у меня следующая - нарисовать деревья от результата поиска в ширину по исходному графу.
Использую проект, вот код
Код:
#include "graph.h"
#include "queue"
#include "iostream"
void BFS (int **&ar, int **father, int **uses, int **&T, int start, int &num, int n)
{int current = start; //tekush vershina
queue<int> que;//ocered poseshen vershin
que.push(start);//polos versh v ochered
(*uses)[start]=num++;//yvelichiv schetchik poseshenii ykazali chto v start mi prishli (num++)-oi
while (!que.empty())//pokaochered ne pusta
{current=que.front();//dostaem iz ochered vershiny stoishyu v nachale
que.pop();//ydalili
for(int i=1;i<=n;i++)//perebiraem spisok vsex vershin
{if (ar[current][i]>0)//esli tekyshaa smejna c ocherednoi
{int u=i;//oboznachali cherez u
if ((*uses)[u]==-1)//esli vershina u eshe ne poseshalac,to
{que.push(u);//poloshili v ocherd
(*father)[u]=current;//ykazivaem otkuda prishli v u
(*uses)[u]=num++;//ykazivaem kakoi po schety bila u
}
else if((*uses)[u]>(*uses)[current]) //esli vershiny u mi posehali pozhe tekysh, - yslovie poperechnosti
{int t=++T[0][0];//yvelichib scetchik kol poperechn reber
T[t][0]=current;//dobavlaem ego
T[t][1]=u;
}
}}}}
#include "graph.h"
int main()
{
ifstream f1;
f1.open("input.txt");
ofstream f2;
f2.open("output.txt");
///////////////////////////////////
int n,M,i,j,start,num;
f1>>n>>M;
int *ar1=new int[M*2];
for (i=0;i<M*2;i++)
f1>>ar1[i];
int **ar=new int*[n+1];
int *father,*uses,**T;
/////////////////////
for (i=1;i<=n+1;i++)
ar[i]=new int[n];
for (i=1;i<n+1;i++)
for (j=1;j<n+1;j++)
ar[i][j]=0;
//////////////////////
int k=0,a=0,b=0;
while(k<M*2)
{
a=ar1[k];
b=ar1[k+1];
ar[a][b]=1;
ar[b][a]=1;
k+=2;
}
/////////////////////////
f2<<n<<endl;
for (i=1;i<n+1;i++)
{
for (j=1;j<n+1;j++)
f2<<ar[i][j]<<" ";
f2<<endl;
}
int m=n*(n-1)/2;
father=new int[n+1];
uses=new int[n+1];
T=new int*[m+1];
f1>>start;
while(start!=0)
{for (i=0;i<=m;i++)//t[o][o] xranit kol-vo reber
{T[i]=new int[2];
T[i][0]=0;
T[i][1]=0;
}
(father)[0]=n;
(uses)[0]=n;
for(i=1;i<=n;i++)
{father[i]=-1;
uses[i]=-1;}
num=1;//scetcik posledov obxoda vershin
BFS(ar,&father,&uses,T,start,num,n);
f2<<"thevertex"<<" "<<start<<endl;
f2<<"the list of poperec"<<endl;
f2<<T[0][0]<<endl;
for(i=1;i<=T[0][0];i++)
{f2<<T[i][0]<<" "<<T[i][1]<<endl;
/////////////////////
int k=0,a=0,b=0;
while(k<M*2)
{ a=ar1[k];b=ar1[k+1];
if(T[i][0]==a && b==T[i][1])
{ar[a][b]=0; ar[b][a]=0; k+=2;}
else k+=2;
}
for (i=1;i<n+1;i++)
{ for (j=1;j<n+1;j++)
f2<<ar[i][j]<<" ";
f2<<endl;
}
}
/////////////////////////////////////
f2<<endl<<"father is"<<endl;
for(i=1;i<=n;i++)
{f2<<i<<" "<<father[i]<<endl;}
f2<<endl<<"the uses is"<<endl;
for(i=1;i<=n;i++)
{f2<<i<<" "<<uses[i]<<endl;}
f2<<endl;
///////////////////////////
int k=0,a=0,b=0;
while(k<M*2)
{ a=ar1[k]; b=ar1[k+1];
ar[a][b]=1; ar[b][a]=1; k+=2;
}
//////////////////////////////////
f1>>start;
}
/////////////////////////////////////////////
f1.close();
f2.close();
return 0;
}
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
void BFS (int **&ar,int **father, int **uses, int **&T, int start, int &num, int n);
вопрос в следующем, как нарисовать граф в диалоговом меню по матрице смежности?