- #include <iostream>
- using namespace std;
- #define MAX_SIZE 20
- using namespace std;
- static int x = [](){std::iOS::sync_with_stdio(false);cin.tie(0);return 0;}();
- typedef struct A{
- int adj;
- int *ptr;
- }Val[MAX_SIZE][MAX_SIZE];
- struct Graph{
- int Vertex[MAX_SIZE];
- Val val;
- int vertex, arc;
- };
- int FindVertex(Graph *G, int v){// 根据顶点数组判断顶点在二维数组中的位置
- for(int i = 0; i <G->vertex; ++i){
- if(G->Vertex[i] == v){
- return i;
- }
- }
- return -1;
- }
- void CreatGraph(Graph *G){// 创建无向图
- cout <<"Please input the number of vertex and arc:" << endl;
- cin>> G->vertex>> G->arc;
- cout <<"Please input the data of vertex:" << endl;
- for(int i = 0; i < G->vertex; ++i)
- cin>> G->Vertex[i];
- for(int i = 0; i <G->vertex; ++i){
- for(int j = 0; j <G->arc; ++j){
- G->val[i][j].adj = 0;
- G->val[i][j].ptr = nullptr;
- }
- }
- cout <<"Please input the relation of vertex and arc:" << endl;
- for(int i = 0; i < G->arc; ++i){
- int v, a;
- cin>> v>> a;
- int m = FindVertex(G, v);
- int n = FindVertex(G, a);
- if(m == -1 || n == -1){
- cout <<"No!!!";
- break;
- }
- G->val[m][n].adj = 1;
- G->val[n][m].adj = 1;
- }
- }
- int Visited[MAX_SIZE];// 记录顶点是否被访问过
- int FindFirst(Graph *G, int v){// 寻找顶点周围有边的顶点
- for(int i = 0; i <G->vertex; ++i){
- if(G->val[v][i].adj)
- return i;
- }
- return -1;
- }
- int NextVertex(Graph *G, int v, int w){// 从下一个位置寻找, 顶点周围有边的顶点
- for(int i = w + 1; i <G->vertex; ++i ){
- if(G->val[v][i].adj)
- return i;
- }
- return -1;
- }
- void PrintV(Graph *G, int v){
- cout <<G->Vertex[v] <<" ";
- }
- void DFS(Graph *G, int v){
- Visited[v] = true;// 准备访问该顶点
- PrintV(G, v);// 访问顶点
- for(int i = FindFirst(G, v); i>= 0; i = NextVertex(G, v, i)){
- if(!Visited[i]){// 如果该顶点未被访问, 则继续搜索
- DFS(G, i);
- }
- }
- }
- void DFSTr(Graph *G){
- for(int i = 0; i <G->vertex; ++i){
- Visited[i] = false;// 设置全部顶点未访问
- }
- for(int i = 0; i <G->vertex; ++i){
- if(!Visited[i]){
- DFS(G, i);
- }
- }
- }
- int main()
- {
- Graph *G = new Graph[sizeof(Graph)];
- CreatGraph(G);
- DFSTr(G);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2997248.html