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 typedef
int ElementType;
13 typedef
int Status;
14 typedef
int WeightType;
15 typedef
int Vertex;
16 typedef
char DataType;
17
18 typedef
int Position;
19 typedef
struct QNode{
20 ElementType *
Data;
21 Position Front, Rear;
22 int MaxSize;
23 }QNode,*
Queue;
24
25 typedef
struct ENode{
26 Vertex V1,V2;
//有向边<v1,V2>
27 WeightType Weight;
//权重
28 }ENode,*
PtrToENode ;
29
30 typedef PtrToENode Edge;
31
32 Status IsFull( Queue Q );
33
34 typedef
struct GNode{
35 int Nv;
//顶点数
36 int Ne;
//边数
37 WeightType G[MaxVerTexNum][MaxVerTexNum];
//邻接矩阵
38 DataType Data[MaxVerTexNum];
//save data of the Vertex;
39 }GNode,*
PtrToGNode;
40
41 typedef PtrToGNode MGraph;
42
43 ElementType DeleteQ( Queue Q );
44
45 Queue CreateQueue(
int MaxSize );
46
47 Status IsEmpty( Queue Q );
48
49 Status AddQ( Queue Q, ElementType X );
50
51 MGraph CreateGraph(
int VertexNum);
//Create a Graph with VertexNum Vertex but without an ege;
52
53 void InsertEdge(MGraph Graph,Edge E);
54
55 MGraph BuildGraph();
56
57 Status IsEdge(MGraph Graph,Vertex V,Vertex W);
//检查<V,W>是不是图中的一条边，即W是不是V的邻接点
58
59 void BFS(MGraph Graph,Vertex S);
60
61 void Unweighted(MGraph Graph,
int dist[],
int path[],Vertex);
62
63 int main(
int argc,
char**
argv)
64 {
65 MGraph Graph;
66 Graph=
BuildGraph();
67
68 int i,j;
69 int dist[
100];
70 int path[
100];
71
72 Vertex S=
1;
73 int sum;
74 for(i=
0;i<=
99;i++
)
75 {
76 dist[i]=path[i]=-
1;
77 }
78
79 printf(
"无向图最短路径\n");
80 Unweighted(Graph,dist,path,S);
81
82 for(j=
0;j<Graph->Nv;j++){
//出现死循环要多调试
83 i=
j;
84 sum=
0;
85 while(i!=-
1){
86
87 printf(
"%d",i);
88 i=
path[i];
89 if(i!=-
1){
90 printf(
"<--");
91 sum++
;
92 }
93
94 }
95 printf(
"\n");
96 printf(
"从%d到%d的无权图最短路径为%d\n",S,j,sum);
97 printf(
"\n");
98 }
99
100 //DFS(Graph, 1);
101 return 0;
102 }
103
104 MGraph CreateGraph(
int VertexNum){
105 Vertex V,W;
106 MGraph Graph;
107 Graph=(MGraph)
malloc(
sizeof(GNode));
//form a Graph
108 Graph->Nv=
VertexNum;
109 Graph->Ne=
0;
//
110 for(V=
0;V<Graph->Nv;V++
)
111 for(W=
0;W<Graph->Nv;W++
)
112 Graph->G[V][W]=
INFINITY;
113 return Graph;
114 }
115
116 void InsertEdge(MGraph Graph,Edge E){
117 Graph->G[E->V1][E->V2]=E->
Weight;
118 //若是无向图还要插入
119 Graph->G[E->V2][E->V1]=E->
Weight;
120 }
121
122 MGraph BuildGraph(){
123 MGraph Graph;
124 Edge E;
125 Vertex V;
126 int Nv,i;
127 printf(
"输入结点的个数\n");
128 scanf(
"%d",&Nv);
//the number of vertex
129 Graph=CreateGraph(Nv);
//initate graph with Nv vertexs !!return 回去要赋值给Graph；
130 //getchar();
131 printf(
"输入弧的个数\n");
132 scanf(
"%d",&(Graph->Ne));
//read the number of ege
133 if(Graph->Ne!=
0)
134 {
135 E=(Edge)
malloc(
sizeof(ENode));
136 for(i=
0;i<Graph->Ne;i++
){
137 // getchar();
138 printf(
"输入弧的信息V1 V2 Weight\n");
139 scanf(
"%d %d %d",&(E->V1),&(E->V2),&(E->
Weight));
140 InsertEdge(Graph,E);
141 }
142 }
143 // for(V=0;V<Graph->Nv;V++)
144 // scanf("%c",&(Graph->Data[V]));
145 return Graph;
146
147 }
148
149 void Visit(Vertex V){
150 printf(
"正在访问顶点%d\n",V);
151 }
152
153 Status IsEdge(MGraph Graph,Vertex V,Vertex W){
154 return Graph->G[V][W]<INFINITY?
TRUE:FALSE;
155 }
156
157 Queue CreateQueue(
int MaxSize )
158 {
159 Queue Q = (Queue)
malloc(
sizeof(
struct QNode));
160 Q->Data = (ElementType *)
malloc(MaxSize *
sizeof(ElementType));
161 Q->Front = Q->Rear =
0;
162 Q->MaxSize =
MaxSize;
163 return Q;
164 }
165
166 Status AddQ( Queue Q, ElementType X )
167 {
168 if ( IsFull(Q) ) {
169 printf(
"队列满");
170 return FALSE;
171 }
172 else {
173 Q->Rear = (Q->Rear+
1)%Q->
MaxSize;
174 Q->Data[Q->Rear] =
X;
175 return FALSE;
176 }
177 }
178 ElementType DeleteQ( Queue Q )
179 {
180 if ( IsEmpty(Q) ) {
181 printf(
"队列空");
182 return ERROR;
183 }
184 else {
185 Q->Front =(Q->Front+
1)%Q->
MaxSize;
186 return Q->Data[Q->
Front];
187 }
188 }
189
190 Status IsEmpty( Queue Q )
191 {
192 return (Q->Front == Q->
Rear);
193 }
194 Status IsFull( Queue Q )
195 {
196 return ((Q->Rear+
1)%Q->MaxSize == Q->
Front);
197 }
198
199 void Unweighted(MGraph Graph,
int dist[],
int path[],Vertex S){
200 Queue Q;
201 Vertex V,W;
202 int MaxSize=
100;
203 Q=
CreateQueue(MaxSize);
204 dist[S]=
0;
205 AddQ(Q,S);
206 while(!
IsEmpty(Q))
207 {
208 V=
DeleteQ(Q);
209 for(W=
0;W<Graph->Nv;W++
)
210 if(Graph->G[V][W]!=
0&&Graph->G[V][W]!=
INFINITY){
211 if(dist[W]==-
1){
212 dist[W]=dist[V]+
1;
213 path[W]=
V;
214 AddQ(Q,W);
215 }
216 }
217 }
218 }
输入输出示例：
转载于:https://www.cnblogs.com/lovecodepql/p/7780498.html
相关资源：数据结构—成绩单生成器
