个人中心
gpt4 book ai didi

C语言实现图的搜索算法示例

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言实现图的搜索算法示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了C语言实现图的搜索算法。分享给大家供大家参考，具体如下:

在游戏中，常常遇到路径规划问题，用到图的相关算法，我们以简单图来学习.

图通常有两种表示方式，矩阵和邻接表。矩阵表示简单，运算快，但当矩阵是稀疏矩阵的时候就存在空间浪费的问题，并且效率也会下降，而邻接表节约空间，并且由于边是连续访问，时间效率也比较高。在本文中，我们将以邻接表来表示图.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<queue>
#include<stack>
using namespace std;
struct SE{
   int vIndex;
   int tag;
   SE* next;
};
struct SMap{
   SE* pE;
   int nnode;
};
void visit(SE *se){
   printf ( "%d\n" , se->vIndex);
}
SMap* create_map( int matrix[][6], int n){
   SMap* pMap = new SMap();
   pMap->nnode = n;
   pMap->pE = new SE[n];
   memset (pMap->pE, 0, n* sizeof (SE));
   for ( int i = 0; i<n; i++){
     pMap->pE[i].vIndex = i;
     pMap->pE[i].tag = 0;
     SE* p = &pMap->pE[i];
     for ( int j = 0; j<n; j++){
       if (matrix[i][j] != 0){
         p->next = new SE();
         p->next->vIndex = j;
         p->next->tag = 0;
         p->next->next = NULL;
         p = p->next;
       }
     }
   }
   return pMap;
}
int BFS(SMap* pMap, int n){
   queue<SE*> q;
   for ( int i = 0; i < n; i++){
     if (pMap->pE[i].tag == 0){
       q.push(&pMap->pE[i]);
       while (!q.empty()){
         SE *se = q.front();
         q.pop();
         if (pMap->pE[se->vIndex].tag == 1){
           continue ;
         }
         visit(se);
         pMap->pE[se->vIndex].tag = 1;
         SE * p = se;
         while (p->next){
           p = p->next;
           if (pMap->pE[p->vIndex].tag == 0){
             q.push(p);
           }
         }
       }
     }
   }
   return 0;
}
int DFS(SMap* pMap, int n){
   stack<SE*> s;
   for ( int i = 0; i < n; i++){
     if (pMap->pE[i].tag == 0){
       s.push(&pMap->pE[i]);
       while (!s.empty()){
         SE *se = s.top();
         s.pop();
         if (pMap->pE[se->vIndex].tag == 1){
           continue ;
         }
         visit(se);
         pMap->pE[se->vIndex].tag = 1;
         SE * p = &pMap->pE[se->vIndex];
         stack<SE*> tmp;
         while (p->next){
           p = p->next;
           if (pMap->pE[p->vIndex].tag == 0){
             tmp.push(p);
           }
         }
         while (!tmp.empty()){
           s.push(tmp.top());
           tmp.pop();
         }
       }
     }
   }
   return 0;
}
int main(){
   int map[6][6] = {
     { 0, 1, 0, 1, 0, 0 },
     { 1, 0, 1, 1, 1, 0 },
     { 0, 1, 0, 1, 0, 0 },
     { 1, 1, 1, 0, 1, 0 },
     { 0, 1, 0, 1, 0, 1 },
     { 0, 0, 0, 0, 1, 0 }
   };
   SMap* smap = create_map(map, 6);
// BFS(smap, 6);
   DFS(smap, 6);
   return 0;
}

希望本文所述对大家C语言程序设计有所帮助.

最后此篇关于C语言实现图的搜索算法示例的文章就讲到这里了,如果你想了解更多关于C语言实现图的搜索算法示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： C语言实现二叉树的搜索及相关算法示例
文章推荐： Qt绘制图表的实现
文章推荐： QT串口通信的实现方法
文章推荐： C++解析Json的方法详解【jsoncpp】
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com