1 #include<stdio.h>
2 #include<stdlib.h>
3
4 #define OK 1
5 #define NO 0
6 #define TRUE 1
7 #define FALSE 0
8 #define ERROR -1
9
10 #define MaxVerTexNum 100
11 #define INFINITY 65535
12
13
14
15
16 typedef
int ElementType;
17 typedef
int Status;
18 typedef
int WeightType;
19 typedef
int Vertex;
20 typedef
char DataType;
21
22 typedef
int Position;
23 typedef
struct QNode{
24 ElementType *
Data;
25 Position Front, Rear;
26 int MaxSize;
27 }QNode,*
Queue;
28
29
30
31 Status Visited[MaxVerTexNum];
32
33 typedef
struct ENode{
34 Vertex V1,V2;
//有向边<v1,V2>
35 WeightType Weight;
//权重
36 }ENode,*
PtrToENode ;
37
38 typedef PtrToENode Edge;
39
40 Status IsFull( Queue Q );
41
42 typedef
struct GNode{
43 int Nv;
//顶点数
44 int Ne;
//边数
45 WeightType G[MaxVerTexNum][MaxVerTexNum];
//邻接矩阵
46 DataType Data[MaxVerTexNum];
//save data of the Vertex;
47 }GNode,*
PtrToGNode;
48
49 typedef PtrToGNode MGraph;
50
51 ElementType DeleteQ( Queue Q );
52
53 Queue CreateQueue(
int MaxSize );
54
55 Status IsEmpty( Queue Q );
56
57 Status AddQ( Queue Q, ElementType X );
58
59 MGraph CreateGraph(
int VertexNum);
//Create a Graph with VertexNum Vertex but without an ege;
60
61 void InsertEdge(MGraph Graph,Edge E);
62
63 MGraph BuildGraph();
64
65 void Visit(Vertex V);
66
67 void DFS(MGraph Graph,Vertex S);
68
69 void DFS1(MGraph Graph,Vertex S);
70
71 Status IsEdge(MGraph Graph,Vertex V,Vertex W);
//检查<V,W>是不是图中的一条边，即W是不是V的邻接点
72
73 void BFS(MGraph Graph,Vertex S);
74
75 int main(
int argc,
char**
argv)
76 {
77 MGraph Graph;
78 Graph=
BuildGraph();
79 printf(
"广度优先遍历\n");
80 BFS(Graph,
1);
81 printf(
"深度优先遍历\n");
82 DFS(Graph,
1);
83 return 0;
84 }
85
86 MGraph CreateGraph(
int VertexNum){
87 Vertex V,W;
88 MGraph Graph;
89 Graph=(MGraph)
malloc(
sizeof(GNode));
//form a Graph
90 Graph->Nv=
VertexNum;
91 Graph->Ne=
0;
//
92 for(V=
0;V<Graph->Nv;V++
)
93 for(W=
0;W<Graph->Nv;W++
)
94 Graph->G[V][W]=
INFINITY;
95 return Graph;
96 }
97
98 void InsertEdge(MGraph Graph,Edge E){
99 Graph->G[E->V1][E->V2]=E->
Weight;
100 //若是无向图还要插入
101 Graph->G[E->V2][E->V1]=E->
Weight;
102 }
103
104 MGraph BuildGraph(){
105 MGraph Graph;
106 Edge E;
107 Vertex V;
108 int Nv,i;
109 printf(
"输入结点的个数\n");
110 scanf(
"%d",&Nv);
//the number of vertex
111 Graph=CreateGraph(Nv);
//initate graph with Nv vertexs !!return 回去要赋值给Graph；
112 //getchar();
113 printf(
"输入弧的个数\n");
114 scanf(
"%d",&(Graph->Ne));
//read the number of ege
115 if(Graph->Ne!=
0)
116 {
117 E=(Edge)
malloc(
sizeof(ENode));
118 for(i=
0;i<Graph->Ne;i++
){
119 // getchar();
120 printf(
"输入弧的信息V1 V2 Weight\n");
121 scanf(
"%d %d %d",&(E->V1),&(E->V2),&(E->
Weight));
122 InsertEdge(Graph,E);
123 }
124 }
125 // for(V=0;V<Graph->Nv;V++)
126 // scanf("%c",&(Graph->Data[V]));
127 return Graph;
128
129 }
130
131 void Visit(Vertex V){
132 printf(
"正在访问顶点%d\n",V);
133 }
134
135 Status IsEdge(MGraph Graph,Vertex V,Vertex W){
136 return Graph->G[V][W]<INFINITY?
TRUE:FALSE;
137 }
138
139 //void (*Visit)(Vertex)
140 void BFS(MGraph Graph,Vertex S){
141 Queue Q;
142 Vertex V,W;
143 int i;
144 int MaxSize=
100;
145 Q=
CreateQueue(MaxSize);
146 for(i=
0;i<Graph->Nv;i++
)
147 Visited[i]=
FALSE;
148 Visit(S);
149 Visited[S]=
TRUE;
150 AddQ(Q,S);
151 while(!
IsEmpty(Q))
152 {
153 V=
DeleteQ(Q);
154 for(W=
0;W<Graph->Nv;W++
)
155 if(!Visited[W]&&
IsEdge(Graph,V,W)){
156 Visit(W);
157 Visited[W]=
TRUE;
158 AddQ(Q,W);
159 }
160 }
161 }
162
163 void DFS(MGraph Graph,Vertex S){
164 Vertex W;
165 int i;
166 for(i=
0;i<Graph->Nv;i++
)
167 Visited[i]=
FALSE;
168 Visit(S);
169 Visited[S]=
TRUE;
170 for(W=
0;W<Graph->Nv;W++)
//一直崩溃也有可能是下面多用了一个没有被赋值的变量
171 if(!Visited[W]&&
IsEdge(Graph,S,W)){
172 Visit(W);
173 Visited[W]=
TRUE;
174 DFS1(Graph,W);
175
176 }
177
178 }
179
180 void DFS1(MGraph Graph,Vertex S){
181 Vertex W;
182 for(W=
0;W<Graph->Nv;W++
)
183 if(!Visited[W]&&
IsEdge(Graph,S,W)){
184 Visit(W);
185 Visited[W]=
TRUE;
186 DFS1(Graph,W);
187
188 }
189 }
190
191
192
193 Queue CreateQueue(
int MaxSize )
194 {
195 Queue Q = (Queue)
malloc(
sizeof(
struct QNode));
196 Q->Data = (ElementType *)
malloc(MaxSize *
sizeof(ElementType));
197 Q->Front = Q->Rear =
0;
198 Q->MaxSize =
MaxSize;
199 return Q;
200 }
201
202 Status AddQ( Queue Q, ElementType X )
203 {
204 if ( IsFull(Q) ) {
205 printf(
"队列满");
206 return FALSE;
207 }
208 else {
209 Q->Rear = (Q->Rear+
1)%Q->
MaxSize;
210 Q->Data[Q->Rear] =
X;
211 return FALSE;
212 }
213 }
214 ElementType DeleteQ( Queue Q )
215 {
216 if ( IsEmpty(Q) ) {
217 printf(
"队列空");
218 return ERROR;
219 }
220 else {
221 Q->Front =(Q->Front+
1)%Q->
MaxSize;
222 return Q->Data[Q->
Front];
223 }
224 }
225
226 Status IsEmpty( Queue Q )
227 {
228 return (Q->Front == Q->
Rear);
229 }
230 Status IsFull( Queue Q )
231 {
232 return ((Q->Rear+
1)%Q->MaxSize == Q->
Front);
233 }
转载于:https://www.cnblogs.com/lovecodepql/p/7747598.html
