1 #include <stdio.h>
2 #include <stdlib.h>
3 #define maxv 10
4 #define max 10
5 typedef char elem;
6 typedef int elemtype;
7 #include "queue.h"
8 #include "mgraph.h"
9 void main()
10 {
11 mgraph g;
12 printf("1.初始化函数测试:\n");
13 initial(g);
14 printf("2.创建函数测试:\n");
15 create(g);
16 printf("3.输出函数测试:\n");
17 printg(g);
18 printf("4.输出顶点度函数测试:\n");
19 degree(g);
20 printf("5.深度优先遍历函数测试:\n");
21 dfstraverse(g);
22 printf("6.广度优先遍历函数测试:\n");
23 bfs(g);
24 }
1 //有向图的邻接矩阵,顶点数据为字符型
2 typedef struct MGraph
3 {
4 elem vexes[maxv];//顶点表
5 int edges[maxv][maxv];//邻接矩阵
6 int n,e;//顶点数n和边数e
7 }mgraph;
8 bool visited[maxv];//访问标志数组
9 void initial(mgraph &g)//初始化函数
10 {
11 int i,j;
12 g.e=0;
13 g.n=0;
14 for(j=0;j<maxv;j++)
15 g.vexes[j]=0;//建立顶点表
16 for(i=0;i<maxv;i++)
17 {
18 for(j=0;j<maxv;j++)
19 {
20 g.edges[i][j]=0;//初始化邻接矩阵
21 }
22 }
23 }
24 int locate(mgraph g,elem u)//查找顶点对应的数组下标值
25 {
26 for(int i=0;i<g.n;i++)
27 {
28 if(g.vexes[i]==u)
29 return i;
30 }
31 return -1;
32 }
33 void create(mgraph &g)//创建图的邻接矩阵存储
34 {
35 int i,j,k;
36 elem u,v;
37 printf("请输入有向图的顶点数:");
38 scanf("%d",&g.n);
39 printf("请输入有向图的弧数:");
40 scanf("%d",&g.e);
41 fflush(stdin);//清空缓存中的数据
42 printf("请输入字符型顶点数据,如ABCD:");
43 for(j=0;j<g.n;j++)
44 scanf("%c",&g.vexes[j]);//建立顶点表
45 fflush(stdin);
46 printf("请输入弧的信息,格式:弧尾,弧头\n");
47 for(k=0;k<g.e;k++)
48 {
49 scanf("%c,%c",&u,&v);
50 i=locate(g,u);
51 j=locate(g,v);
52 g.edges[i][j]=1;
53 fflush(stdin);
54 }
55 }
56 void printg(mgraph g)//输出有向图的邻接矩阵
57 {
58 int i,j;
59 printf("输入图的邻接矩阵存储信息:\n");
60 printf("顶点数据:\n");
61 for(i=0;i<g.n;i++)
62 printf("%d:%c\n",i,g.vexes[i]);
63 printf("邻接矩阵数据:\n");
64 for(i=0;i<g.n;i++)
65 {
66 for(j=0;j<g.n;j++)
67 {
68 printf("%3d",g.edges[i][j]);
69 }
70 printf("\n");
71 }
72 }
73 void degree(mgraph g)//输出顶点的度
74 {
75 int i,j,in,out;
76 for(i=0;i<g.n;i++)
77 {
78 in=0;
79 out=0;
80 for(j=0;j<g.n;j++)
81 {
82 if(g.edges[i][j]!=0)
83 out++;
84 if(g.edges[j][i]!=0)
85 in++;
86 }
87 printf("顶点%c的出度为%d---入度为%d---度为%d\n",g.vexes[i],out,in,in+out);
88 }
89 }
90 int firstadjvex(mgraph g,int v)//顶点v的第一个邻接顶点
91 {
92 for(int i=0;i<g.n;i++)
93 {
94 if(g.edges[v][i]==1)
95 return i;
96 }
97 return -1;
98 }
99 int nextadjvex(mgraph g,int v,int w)//顶点v的相对于w的下一个邻接顶点
100 {
101 for(int i=w+1;i<g.n;i++)
102 {
103 if(g.edges[v][i]==1)
104 return i;
105 }
106 return -1;
107 }
108 void dfs(mgraph g,int v)//遍历一个连通分量
109 {
110 int w;
111 visited[v]=true;
112 printf("%c ",g.vexes[v]);
113 for(w=firstadjvex(g,v);w>=0;w=nextadjvex(g,v,w))
114 {
115 if(!visited[w])
116 dfs(g,w);
117 }
118 }
119 void dfstraverse(mgraph g)//深度优先遍历
120 {
121 int v;
122 for(v=0;v<g.n;v++)
123 visited[v]=false;//标志访问数组初始化
124 for(v=0;v<g.n;v++)
125 {
126 if(!visited[v])
127 dfs(g,v);
128 }
129 }
130 void bfs(mgraph g)//广度优先遍历
131 {
132 int u=0,v=0,w=0;
133 queue q;
134 for(v=0;v<g.n;v++)
135 visited[v]=false;
136 initqueue(q);
137 for(v=0;v<g.n;v++)
138 {
139 if(!visited[v])
140 {
141 visited[v]=true;
142 printf("%c ",g.vexes[v]);
143 enqueue(q,v);
144 while(!queueempty(q))
145 {
146 dequeue(q,u);
147 for(w=firstadjvex(g,u);w>=0;w=nextadjvex(g,u,w))
148 {
149 if(!visited[w])
150 {
151 visited[w]=true;
152 printf("%c ",g.vexes[w]);
153 enqueue(q,w);
154 }
155 }
156 }
157 }
158 }
159 destroyqueue(q);
160 }
1 typedef struct
2 {
3 elemtype *base;//动态分配存储空间
4 int front;//头指针,若队列不空指向队列头元素
5 int rear;//尾指针,若队列不空指向队列尾元素的下一个位置
6 }queue;
7 void initqueue(queue &q)//初始化队列
8 {
9 q.base=new elemtype[max];//分配存储空间
10 if(!q.base)
11 {
12 printf("队列分配失败\n");
13 exit(-2);
14 }
15 else
16 q.front=q.rear=0;
17 }
18 int queueempty(queue q)//判断队列是否为空
19 {
20 if(q.front==q.rear)
21 return 1;
22 else
23 return 0;
24 }
25 void enqueue(queue &q,elemtype e)//入队列操作
26 {
27 if((q.rear+1)%max==q.front)
28 {
29 printf("队满,无法插入新元素!\n");
30 exit(-2);
31 }
32 else
33 {
34 q.base[q.rear]=e;
35 q.rear=(q.rear+1)%max;
36 }
37 }
38 void dequeue(queue &q,elemtype e)//出队列操作
39 {
40 if(q.front==q.rear)//判断队列是否为空
41 {
42 printf("空队列,无法删除头元素!\n");
43 exit(-2);
44 }
45 else
46 {
47 e=q.base[q.front];
48 q.front=(q.front+1)%max;
49 }
50 }
51 void destroyqueue(queue &q)//销毁队列
52 {
53 free(q.base);
54 q.base=NULL;
55 q.front=0;
56 q.rear=0;
57 printf("\n");
58 }
