DBS.rar_DBS

#include <iostream> using namespace std; #define NULL 0 enum color{WHITE = 0,GRAY,BLACK}; struct V{ int id; int color; int parent; //父辈 int start; //标记第一个时间 int finish; //检查结束后标记的第二个时间 V * next; }; struct Stack{ int top; int length; int * stack; Stack(int n){ top = 0; length = n; stack = (int *)malloc(sizeof(int)*n); } bool stack_empty(){ if(top == 0) return 1; else return 0; } void push(int x){ top ++; stack[top] = x; } int pop(){ if(stack_empty()) { cout << "underflow" << endl; return 0; } else { top --; return stack[top + 1]; } } }; void creat_g(V* arr,int n){ for(int i = 1; i <= n;i ++) { arr[i].id = i; arr[i].next = NULL; cout << i <<"点与几个点相连" << endl; int j; cin >> j; V *iterator1 = &arr[i]; while(j) { for(;iterator1->next;iterator1 = iterator1->next); V* New = (V*)malloc(sizeof(V)); cout << "id:" << endl; cin >> New->id; iterator1->next = New; New->next = NULL; j -- ; } } } void DBS(V * arr,int n){ for(int i = 1;i <= n;i ++) { arr[i].color = WHITE; arr[i].parent = 0; } int time = 0; for(int i = 1;i <= n;i ++) { if(arr[i].color == WHITE) { time ++; arr[i].color = GRAY; arr[i].start = time; Stack one(n); one.push(arr[i].id); while(!one.stack_empty()) { V *iterator2 = arr[one.top].next; while(iterator2) { if(arr[iterator2->id].color == WHITE ) { arr[iterator2->id].parent = one.top; one.push(arr[iterator2->id].id); arr[iterator2->id].color = GRAY; time ++; arr[iterator2->id].start = time; break; //保证是深度优先 } iterator2 = iterator2->next; } if(iterator2 == NULL) //出栈条件的判断 while(!one.stack_empty()) { time ++; arr[one.top].color = BLACK; arr[one.top].finish = time; cout << arr[one.stack].id << endl; } } } } } int main(){ int n; cout << "输入图中有几个点:" << endl; cin >> n; V* arr = (V *)malloc(sizeof(V)*n); creat_g(arr,n); DBS(arr,n); system("pause"); return 0; }