图的遍历

写于 | 归档 | | 翻阅:
| 共计: 404 字 | 时长 ≈ 2 min

这是一个以邻接表为基础的遍历……
包括DFS的递归非递归实现以及BFS队列实现

递归DFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
​
int main(){
	TGraph* G = (TGraph*)malloc(sizeof(TGraph));
	graph_init(G);//稍微初始化一下我们的图
	int visited[N];for(int i=0;i<N;i++) visited[i]=0;
	for(int i=0;i<N;i++){
		if(visited[i]==0){
			DFS(G,visited,i);
			printf("\n");
		}
	}
} 
void DFS(TGraph* G,int visited[N],int i){
	printf("%d ",G->adjlist[i].vex);visited[i]=1;
	ENode* p = G->adjlist[i].next;
	while(p!=NULL){
		if(visited[p->vex]==0){
			DFS(G,visited,p->vex);
		}
		p = p -> next;
	}
}

非递归DFS：

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
​
void dfs(TGraph* G,int visited[N]){
	Tqueue* stack = stack_init(G->nv);
	for(int i=0;i<G->nv;i++){
		if(visited[i]==1) break;
		else{
			stack->qu[stack->rear++] = i;
			visited[i]=1;
			while(stack->front!=stack->rear){
				ENode* temp = G->adjlist[stack->qu[stack->rear-1]].next;
				printf("%d ",stack->qu[--stack->rear]);
				while(1){
					if(temp==NULL) break;
					if(visited[temp->vex]==0){
						stack->qu[stack->rear++] = temp->vex;
						visited[temp->vex]=1;break;
					}
					temp = temp->next;
				}
				
			}
		}
	}
	free(stack);
}

BFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
​
void bfs(TGraph* G,int visited[N]){
	Tqueue* queue = queue_init(G->nv);
	for(int i=0;i<G->nv;i++){
		if(visited[i]==1) break;
		queue->qu[queue->rear++%G->nv] = i;visited[i]=1;//简单地借用一下循环队列的思想
		while(queue->front%G->nv!=queue->rear%G->nv){
			ENode* temp = G->adjlist[queue->qu[(queue->front)%G->nv]].next;
			printf("%d ",queue->qu[(queue->front++)%G->nv]);
			while(1){
				if(temp==NULL) break;
					if(visited[temp->vex]==0){
						queue->qu[queue->rear++%G->nv] = temp->vex;
						visited[temp->vex]=1;break;
					}
					temp = temp->next;
			}
		}
	}
	free(queue);
}