数据结构 图及其应用

一、要求
　　1.设计并验证如下算法：图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。
　　2.设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。
二、代码
1.

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<time.h>
4. #define INFINITY INT_MAX
5. #define MAX_VERTEX_NUM 20
6. typedef struct queue
7. {
8.     int Data[MAX_VERTEX_NUM];
9.     int front;
10.     int rear;
11. }SqQueue;
14. int visited[MAX_VERTEX_NUM];//1--已访问   0--未访问
16. typedef struct mgraph
17. {
18.     char vexs[MAX_VERTEX_NUM];//顶点向量
19.     int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
20.     int vexnum;//图的顶点数
21. }Mgraph;
23. void init_queue(SqQueue *);
24. void EnQueue(SqQueue *,int);
25. void DeQueue(SqQueue *);
26. int empty_queue(SqQueue *);
27. void DFS(Mgraph G,int v);
28. void DFSTraverse(Mgraph G);
29. void BFSTraverse(Mgraph G);
31. int main()
32. {
33.     Mgraph G;
34.     printf("请输入图的顶点数\n");
35.     scanf("%d",&G.vexnum);
36.     printf("输入图的各个顶点向量\n");
37.     scanf("%s",&G.vexs);
38.     srand((unsigned)time(NULL));
39.     for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵
40.     {
41.         for(int j=0;j<G.vexnum;j++)
42.             G.arcs[i][j]=rand()%2;
43.     }
44.     printf("该图的邻接矩阵如下：\n");
45.     for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵
46.     {
47.         for(int j=0;j<G.vexnum;j++)
48.             printf("%d ",G.arcs[i][j]);
49.         printf("\n");
50.     }
51.     printf("深度优先遍历结果如下：\n");
52.     DFSTraverse(G);
53.     printf("\n");
54.     printf("广度优先遍历结果如下：\n");
55.     BFSTraverse(G);
56.     return 0;
57. }
58. void DFSTraverse(Mgraph G)
59. {
60.     for(int v=0;v<G.vexnum;v++)//标记赋值为未访问
61.         visited[v]=0;
62.     for(int v=0;v<G.vexnum;v++)//调用DFS
63.         if(!visited[v])
64.            DFS(G,v);
65. }
66. void DFS(Mgraph G,int v)
67. {
68.     visited[v]=1;
69.     printf("%c ",G.vexs[v]);
70.     for(int n=0;n<G.vexnum;n++)
71.     {
72.         if((visited[n]==0)&&(G.arcs[v][n]==1))
73.             DFS(G,n);
74.     }
75. }
77. void BFSTraverse(Mgraph G)//广度优先遍历
78. {
79.     SqQueue Q;
80.     for(int i=0;i<G.vexnum;i++)
81.         visited[i]=0;
82.     init_queue(&Q);
83.     for(int i=0;i<G.vexnum;i++)
84.     {
85.         if(!visited[i])
86.         {
87.             visited[i]=1;
88.             printf("%c ",G.vexs[i]);
89.             EnQueue(&Q,i);
90.         }
91.         while(!empty_queue(&Q))
92.         {
93.             DeQueue(&Q);
94.             for(int j=0;j<G.vexnum;j++)
95.             {
96.                 if(!visited[j]&&G.arcs[i][j])
97.                 {
98.                     visited[j]=1;
99.                     printf("%c ",G.vexs[j]);
100.                     EnQueue(&Q,j);
101.                 }
102.             }
103.          }
104.     }
105. }
107. void init_queue(SqQueue *Q)
108. {
109.     Q->front=Q->rear=0;
110. }
112. void EnQueue(SqQueue *Q,int e)
113. {
114.         Q->Data[Q->rear]=e;
115.         Q->rear++;
116. }
118. void DeQueue(SqQueue *Q)
119. {
120.     Q->front++;
121. }
123. int empty_queue(SqQueue *Q)
124. {
125.     if(Q->front==Q->rear)
126.         return 1;
127.     else
128.         return 0;
129. }

复制代码

 
运行结果：
 
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！