Графы. решение практических задач с использованием графов (С++) — страница 10

  • Просмотров 21578
  • Скачиваний 923
  • Размер файла 47
    Кб

vertex = 1; // Первая вершина FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл void add(Node*& list,int data){ //Добавление смежной вершины if(!list){list=new Node;list->inf=data;list->next=0;return;} Node *temp=list; while(temp->next)temp=temp->next; Node *elem=new Node; elem->inf=data; elem->next=NULL; temp->next=elem; } void del(Node* &l,int key){ // Удаление вершины key из списка if(l->inf==key){Node *tmp=l; l=l->next; delete tmp;} else{ Node *tmp=l; while(tmp){ if(tmp->next) // есть следующая вершина

if(tmp->next->inf==key){ // и она искомая Node *tmp2=tmp->next; tmp->next=tmp->next->next; delete tmp2; } tmp=tmp->next; } } } bool eiler(Node **gr,int num){ // Определение эйлеровости графа int count; for(int i=0;i<num;i++){ //проходим все вершины count=0; Node *tmp=gr[i]; while(tmp){ // считаем степень count++; tmp=tmp->next; } if(count%2==1)return 0; // степень нечетная } return 1; // все степени четные } void eiler_path(Node **gr){ //Построение цикла Node *S = init();// Стек для пройденных вершин int v=vertex;// 1я вершина (произвольная) int u; push(S,v); //сохраняем ее в стек

while(S){ //пока стек не пуст v = peek(S); // текущая вершина if(!gr[v]){ // если нет инцидентных ребер v=pop(S); fprintf(fo,"%d ",v); //выводим вершину }else { u=gr[v]->inf; push(S,u); //проходим в следующую вершину del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро } } } int main(){ int n; // Количество вершин int zn;// Текущее значение fscanf(fi,"%d",&n); graph=new Node*[n]; for(int i=0;i<n;i++)graph[i]=NULL; for(int i=0;i<n;i++) // заполняем массив списков for(int j=0;j<n;j++){ fscanf(fi,"%d",&zn); if(zn) add(graph[i],j); } if(eiler(graph,n))eiler_path(graph);

else fprintf(fo,"Граф не является эйлеровым."); return(0); } 3.Построить остовное дерево минимальной стоимости для связанного взвешенного графа, используя алгоритм Прима. #include <iostream.h> #include <stdio.h> #include <values.h> FILE* fi = fopen("p_graph.txt","r"); //Входной файл FILE* fo = fopen("p_ostov.txt","w"); //Выходной файл struct edge{ // Структура для хранения ребра int b,e; int weigh; }; int **graph; // исходный граф int p; // количество вершин в графе edge *SST; // остов int num_ver=0; //

количество ребер в остове int *S; // вершины, включенные в остов int num_s=0; //количество вершин в остове int calc_ver(){ // подсчитывает число ребер в графе int i=0,j,res=0; while(i<p){j=i+1; while(j++<p)if(graph[i][j])res+=1; i++;} return res; } bool added(int v){ // проверяет: добавлена вершина v в остов for(int i=0;i<num_s;i++)if(v==S[i])return 1; return 0; } void prim(){ // построение остова S = new int[calc_ver()]; int *alf = new int[p]; // ближайшие вершины, добавленные в остов int *bet = new int[p]; // длины ребер, соединяющие вершины с остовом int u =

0; // произвольная вершина S[num_s] = u; num_s++; // добавляем в остов for(int v=0;v<p;v++) if(graph[v][u]){alf[v] = u; bet[v] = graph[u][v];}//u - ближайшая вершина else {alf[v] = -1; bet[v] = MAXINT;} int w,x; for(int i=0;i<p-1;i++){ x = MAXINT; for(int v=0;v<p;v++){ // поиск ближайшей к остову вершины if(bet[v]<x && !added(v)){w = v; x = bet[v];} } S[num_s] = w; num_s++; // добавляем найденную вершину к остову // и ребро SST[num_ver].b=alf[w];SST[num_ver].e=w;SST[num_ver].weigh=graph[alf[w]][w]; num_ver++; for(int v=0;v<p;v++){ if(graph[v][w] && !added(v))// меняем ближайшую вершину остова