有關資料結構DFS和BFS作業!!!

arou65271

可以麻煩大大們幫我解決這作業的問題嗎?
研究好幾天,程式卻毫無增進,下禮拜就要繳交這作業~
這作業對成績很重要!
拜託大大們,可以幫幫小弟嗎?幫小弟把程式碼打出來~
開發語言用C或C++都可以!萬衷感謝!!!
------------以下是題目-------------
實施adjacent matrix and adjacent list 為一個給定的節點隨機生成具有n和e邊緣。
你的程式需要有一個界面，可以輸入 n（如10）和E（例如，15），
...

瀏覽完整內容，請先 註冊 或 登入會員

回復

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

arou65271

都網路上面找的，
應該不難改

Adj. Matrix

1. /* Program for creation of adjacency matrix */
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. #define max 20
   
5. 
   
6. int adj[max][max]; /*Adjacency matrix */
   
7. int n; /* Denotes number of nodes in the graph */
   
8. void main()
   
9. {
   
10. int max_edges,i,j,origin,destin;
    
11. char graph_type;
    
12. 
    
13. p rintf("Enter number of nodes : ");
    
14. scanf("%d",&n);
    
15. p rintf("Enter type of graph, directed or undirected (d/u) : ");
    
16. fflush(stdin);
    
17. scanf("%c",&graph_type);
    
18. 
    
19. if(graph_type=='u')
    
20. max_edges=n*(n-1)/2;
    
21. else
    
22. max_edges=n*(n-1);
    
23. 
    
24. for(i=1;i<=max_edges;i++)
    
25. {
    
26. p rintf("Enter edge %d( 0 0 to quit ) : ",i);
    
27. scanf("%d %d",&origin,&destin);
    
28. if( (origin==0) && (destin==0) )
    
29. break;
    
30. if( origin > n || destin > n || origin<=0 || destin<=0)
    
31. {
    
32. p rintf("Invalid edge!\n");
    
33. i--;
    
34. }
    
35. else
    
36. {
    
37. adj[origin][destin]=1;
    
38. if( graph_type=='u')
    
39. adj[destin][origin]=1;
    
40. }
    
41. }/*End of for*/
    
42. 
    
43. p rintf("The adjacency matrix is :\n");
    
44. for(i=1;i<=n;i++)
    
45. {
    
46. for(j=1;j<=n;j++)
    
47. p rintf("%4d",adj[i][j]);
    
48. p rintf("\n");
    
49. }
    
50. }/*End of main()*/

複製代碼

BFS and DFS

1. /*TO FIND THE BFS AND DFS OF THE GIVEN GRAPH*/
   
2. 
   
3. #define size 20
   
4. 
   
5. int a[10][10],vertex[10],n,e;
   
6. 
   
7. /*STACK FUNCTIONS*/
   
8. #define bottom -1
   
9. 
   
10. int stack[size],top=bottom;
    
11. int stackempty()
    
12. {
    
13. return(top=bottom) ? 1:0;
    
14. }
    
15. int stackfull()
    
16. {
    
17. return(top==size-1) ? 1:0;
    
18. }
    
19. 
    
20. void push(int item)
    
21. {
    
22. if(stackfull())
    
23. p rintf("7
    
24. 
    
25. STACK IS FULL");
    
26. else
    
27. stack[++top]=item;
    
28. }
    
29. 
    
30. int pop()
    
31. {
    
32. if(stackempty())
    
33. {
    
34. p rintf("7
    
35. 
    
36. STACK IS EMPTY");
    
37. return -1;
    
38. }
    
39. else
    
40. return stack[top--];
    
41. }
    
42. 
    
43. int peep()
    
44. {
    
45. if(stackempty())
    
46. {
    
47. p rintf("7
    
48. 
    
49. STACK IS EMPTY");
    
50. return -1;
    
51. }
    
52. else
    
53. return stack[top];
    
54. }
    
55. 
    
56. /* QUEUE FUNCTIONS */
    
57. #define start -1
    
58. 
    
59. int q[size];
    
60. int f=start,r=start;
    
61. 
    
62. int qempty(){ return(f==r)?1:0; }
    
63. int qfull(){ return(r==size-1)?1:0;}
    
64. 
    
65. void addq(int c)
    
66. {
    
67. if(qfull())
    
68. p rintf("7
    
69. 
    
70. QUEUE IS FULL");
    
71. else
    
72. q[++r]=c;
    
73. }
    
74. 
    
75. int delq()
    
76. {
    
77. if(qempty())
    
78. {
    
79. p rintf("7
    
80. 
    
81. QUEUE IS EMPTY");
    
82. return -1;
    
83. }
    
84. else
    
85. return q[++f];
    
86. }
    
87. // j is unvisited adjecent vertex to i
    
88. int adjvertex(int i)
    
89. {
    
90. int j;
    
91. for(j=0;j
    
92. if(a[i][j]==1&&vertex[j]==0)
    
93. return j;
    
94. return n;
    
95. }
    
96. 
    
97. int visitall()
    
98. {
    
99. int i;
    
100. for(i=0;i
     
101. if(vertex[i]==0)
     
102. return 0;
     
103. return 1;
     
104. }
     
105. 
     
106. /*FUNCTION FOR BFS*/
     
107. void bfs()
     
108. {
     
109. int i,j,k,cur=0;//current vertex is startting vertex
     
110. for(i=0;i
     
111. vertex[i]=0;//not visited
     
112. p rintf("
     
113. 
     
114. BFS path => V%d ",cur+1);
     
115. addq(cur);
     
116. vertex[cur]=1;//marking visited vertex
     
117. while(!visitall())
     
118. {
     
119. if(qempty())
     
120. {
     
121. p rintf("7
     
122. 
     
123. GRAPH IS DISCONNECTED");
     
124. break;
     
125. }
     
126. cur=delq();
     
127. //visit all vertices which are adjecent to current vertex
     
128. for(j=0;j
     
129. {
     
130. //adjecent are not visited
     
131. if(a[cur][j]==1&&vertex[j]==0)
     
132. {
     
133. p rintf("V%d ",j+1);
     
134. addq(j);
     
135. //marking visited vertex
     
136. vertex[j]=1;
     
137. }
     
138. }
     
139. }
     
140. }
     
141. 
     
142. /*FUNCTION FOR DFS*/
     
143. void dfs()
     
144. {
     
145. int i,j,k,cur=0;//current vertex is startting vertex
     
146. for(i=0;i
     
147. vertex[i]=0;//not visited
     
148. p rintf("
     
149. 
     
150. DFS path => V%d ",cur+1);
     
151. push(cur);
     
152. vertex[cur]=1;//marking visited vertex
     
153. while(!visitall())
     
154. {
     
155. do
     
156. {
     
157. cur=adjvertex(peep());
     
158. if(cur==n) pop();
     
159. }
     
160. while(cur==n&&!stackempty());
     
161. if(stackempty())
     
162. {
     
163. p rintf("7
     
164. 
     
165. GRAPH IS DISCONNECTED");
     
166. break;
     
167. }
     
168. if(cur!=n)
     
169. {
     
170. p rintf(" V%d ",cur+1);
     
171. push(cur);
     
172. vertex[cur]=1;//marking visited vertex
     
173. }
     
174. }
     
175. }
     
176. 
     
177. /*MAIN PROGRAM*/
     
178. void main()
     
179. {
     
180. int i,j,k;
     
181. clrscr();
     
182. for(i=0;i<10;i++)
     
183. for(j=0;j<10;j++)
     
184. a[i][j]=0;
     
185. 
     
186. p rintf("
     
187. ENTER NO OF VERTICES & EDGES OF UNDIRECTED GRAPH : ");
     
188. scanf("%d%d",&n,&e);
     
189. 
     
190. p rintf("
     
191. ENTER EDGES AS PAIR OF VERTICES
     
192. 
     
193. ");
     
194. for(k=1;k<=e;k++)
     
195. {
     
196. p rintf("EDGE %d =>",k);
     
197. scanf("%d%d",&i,&j);
     
198. //for undirected graph
     
199. a[i-1][j-1]=1;
     
200. }
     
201. 
     
202. dfs();
     
203. bfs();
     
204. getch();
     
205. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

arou65271

謝謝妳喔~
可是小弟還是改不出來@@"
對了~DFS和BFS那邊程式碼錯很多耶~
都不能跑@@"
可以麻煩大大幫我把這一題完整打出來嗎?
小弟笨笨的,好難的作業啊!!!