PTA——7-2 图深度优先遍历

痛定思痛。 2023-01-19 13:54 4阅读 0赞

编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

# 输入格式: #

输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。

# 输出格式: #

输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。

# 输入样例1: #

> 3 3  
> 0 1  
> 1 2  
> 0 2

# 输出样例1: #

> 0 1 2

# 输入样例2: #

> 4 4  
> 0 2  
> 0 1  
> 1 2  
> 3 0

# 输出样例2: #

> 0 1 2 3

# 思路： #

使用从《啊哈算法》中学到的建立一个20000\*20000的数组来当**邻接矩阵**，是非常浪费空间和时间的，在测试的时候是过不去的，那么《数据结构》上还有一种和邻接矩阵功能类似的结构叫**邻接表**，而我们用C++的Vector即可实现

# 实现代码： #

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    //建立表头结点表 
    vector<int> adjacency[20000];
    int book[20000];
    
    void dfs(int cur){ 
        
    	cout<<cur<<" ";
        book[cur]=1;
    
    	//遍历链表中的结点 
    	int length=adjacency[cur].size();
    	for(int i=0;i<length;i++){ 
    		if(book[adjacency[cur][i]]==0){ 
    			dfs(adjacency[cur][i]);
    		}
    	}
    }
    
    int main(){ 
        int vertex,edge,vertex1,vertex2;
    	cin>>vertex>>edge;
    	
    	//输入边 
    	for(int i=0;i<edge;i++){ 
    		cin>>vertex1>>vertex2;
    		adjacency[vertex1].push_back(vertex2);
    	}
    	
    	//给邻接表的每个链表的结点排序 
    	for(int i=0;i<vertex;i++){ 
    		sort(adjacency[i].begin(),adjacency[i].end());
    	}
        
        //遍历每个结点 
    	for(int i=0;i<vertex;i++){ 
    		if(book[i]==0){ 
        	dfs(i);	
    		}
    	}
    
    	return 0;
    }