邻接矩阵的DFS

采用递归的方法

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define MaxSize 20
  5 
  6 typedef struct{
  7     int Ver[MaxSize];
  8     int Edge[MaxSize][MaxSize];
  9     int VerNum;
 10     int EdgeNum;
 11 }Graph;
 12 
 13 void CreateGraph(Graph &G)
 14 {
 15     int x,i,j;
 16     printf("输入顶点元素:\n");
 17     for(i=0;i<MaxSize;i++)
 18     {
 19         scanf("%d",&x);
 20         if(x==-1)
 21             break;
 22         else
 23         {
 24             G.Ver[i]=x;
 25             G.VerNum++;    
 26         }
 27     }
 28     
 29     printf("输入边(0/1):\n");
 30     for(i=0;i<G.VerNum;i++)
 31     {
 32         for(j=0;j<G.VerNum;j++)
 33         {
 34             scanf("%d",&x);
 35             G.Edge[i][j]=x;
 36             if(x==1)
 37                 G.EdgeNum++;
 38         }
 39     }
 40         
 41     G.EdgeNum=G.EdgeNum/2;
 42 }
 43 
 44 int ArrNum(Graph G,int ver)
 45 {
 46     for(int i=0;i<G.VerNum;i++)
 47         if(G.Ver[i]==ver)
 48             return i;
 49     return -1;
 50 }
 51 
 52 int FirstNeighbor(Graph G,int ver)
 53 {
 54     int x=ArrNum(G,ver);
 55     for(int i=0;i<G.VerNum;i++)
 56         if(G.Edge[x][i]==1)
 57             return i;
 58     return -1;
 59 }
 60 
 61 int NextNeighbor(Graph G,int ver,int w)
 62 {
 63     int x=ArrNum(G,ver);
 64     for(int i=w+1;i<G.VerNum;i++)
 65         if(G.Edge[x][i]==1)
 66             return i;
 67     return -1;
 68 }
 69 
 70 void DisplayGraph(Graph G)
 71 {
 72     int i,j;
 73     printf("顶点元素有%d个,边有%d个\n顶点元素分别是:",G.VerNum,G.EdgeNum);
 74     for(i=0;i<G.VerNum;i++)
 75         printf("%d ",G.Ver[i]);
 76     printf("\n");
 77     printf("邻接矩阵为:\n");
 78     for(i=0;i<G.VerNum;i++)
 79         for(j=0;j<G.VerNum;j++)
 80         {
 81             printf("%d ",G.Edge[i][j]);
 82             if(j==G.VerNum-1)
 83                 printf("\n");    
 84         }
 85 }
 86 
 87 bool visited[MaxSize];
 88 void DFS(Graph G,int v)
 89 {
 90     printf("%d ",G.Ver[v]);
 91     visited[v]=true;
 92     for(int w=FirstNeighbor(G,G.Ver[v]);w>=0;w=NextNeighbor(G,G.Ver[v],w))
 93     {
 94         if(!visited[w])
 95             DFS(G,w);
 96     }
 97 }
 98 
 99 void DFSTraverse(Graph G)
100 {
101     for(int i=0;i<G.VerNum;i++)
102         visited[i]=false;
103     for(int i=0;i<G.VerNum;i++)
104         if(!visited[i])
105             DFS(G,i);
106 }
107 
108 int main()
109 {
110     Graph G;
111     CreateGraph(G);
112     DisplayGraph(G);
113     
114     DFSTraverse(G);
115     return 0;    
116 }