Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Vanya_1234
0 / 0 / 1
Регистрация: 19.05.2013
Сообщений: 33
1

Прокомментировать код программы (Обход ориентированного графа в ширину)

07.02.2015, 14:45. Просмотров 290. Ответов 0
Метки нет (Все метки)

Здравствуйте! Очень нужно написать прогу для обхода ориентированного графа в ширину. Нашёл код, но как он работает понять немогу. Помогите пожалуйста! !!
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
 
typedef struct Q
{
    int data[MAX];
    int R,F;
}Q;
 
typedef struct node
{
    struct node *next;
    int vertex;
}node;
 
void enqueue(Q *,int);
int dequque(Q *);
int empty(Q *);
int full(Q *);
void BFS(int);
void readgraph();            //create an adjecency list
void insert(int vi,int vj);     //insert an edge (vi,vj)in adj.list
void DFS(int i);
int visited[MAX];
node *G[20];                //heads of the linked list
int n;                       // no of nodes
 
void main()
{
    int i,op;
    clrscr();
    do
      { printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit");
        printf("\nEnter Your Choice: ");
        scanf("%d",&op);
        switch(op)
         { case 1: readgraph();break;
           case 2: printf("\nStarting Node No. : ");
               scanf("%d",&i);
               BFS(i);break;
           case 3:  for(i=0;i<n;i++)
             visited[i]=0;
               printf("\nStarting Node No. : ");
               scanf("%d",&i);
               DFS(i);break;
          }
       }while(op!=4);
}
 
 
void BFS(int v)
{
    int w,i,visited[MAX];
    Q q;
 
    node *p;
    q.R=q.F=-1;              //initialise
    for(i=0;i<n;i++)
        visited[i]=0;
    enqueue(&q,v);
    printf("\nVisit\t%d",v);
    visited[v]=1;
    while(!empty(&q))
    {
        v=dequeue(&q);
        //insert all unvisited,adjacent vertices of v into queue
        for(p=G[v];p!=NULL;p=p->next)
        {
            w=p->vertex;
            if(visited[w]==0)
            {
                enqueue(&q,w);
                visited[w]=1;
                printf("\nvisit\t%d",w);
            }
        }
    }
}
 
void DFS(int i)
{
    node *p;
    printf("\n%d",i);
    p=G[i];
    visited[i]=1;
    while(p!=NULL)
    {
        i=p->vertex;
        if(!visited[i])
            DFS(i);
        p=p->next;
    }
}
 
 
int empty(Q *P)
{
    if(P->R==-1)
        return(1);
    return(0);
}
 
int full(Q *P)
{
    if(P->R==MAX-1)
        return(1);
    return(0);
}
 
void enqueue(Q *P,int x)
{
    if(P->R==-1)
    {
        P->R=P->F=0;
        P->data[P->R]=x;
    }
    else
    {
        P->R=P->R+1;
        P->data[P->R]=x;
    }
}
 
int dequeue(Q *P)
{
    int x;
    x=P->data[P->F];
    if(P->R==P->F)
    {
        P->R=-1;
        P->F=-1;
    }
    else
        P->F=P->F+1;
    return(x);
}
 
void readgraph()
{     int i,vi,vj,no_of_edges;
    printf("\nEnter no. of vertices :");
    scanf("%d",&n);
    //initialise G[] with NULL
    for(i=0;i<n;i++)
        G[i]=NULL;
    //read edges and insert them in G[]
    printf("\nEnter no of edges :");
    scanf("%d",&no_of_edges);
    for(i=0;i<no_of_edges;i++)
    {
        printf("\nEnter an edge (u,v)  :");
        scanf("%d%d",&vi,&vj);
        insert(vi,vj);
        insert(vj,vi);
    }
}
 
void insert(int vi,int vj)
{
    node *p,*q;
    //acquire memory for the new node
    q=(node *)malloc(sizeof(node));
    q->vertex=vj;
    q->next=NULL;
    //insert the node in the linked list for the vertex no. vi
    if(G[vi]==NULL)
        G[vi]=q;
    else
    {
        // go to the end of linked list
        p=G[vi];
        while(p->next!=NULL)
            p=p->next;
        p->next=q;
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2015, 14:45
Ответы с готовыми решениями:

Представление циклического ориентированного графа списком
Доброго дня, форумчане. Скажите, правильно ли я мыслю? Решил сделать граф в качестве треугольника...

Прокомментировать код программы, работающей с массивом
#define K 50 int x, j; /*ввод x */.. for (j=0; j&lt;K-1; j++) x=x; Вот что эта программа...

Найти все пути, соединяющие две вершины ориентированного графа.
Помогите дописать программу. #include&lt;stdio.h&gt; #include&lt;conio.h&gt; int visited; int A; void...

Обход графа в ширину - перевести код с C++
Добрый вечер. Умоляю, помогите перевести нижепредставленный код в C#, какой день уже мучаюсь, все...

Обход ориентированного графа сверху вниз
Здравствуйте! У меня есть ориентированный граф. Нужно обойдя его, получить его слои. Поясню на...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2015, 14:45

Обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии от данной вершины
Реализуйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном...

Выполнить обход в ширину неориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица инциденций
Буду очень благодарен, если поможете Выполнить обход в ширину неориентированного графа, начиная с...

Обход графа в ширину
Нужно вывести список всех посещенных вершин графа, заданного матрицей смежности. Есть функция...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru