#graph.h头文件

1 #ifndef GRAPH_H 2 #define GRAPH_H 3  4 struct adjNode{ 5     int node; 6     struct adjNode *next; 7 }; 8  9 10 /*图的矩阵表示向邻接表表示的转换*/11 void matrixToAdjlist(int *matrix, adjNode *adjList, int n){12     int i, j;13     adjNode *tempNode;14     for(i=0; i
     
      =0; j--){19             if(*(matrix+i*n+j)== 1){20                 tempNode=(adjNode *)malloc(sizeof(adjNode));21                 tempNode->next=adjList[i].next;22                 tempNode->node=j;23                 adjList[i].next=tempNode;24             }25         }26     }27 }28 29 /*释放邻接表中分配的空间*/30 void freeAdjList(adjNode *adjList, int n){31     int i;32     adjNode *tempNode;33 34     for(i=0; i
      
       next;38             free(tempNode);39             tempNode=adjList[i].next;40         }41     }42 43     free(adjList);44 }45 46 #endif // GRAPH_H
      
     

 

main.h

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include "graph.h"  5 using namespace std;  6   7 const int invalid_p=-1;  8 int gtm=0;  9 enum Color{w, g, b}; 10  11 struct DFS_struct{ 12     Color color; 13     int parent; 14     int dtime, ftime;  //节点的发现时间和邻接表扫描完成时间 15 }; 16  17 void DFS_visit(adjNode *adjList, DFS_struct *dfsArray, int u){ 18     int v; 19     adjNode *tempNode; 20  21     dfsArray[u].color=g; 22     gtm += 1; 23     dfsArray[u].dtime=gtm; 24  25     tempNode=adjList[u].next; 26     while(tempNode != NULL){ 27         v=tempNode->node; 28         if(dfsArray[v].color == w){ 29            dfsArray[v].parent=u; 30            DFS_visit(adjList, dfsArray, v); 31         } 32  33         tempNode=tempNode->next; 34     } 35  36     dfsArray[u].color=b; 37     gtm += 1; 38     dfsArray[u].ftime=gtm; 39 } 40  41 void DFS(adjNode *adjList, DFS_struct *dfsArray, int n, vector
        
          &forestRoots){ 42     int i; 43     for(i=0; i
         

forestRoots; //forestRoots中保存每棵深度优先搜索树的树根节点编号 64 65 printf("Input node number: "); 66 scanf("%d", &nodeNum); 67 68 matrix=(int *)malloc(sizeof(int)*nodeNum*nodeNum); 69 adjList=(adjNode *)malloc(sizeof(adjNode)*nodeNum); 70 71 for(i=0; i

%d", tempNode->node); 91 tempNode=tempNode->next; 92 } 93 printf("\n"); 94 } 95 96 dfsArray=(DFS_struct *)malloc(sizeof(DFS_struct)*nodeNum); 97 DFS(adjList, dfsArray, nodeNum, forestRoots); 98 99 /*在这里深度优先搜索森林已经建立，可以进行别的操作*/100 printf("DFS learning completed\n");101 printf("forest roots:");102 for(i=0; i