VPF::обход 'графа' - Форум программистов

chaos

Дата 17.12.2004, 18:15 (ссылка)

(нет голосов)

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

Репутация: нет
Всего: 44

Вот еще переписал вроде для малого кол-ва точек работает, а решил для 30, все писец загнулось smile

(

Код


#include <stdio.h>
#include <conio.h>

#define MAX 30

int cMatrix[MAX][MAX];
int pMatrix[MAX*MAX];
int Weight[MAX];
int hod[MAX*MAX];
int ss = 0, N=0, vS, vE;
char *FILENAME = "c:\\graphp.txt";


void init()
{
	int q;
	FILE *f = fopen(FILENAME, "r");
	fscanf(f,"%d\n",&N);
	fscanf(f,"%d %d\n", &vS, &vE);
	for (int i=0; i<N; i++)
  for (int j=0; j<N; j++)
  {
  	fscanf(f,"%d", &q);
  	cMatrix[i][j] = q;
  	pMatrix[i*N+j] = 0;
  	hod[i*N+j] = 0;
  }
	for (i=0; i<N; i++)
	{
  fscanf(f,"%d", &q);
  Weight[i] = q;
	}
	fclose(f);
}


int rez()
{
	int s=0;
	for (int n=0; n<ss-1; n++)
  s += Weight[hod[n]]*Weight[hod[n+1]];
	return s;
}


void beanGraph(int s, int e, int *m)
{
	int mm[MAX][MAX], mmm[MAX], a, b, c;
	hod[ss] = s;	

	ss++;	
	printf("stack = %d\n",ss);
	
	printf("%d\n", s);

	for (a=0; a<N; a++)
	{
  for (b=0; b<N; b++) 
  {
  	mm[a][b] = *(m+a*N+b); 
  	printf("%d ", mm[a][b]); 
  }
  printf("\n");
	}

	for (a=0; a<N; a++) if (mm[e][a]) mm[s][a] = mm[e][a];

	if (s == vE) 
	{
  printf("return\n");
  //if (ss == N)
  //{
  	printf("%d  hod-- ", ss); 
  	for (a=0; a<ss; a++) printf("%d ", hod[a]);
  	printf("    %d", rez());
  //}
  printf("\n");
  //ss -= 1;
  return;
	}

	for (c=0; c<N; c++)
	{

  //printf("---%d\n",s); 
  if (cMatrix[s][c] && mm[s][c]==0)
  {
  	//mm[s][c] = 1;
  	mm[c][s] = 1;
  	for (a=0; a<N; a++)	for (b=0; b<N; b++) mmm[a*N+b] = mm[a][b]; 
  	beanGraph(c,s,mmm);
  	ss -= 1;
  }
  //mm[s][c] = 1;
	}
}



void main()
{
	init();
	beanGraph(vS,vS,pMatrix);
	
}

вормат данных:

кол-во вершин
начальная вершина конечная
матрица смежности
вес каждой вершины

Пример:
4
1 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
1
2
3
4

Это сообщение отредактировал(а) chaos - 17.12.2004, 18:34

chaos

Дата 24.12.2004, 16:12 (ссылка)

(нет голосов)

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

Репутация: нет
Всего: 44

все написал, и даже работает smile

кому интересно вот исходник на срр

Код


#include <stdio.h>  //подключаем библиотеки
#include <conio.h>  
#include <string.h>  	
#include <process.h>


char **cMatrix;    //описываем указатель
char *pMatrix, *Weight;  //описываем указатели
int N=0, vS, vE, pog, kolvo, skol=0, price, fexit=0;  //описываем переменные
char *FILENAME;        	//описываем указатель на строку


void init()  	//функция инициализации - читает файл с даннывми
{
	int i,j,q;  //описание переменных
	FILE *f = fopen(FILENAME, "r");  //описываем файловую переменную и открываем файл
	fscanf(f,"%d\n",&N);    //читаем из файла кол-во вершин
	fscanf(f,"%d %d\n", &vS, &vE);  //читаем стартовую и финишную вершину
	fscanf(f,"%d %d %d", &price, &pog, &kolvo);	//читаем необходимую цену для поиска пути,
            //погрешность, кол-во путей для поиска 
        	

	Weight  = new char[N];  	//выделяем память для N вершин - матрица весов
	pMatrix = new char[N];  	//выделяем память для N вершин - матрица переходов
	
	cMatrix = new char*[N];  	//выделяем память для 2-х мерного массива

	for (i=0; i<N; i++)    
	{
  cMatrix[i] = new char[N];	//выделяем память для каждой строки матрицы
  for (j=0; j<N; j++)
  {
  	fscanf(f,"%d", &q);  //читаем матрицу смежности
  	cMatrix[i][j] = q;  //записываем в массив
  }
	}

	for (i=0; i<N; i++)
	{
  fscanf(f,"%d", &q);  	//читаем вес вершины
  Weight[i] = q;    //записываем в массив
  pMatrix[i] = 0;    //инициализируем матрицу переходов нулями
	}

	fclose(f);      //закрываем файл
}


int price_tour(char *p)  //функция подсчитывает результат по правилу ab+bc+cd...
{
	int sum=0;    //для суммы
	for (int n=1; n<N; n++) sum += Weight[p[n-1]]*Weight[p[n]];	//считаем
	return sum;    //возвращаем результат
}

void beanGraph(int s, int e, char *m)	//функция обхода графа
{
	if (fexit) return;
	int c,a;      	//описываем переменные
	m[s] = e;      	//записываем в массив переходов очередную вершину

	if (s == vE)      //проверка на достижимость конца пути
	{	
  int f=0;      //описываем переменную
  char *hod = new char[N];  //выделяем память для массива
  for (int x=0; x<N; x++)	if (m[x] == 0) f = 1;//проверка: всели вершины обошли
  if (!f)  	//если все то ...
  {
  	f=0; 
  	for (c=0; c<N; c++)
    for (a=0; a<N; a++) 
    	if (m[a]==c+1)
    	{
//      printf("%d ", a);  
      hod[f++] = a;	//записываем ходы для передачи в ф. price_tour
    	}
  	f = price_tour(hod);	//функция возвращает посчитанный результат
  	if (price <= f+pog && price >= f-pog)	//проверяем на условие
  	{
    if (skol >= kolvo) {fexit=1; return;};	//если необходимые пути найдены то закрываем программу
    skol++;  	
    for (a=0; a<N; a++) printf("%d ", hod[a]);//вывод пути
    printf("price tour = %d\n", f);//вывод цены пути
  	}
  	delete[] hod;	//освобождаем память
  }
  return;	//выход из функции
	}

	char *mmm = new char[N];  //выделяем память

	for (c=0; c<N; c++)  //цикл по смежным вершинам
	{	
  if (cMatrix[s][c] && m[c]==0)  //если не обходили то ...
  {
  	memcpy(mmm, m, N);    //копируем содержимое одного массива в другой
  	beanGraph(c,e+1,mmm);  	//вызываем функцию
  }
	}
	delete[] mmm;  	//освобождаем память
}    

int main(int argc, char *argv[])  //главная функция получает название файла с данными
{
	if (argc == 2)      //проверка на один аргумент
	{
  FILENAME = argv[1];    //имя файла
  init();      	//вызываем функцию	
  beanGraph(vS,1,pMatrix);  //вызываем функцию	
  for(vS=0; vS<N; vS++) delete cMatrix[vS];	//освобождаем память(двумерный массив)
  delete[] cMatrix; //освобождаем память
  delete[] Weight;//освобождаем память
  delete[] pMatrix;//освобождаем память
	}
	else printf("Usage: kgraph.exe file_data.txt\n");//выводим подсказку
	getch();  //ждем нажатия клавиши
	return 0;  //конец
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »