Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.05.2011, 19:00   #1
Lodyr
Пользователь
 
Регистрация: 15.12.2009
Сообщений: 69
По умолчанию Нарисовать граф по матрице смежности

Задача у меня следующая - нарисовать деревья от результата поиска в ширину по исходному графу.
Использую проект, вот код
Код:
#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);
вопрос в следующем, как нарисовать граф в диалоговом меню по матрице смежности?
Lodyr вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нарисовать дерево (связный граф без циклов) в Pascal Машуля Помощь студентам 3 20.12.2010 13:28
Матрица смежности rubakKa Общие вопросы C/C++ 5 18.12.2010 21:33
Список смежности (С++) phantom4eg Помощь студентам 0 21.04.2010 18:27
TurboPascal: граф, матрица смежности и матрица инцидентности. ulala Помощь студентам 0 02.12.2009 10:11
Помогите нарисовать граф в Exsel. Ol'ga Общие вопросы Delphi 2 13.06.2009 08:39