邻接图的深度广度优先遍历

简介:

邻接图的优点就是,现用现申请,空间存储很灵活,并且需要的空间也很小。我们在做复杂网络时,通常也是用这种方法。缺点是不适合并行化,因为cuda只支持连续地址空间的拷贝。

数据结构

主要包括,边节点和顶点节点

复制代码
typedef struct edgeNode{
    int num;
    int weight;
    struct edgeNode * next;
}edgeNode;

typedef struct vertexNode{
    char data;
    edgeNode * firstNode;
}vertexNode,List[NUM];

typedef struct Graph{
    List list;
    int numver,numedges;
}Graph;
复制代码

深度优先遍历

与矩阵图类似

复制代码
void DFS(Graph *g,int i){
    edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
    visited[i] = 1;
    printf("%c ",g->list[i].data);
    p = g->list[i].firstNode;
    while(p){
        if(!visited[p->num])
            DFS(g,p->num);
        p = p->next;
    }
}
void DFSTraverse(Graph *g){
    int i;
    for(i=0;i<g->numver;i++)
        visited[i] = 0;
    for(i=0;i<g->numver;i++)
        if(!visited[i])
            DFS(g,i);
}
复制代码

广度优先遍历

复制代码
void BFSTraverse(Graph *g){
    int i;
    edgeNode *p;
    Queue *q = (Queue *)malloc(sizeof(Queue));

    for(i=0;i<g->numver;i++)
        visited[i] = 0;
    initQueue(q,0);
    for(i=0;i<g->numver;i++){
        if(!visited[i]){
            visited[i] = 1;
            printf("%c ",g->list[i].data);
            inQueue(q,i);
            while(getLength(q)){
                int *tar = (int *)malloc(sizeof(int));
                outQueue(q,tar);
                p = g->list[*tar].firstNode;
                while(p){
                    if(!visited[p->num]){
                        visited[p->num] = 1;
                        printf("%c ",g->list[p->num].data);
                        inQueue(q,p->num);
                    }
                    p = p->next;
                }

            }
        }
    }

}
复制代码

示例图

示例代码

复制代码
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define NUM 5
  4 #define MAXSIZE NUM
  5 
  6 typedef struct edgeNode{
  7     int num;
  8     int weight;
  9     struct edgeNode * next;
 10 }edgeNode;
 11 
 12 typedef struct vertexNode{
 13     char data;
 14     edgeNode * firstNode;
 15 }vertexNode,List[NUM];
 16 
 17 typedef struct Graph{
 18     List list;
 19     int numver,numedges;
 20 }Graph;
 21 
 22 typedef struct Queue{
 23     int data[NUM];
 24     int front;
 25     int rear;
 26 }Queue;
 27 
 28 void initQueue(Queue *q,int n);
 29 void showQueue(Queue *q);
 30 int getLength(Queue *q);
 31 int inQueue(Queue *q,int num);
 32 int outQueue(Queue *q,int *tar);
 33 
 34 void createGraph(Graph *g);
 35 void showGraph(Graph *g);
 36 void add(Graph *g,int a,int b,int c);
 37 void DFS(Graph *g,int i);
 38 void DFSTraverse(Graph *g);
 39 void BFSTraverse(Graph *g);
 40 
 41 int visited[NUM];
 42 
 43 int main()
 44 {
 45     Graph * g = (Graph *)malloc(sizeof(Graph));
 46     createGraph(g);
 47     showGraph(g);
 48     printf("\n");
 49     DFSTraverse(g);
 50     printf("\n");
 51     BFSTraverse(g);
 52     return 0;
 53 }
 54 void add(Graph *g,int a,int b,int c){
 55     edgeNode *e;
 56 
 57     e = (edgeNode *)malloc(sizeof(edgeNode));
 58     e->next = g->list[a].firstNode;
 59     g->list[a].firstNode = e;
 60     e->num = b;
 61     e->weight = c;
 62 
 63     e = (edgeNode *)malloc(sizeof(edgeNode));
 64     e->next = g->list[b].firstNode;
 65     g->list[b].firstNode = e;
 66     e->num = a;
 67     e->weight = c;
 68 
 69     g->numedges++;
 70 
 71 
 72 }
 73 
 74 void createGraph(Graph *g){
 75     int i;
 76     for(i=0;i<NUM;i++){
 77         g->list[i].data = 65+i;
 78         g->list[i].firstNode = NULL;
 79     }
 80     g->numver = NUM;
 81     g->numedges = 0;
 82     //添加顶点0的边
 83     add(g,0,1,0);
 84     add(g,0,2,0);
 85     add(g,0,3,0);
 86     add(g,0,4,0);
 87 
 88     add(g,1,3,0);
 89     add(g,1,4,0);
 90 
 91     add(g,2,4,0);
 92 
 93     add(g,3,4,0);
 94 }
 95 void showGraph(Graph *g){
 96     int i;
 97     for(i=0;i<g->numver;i++){
 98         printf("g[%d] ",i);
 99         edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
100         p = g->list[i].firstNode;
101         while(p){
102             printf("->%d(%d)",p->num,p->weight);
103             p = p->next;
104         }
105         printf("->null\n");
106     }
107 }
108 
109 void DFS(Graph *g,int i){
110     edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode));
111     visited[i] = 1;
112     printf("%c ",g->list[i].data);
113     p = g->list[i].firstNode;
114     while(p){
115         if(!visited[p->num])
116             DFS(g,p->num);
117         p = p->next;
118     }
119 }
120 void DFSTraverse(Graph *g){
121     int i;
122     for(i=0;i<g->numver;i++)
123         visited[i] = 0;
124     for(i=0;i<g->numver;i++)
125         if(!visited[i])
126             DFS(g,i);
127 }
128 void BFSTraverse(Graph *g){
129     int i;
130     edgeNode *p;
131     Queue *q = (Queue *)malloc(sizeof(Queue));
132 
133     for(i=0;i<g->numver;i++)
134         visited[i] = 0;
135     initQueue(q,0);
136     for(i=0;i<g->numver;i++){
137         if(!visited[i]){
138             visited[i] = 1;
139             printf("%c ",g->list[i].data);
140             inQueue(q,i);
141             while(getLength(q)){
142                 int *tar = (int *)malloc(sizeof(int));
143                 outQueue(q,tar);
144                 p = g->list[*tar].firstNode;
145                 while(p){
146                     if(!visited[p->num]){
147                         visited[p->num] = 1;
148                         printf("%c ",g->list[p->num].data);
149                         inQueue(q,p->num);
150                     }
151                     p = p->next;
152                 }
153 
154             }
155         }
156     }
157 
158 }
159 
160 void initQueue(Queue *q,int n){
161     int i;
162     q->front=0;
163     q->rear =0;
164     for(i=0;i<n;i++){
165         q->data[q->rear]=2*i+1;
166         q->rear++;
167     }
168 }
169 void showQueue(Queue *q){
170     int i;
171     int len=getLength(q);
172     printf("front-");
173     for(i=0;i<len;i++){
174         if(q->front+i<MAXSIZE)
175             printf("%d-",q->data[q->front+i]);
176         else
177             printf("%d-",q->data[q->front+i-MAXSIZE]);
178     }
179     printf("rear\n");
180 }
181 int getLength(Queue *q){
182     return (q->rear-q->front+MAXSIZE)%MAXSIZE;
183 }
184 int inQueue(Queue *q,int num){
185     if((q->rear+1)%MAXSIZE == q->front)
186         return 0;
187     q->data[q->rear] = num;
188     q->rear = (q->rear+1)%MAXSIZE;
189     return 1;
190 }
191 int outQueue(Queue *q,int *tar){
192     if(q->front == q->rear)
193         return 0;
194     *tar = q->data[q->front];
195     q->front = (q->front+1)%MAXSIZE;
196     return 1;
197 }
复制代码

运行结果

本文转自博客园xingoo的博客,原文链接:邻接图的深度广度优先遍历,如需转载请自行联系原博主。
相关文章
数据结构实验之图论二:图的深度遍历
数据结构实验之图论二:图的深度遍历
|
5月前
|
算法
图的应用(最小生成树,最短路径,有向无环图)
图的应用(最小生成树,最短路径,有向无环图
30 0
|
算法
广度优先遍历(BFS):逐层探索图的算法奥秘
在图论中,广度优先遍历(Breadth-First Search,BFS)是一种图遍历算法,它以一种逐层的方式探索图的节点。通过从起始节点开始,逐层向外扩展,BFS能够帮助我们解决许多与图相关的问题。
115 0
|
5月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
存储 算法
图的广度优先遍历和深度优先遍历
本文主要是学习图的广度优先遍历和图的深度优先遍历
144 1
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
72 0
|
存储
图操作之邻接矩阵与邻接表的深度优先遍历
图操作之邻接矩阵与邻接表的深度优先遍历
153 0
|
存储
【32. 图中的层次(图的广度优先遍历)】
思路 - 因为所有的`边长都为1`,所以可以使用`宽度优先搜索`的思想,每当队列pop出一个元素时,将其距离为1的节点都加到队列中(层次遍历思想) - `st[]`标记各个节点有没有走过,`d[]`保存1号节点到各个节点的距离,初始时都为-1。
140 0
【32. 图中的层次(图的广度优先遍历)】
|
存储 算法 C++
C++实现图 - 04 最短路径
今天我们来看看图论中另一个非常重要的问题 —— 最短路径,正如其名就是要再图中找到起点到终点的最短路径,这就需要不断地去比较每条边的权值。这一讲我们将会具体介绍迪杰斯特拉算法和弗洛伊德算法的实现。
344 0
C++实现图 - 04 最短路径
|
算法
树与图的广度优先遍历
复习acwing算法基础课的内容,本篇为讲解基础算法:树与图的广度优先遍历,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
89 0
树与图的广度优先遍历