深度优先搜索DFS——图邻接矩阵表示
同样的DFS，这个是用邻接矩阵保存的图，或许应用没有那么广，要浪费较多的空间，但是还是有必要实现一下的，和之前那个算法的思想是一样的，只是变换了存储结构。
/*图邻接矩阵表示DFSinput:17A 0 0 0 0 1 0 0B 0 0 1 1 0 0 0C 0 1 0 1 0 0 0D 0 1 0 0 1 1 0E 1 0 0 1 0 0 1F 0 0 0 1 0 0 0G 0 0 0 0 1 0 0output:A E D B C F G*/#include<iostream>#include<cstring>using namespace std;struct Graph{ //图邻接矩阵表示 char data; bool *adjacency;};void Create(Graph G[],int n){ //创建图邻接矩阵表示 int i,j; for(i=1; i<=n; i++){ cin>>G[i].data; G[i].adjacency = new bool[n]; for(j=1; j<=n; j++)cin>>G[i].adjacency[j]; }}void DFS(Graph G[],int vex,int n,bool visited[]){ //DFS图邻接矩阵表示 if(!visited[vex]){ visited[vex] = true; cout<<G[vex].data<<' '; int i; for(i=1; i<=n; i++){ if(G[vex].adjacency[i] && !visited[i])DFS(G,i,n,visited); } }}int main(){ Graph *G; bool *visited; int t,n; cin>>t; while(t--){ cin>>n; G = new Graph[n]; visited = new bool[n]; memset(visited,0,sizeof(visited)); Create(G,n); DFS(G,1,n,visited); cout<<endl; } return 0;}