代码主要是用基本图结构矩阵和邻接表示的图进行深度优先遍历，没什么说的，循环+递归 很简单
#include<iostream> #define MAX_VERTEX 100 using namespace std; //array struct Side_Array{ int link; int mark; }; char vertex_infos[MAX_VERTEX]; Side_Array matrix[MAX_VERTEX][MAX_VERTEX]; void DFS_For_Array(int x,int y){ for(int j=0;j<MAX_VERTEX;j++){ matrix[j][x].mark=1; } if(vertex_infos[x]==0){ return ; } cout<<vertex_infos[x]; for(int i=y;i<MAX_VERTEX;i++){ if(matrix[x][i].link==1&&matrix[x][i].mark==0){ DFS_For_Array(i,0); } } } int Array_Check(){ for(int i=0;i<MAX_VERTEX;i++){ if(matrix[0][i].mark==0){ return i; } } return -1; } //list struct Side{ int index; int weight; Side* next; }; struct Vertex{ char data; int mark; Side* first; }; typedef Vertex AdjList[MAX_VERTEX]; struct AdjGraph { AdjList adjlist; int num_vertex; int num_side; }; void DFS_For_List(AdjGraph& adjGraph,int x){ if(adjGraph.adjlist[x].data==0||adjGraph.adjlist[x].mark==1){ return; } cout<<adjGraph.adjlist[x].data; adjGraph.adjlist[x].mark=1; Side* p=adjGraph.adjlist[x].first; while(p!=0){ DFS_For_List(adjGraph,p->index); p=p->next; } } int List_Check(AdjGraph& adjGraph){ for(int i=0;i<MAX_VERTEX;i++){ if(adjGraph.adjlist[i].mark==0&&adjGraph.adjlist[i].data!=0){ return i; } } return -1; } int main(){ //array /* for(int i=0;i<MAX_VERTEX;i++){ vertex_infos[i]=0; for(int j=0;j<MAX_VERTEX;j++){ matrix[i][j].link=0; matrix[i][j].mark=0; } } cout<<"input vertex and side nums:"; int num_vertex; int num_side; cin>>num_vertex>>num_side; cout<<"input vertex char data:"; for(int i=0;i<num_vertex;i++){ cin>>vertex_infos[i]; } for(int i=0;i<num_side;i++){ int v1; int v2; cout<<"input two vertex:"; cin>>v1>>v2; matrix[v1][v2].link=1; matrix[v2][v1].link=1; } int index=Array_Check(); while(index!=-1){ DFS_For_Array(index,0); index=Array_Check(); } cout<<endl; */ //list AdjGraph adjGraph; for(int i=0;i<MAX_VERTEX;i++){ adjGraph.adjlist[i].mark=0; adjGraph.adjlist[i].data=0; adjGraph.adjlist[i].first=0; } cout<<"input vertex and side nums:"; cin>>adjGraph.num_vertex>>adjGraph.num_side; cout<<"input vertex char data:"; for(int i=0;i<adjGraph.num_vertex;i++){ cin>>adjGraph.adjlist[i].data; } for(int i=0;i<adjGraph.num_side;i++){ int v1; int v2; cout<<"input two vertex:"; cin>>v1>>v2; Side* side1=new Side(); side1->index=v2; Side* side2=new Side(); side2->index=v1; if(adjGraph.adjlist[v1].first==0){ adjGraph.adjlist[v1].first=side1; } else{ Side* temp=adjGraph.adjlist[v1].first; adjGraph.adjlist[v1].first=side1; side1->next=temp; } if(adjGraph.adjlist[v2].first==0){ adjGraph.adjlist[v2].first=side2; } else{ Side* temp=adjGraph.adjlist[v2].first; adjGraph.adjlist[v2].first=side2; side2->next=temp; } } int index=List_Check(adjGraph); while(index!=-1){ DFS_For_List(adjGraph,index); index=List_Check(adjGraph); } for(int i=0;i<adjGraph.num_vertex;i++){ Side* p=adjGraph.adjlist[i].first; while(p!=0){ Side* temp=p->next; delete p; p=temp; } } return 0; }
