文档章节

数据结构【图】—022邻接矩阵的深度和广度遍历

o
 osc_y8yehimr
发布于 2019/03/20 21:20
字数 747
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  1 #include "000库函数.h"
  2 //无向图
  3 
  4 typedef char VertexType; /* 顶点类型应由用户定义 */
  5 typedef int EdgeType; /* 边上的权值类型应由用户定义 */
  6 
  7 #define MAXSIZE 9 /* 存储空间初始分配量 */
  8 #define MAXEDGE 15
  9 #define MAXVEX 9
 10 #define INFINITY 65535
 11 
 12 struct MGraph {//临接矩阵参数
 13     VertexType vexs[MAXVEX];
 14     EdgeType arc[MAXVEX][MAXVEX];
 15     int numVertexes, numEdges;
 16 };
 17 
 18 struct Queue {//遍历表
 19     char data;//标号
 20     Queue *front;//
 21     Queue *rear;//
 22 };
 23 //queue链表的初始化
 24 void InitQueue(Queue **q) {
 25     (*q) = new Queue;
 26     (*q)->data = 0;
 27     (*q)->front = NULL;
 28     (*q)->rear = NULL;
 29 }
 30 
 31 void CreateMGraph(MGraph **G) {
 32     (*G) = new MGraph;
 33     (*G)->numEdges = 15;
 34     (*G)->numVertexes = 9;
 35     /* 读入顶点信息,建立顶点表 */
 36     (*G)->vexs[0] = 'A';
 37     (*G)->vexs[1] = 'B';
 38     (*G)->vexs[2] = 'C';
 39     (*G)->vexs[3] = 'D';
 40     (*G)->vexs[4] = 'E';
 41     (*G)->vexs[5] = 'F';
 42     (*G)->vexs[6] = 'G';
 43     (*G)->vexs[7] = 'H';
 44     (*G)->vexs[8] = 'I';
 45 
 46 
 47     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */
 48     {
 49         for (int j = 0; j < (*G)->numVertexes; ++j)
 50         {
 51             (*G)->arc[i][j] = 0;
 52         }
 53     }
 54 
 55     (*G)->arc[0][1] = 1;
 56     (*G)->arc[0][5] = 1;
 57  
 58     (*G)->arc[1][2] = 1;
 59     (*G)->arc[1][8] = 1;
 60     (*G)->arc[1][6] = 1;
 61  
 62     (*G)->arc[2][3] = 1;
 63     (*G)->arc[2][8] = 1;
 64  
 65     (*G)->arc[3][4] = 1;
 66     (*G)->arc[3][7] = 1;
 67     (*G)->arc[3][6] = 1;
 68     (*G)->arc[3][8] = 1;
 69  
 70     (*G)->arc[4][5] = 1;
 71     (*G)->arc[4][7] = 1;
 72  
 73     (*G)->arc[5][6] = 1;
 74  
 75     (*G)->arc[6][7] = 1;
 76 
 77 
 78     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */
 79     {
 80         for (int j = 0; j < (*G)->numVertexes; ++j)
 81         {
 82             (*G)->arc[j][i] = (*G)->arc[i][j];
 83         }
 84     }
 85 
 86 }
 87 
 88 Queue *q;//用来存储路径
 89 vector<bool>a(MAXVEX, true);//访问标志
 90 void DFS(MGraph *G, int pot) {
 91     a[pot] = false;//已经访问过
 92     Queue *p;
 93     InitQueue(&p);
 94     p->data = G->vexs[pot];
 95     q->rear = p;
 96     p->front = q;
 97     q = p;
 98     for (int i = 0; i < G->numVertexes; ++i) {
 99         if (G->arc[pot][i] && a[i]) {//有路
100             DFS(G, i);//递归遍历,编历到B,就到B中找可行路径,A中其他的可行路径以后再遍历
101         }
102     }
103 }
104 
105 void DFSTraverse(MGraph *G) {//深度遍历
106     InitQueue(&q);
107     Queue *head = q;
108     for (int i = 0; i < G->numVertexes; ++i) {
109         if (a[i])//未访问过
110             DFS(G, i);//进入回溯
111     }
112     Queue *p = head->rear;
113     while (p) {
114         cout << p->data << "  ";
115         p = p->rear;
116     }
117     cout << endl;
118     
119     
120 }
121 
122 
123 vector<char> bf;
124 vector<bool>b(MAXVEX, true);//访问标志
125 deque<int>s;
126 void BFS(MGraph *G, int pot) {
127     s.pop_front();//出栈
128     bf.push_back(G->vexs[pot]);
129     if (bf.size() >= G->numVertexes)return;
130     for (int j = 0; j < G->numVertexes; ++j) {
131         if (G->arc[pot][j] && b[j]) {
132             b[j] = false;//遍历过
133             s.push_back(j);
134         }            
135     }
136     BFS(G, s.front());    
137 }
138 
139 void BFSTraverse(MGraph *G) {
140     for (int i = 0; i < G->numVertexes; ++i) {
141         if (b[i]) {
142             s.push_back(i);
143             b[i] = false;//遍历过
144             BFS(G, s.front());
145         }
146     }
147     for (auto f : bf)
148         cout << f << "  ";
149     cout << endl;
150 }
151 int T022(void)
152 {
153     MGraph *G;
154     CreateMGraph(&G);
155     //printf("\n深度遍历:");
156     //DFSTraverse(G);
157     printf("\n广度遍历:");
158     BFSTraverse(G);
159     return 0;
160 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

pyhon

cython 相关的帖子. http://blog.behnel.de/categories/cython.html https://www.nexedi.com/ 我们追求的价值观 家 多核Python HTTP服务器(比Go更快)(破坏者:Cython) 价值观 当让-保罗·...

MtrS
15分钟前
9
0
多处理与线程Python - Multiprocessing vs Threading Python

问题: I am trying to understand the advantages of multiprocessing over threading . 我试图了解多处理优于线程的优势。 I know that multiprocessing gets around the Global Interpret......

法国红酒甜
20分钟前
9
0
格式编号始终显示2个小数位 - Format number to always show 2 decimal places

问题: I would like to format my numbers to always display 2 decimal places, rounding where applicable. 我想将数字格式化为始终显示2个小数位,并在适用的情况下四舍五入。 Examples...

富含淀粉
今天
22
0
Docker可视化工具Portainer

1 前言 从没想到Docker也有可视化的工具,因为它的命令还是非常清晰简单的。无聊搜了一下,原来已经有很多Docker可视化工具了。如DockerUI、Shipyard、Rancher、Portainer等。查看对比了一番...

南瓜慢说
今天
20
0
日志系统新贵 Loki,真香!!

最近,在对公司容器云的日志方案进行设计的时候,发现主流的ELK或者EFK比较重,再加上现阶段对于ES复杂的搜索功能很多都用不上最终选择了Grafana开源的Loki日志系统,下面介绍下Loki的背景。...

庞陆阳
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部