Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Последовательность ребер

Библиотеки для работы с графами.

1) Реализации:

1.1) Таблица смежностей:

//header

 

struct graph{

int m;

int n;

int mas[101][101];

};

graph create_graph();

bool is_emtpty(graph Graph);

void neigs(graph Graph, int k, int result[100]);

void add_edge(graph Graph, int from, int to);

void delete_top(graph Graph, int top);

void delete_edge(graph Graph, int from, int to);

 

 

//.cpp

 

#include < iostream>

#include " table1.h"

using namespace std;

graph create_graph(){

graph Gr;

for(int i=0; i< 101; i++){

for(int j=0; j< 101; j++){

Gr.mas[i][j]=0;

}

}

return Gr;

}

bool is_empty(graph g){

int i=0, j=0;

bool stop=false;

while((i< 101)& & (! stop)){

j=0;

while((j< 101)& & (! stop)){

stop=(g.mas[i][j]! =0);

j++;

}

i++;

}

return! stop;

}

void neigs(graph Graph, int k, int result[100]){

int i;

for(i=0; i< 101; i++) result[i]=0;

int s=0;

for(i=0; i< 101; i++){

if(Graph.mas[k][i]! =0){

result[s]=i;

s++;

}

}

}

void add_edge(graph Graph, int from, int to){

Graph.mas[from][to]=1;

}

void delete_top(graph Graph, int top){

for(int i=0; i< 101; i++){

Graph.mas[top][i]=0;

}

}

 

void delete_edge(graph Graph, int from, int to){

Graph.mas[from][to]=0;

}

 

Последовательность ребер

//header

const int n=100; [R1]

struct graph{

int m;

int N;

int mas[2][n];

};

graph create_graph();

bool is_emtpty(graph Graph);

void eigs(graph Graph, int k, int result[100], int& num);

void add_edge(graph Graph, int from, int to);

void delete_top(graph Graph, int top);

void delete_edge(graph Graph, int from, int to);

 

//.cpp

#include< iostream>

#include " table2.h"

using namespace std;

graph create_graph(){

graph Graph;

for(int i=0; i< n; i++){

Graph.mas[0][i]=0;

Graph.mas[1][i]=0;

}

return Graph;

[R2] }

bool is_emtpty(graph Graph){

int i=0; bool stop=false;

while((i< n)& & (! stop)){

stop=((Graph.mas[0][i]! =0)||(Graph.mas[1][i]! =0));

i++;

}

return! stop;

[R3] }

void eigs(graph Graph, int k, int result[100], int& number){

int i; number=0;

for(i=0; i< n; i++){

result[i]=0;

}

for(i=0; i< n; i++){

if(Graph.mas[0][i]==k){

result[number]=Graph.mas[1][i];

number++;

}

}

}

 

void add_edge(graph Graph, int from, int to){

int i=0;

while(Graph.mas[i]==0) i++;

Graph.mas[0][i]=from;

Graph.mas[1][i]=to;

}

void delete_top(graph Graph, int top){

for(int i=0; i< n; i++){

if(Graph.mas[0][i]==top){

Graph.mas[0][i]=0;

Graph.mas[1][i]=0;

}

[R4] }

}

void delete_edge(graph Graph, int from, int to){

for(int i=0; i< n; i++){

if((Graph.mas[0][i]==from)& & (Graph.mas[1][i]==to)){

Graph.mas[0][i]=0;

Graph.mas[1][i]=0;

 

}

}

}

 

1.3) Список соседей для каждой вершины:

//header

struct graph{

int m;

int n;

int mas[101][100];

};

graph create_graph();

bool is_emtpty(graph Graph);

void read_graph(graph Graph);

void write_graph(graph Graph);

void eigs(graph Graph, int k, int result[100]);

void add_edge(graph Graph, int from, int to);

void delete_top(graph Graph, int top);

void delete_edge(graph Graph, int from, int to);

 

//.cpp

#include < iostream>

#include " table3.h"

using namespace std;

graph create_graph(){

graph Gr;

int i=1;

for(i=1; i< 101; i++){

for(int j=0; j< 100; j++){

Gr.mas[i][j]=0;

}

}

return Gr;

}

void read_graph(graph g){

int s;

cout< < " Введите количество вершин" < < endl;

int i;

cin> > g.n;

for(i=1; i< g.n; i++){

int j=0;

cout< < " Введите количество соседей у " < < i< < " вершины" < < endl;;

cin> > s;

while(j< s){

cout< < j+1< < " сосед";

cin> > g.mas[i][j];

j++;

}

}

}

void write_graph(graph g){

int i=1;

while((g.mas[i][0]! =0)& & (i< 101)){

int j=0;

while((g.mas[i][j]! =0)& & (j< 100)){

cout< < g.mas[i][j]< < ", ";

j++;

}

cout< < endl;

i++;

}

}

bool is_empty(graph g){

int i=1, j=0;

bool stop=false;

while((i< 101)& & (! stop)){

j=0;

while((j< 100)& & (! stop)){

stop=(g.mas[i][j]! =0);

j++;

}

i++;

}

return! stop;

}

void eigs(graph Graph, int k, int result[100]){

 

for(int i=1; i< 101; i++){

result[i]=Graph.mas[k][i];

}

[R5] [R6] }

 

void add_edge(graph Graph, int from, int to){

int i=0;

while((Graph.mas[from][i]! =0)& & (i< 100)) i++;

Graph.mas[from][i]=to;

}

void delete_top(graph Graph, int top){

for(int i=0; i< 100; i++){

Graph.mas[top][i]=0;

}

}

 

void delete_edge(graph Graph, int from, int to){

for(int i=0; i< 100; i++){

if(Graph.mas[from][i]==to) Graph.mas[from][i]=0;

}

}[R7]

 

 

2) Обходы:

<== предыдущая лекция | следующая лекция ==>
 | 
Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.014 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал