博客

图的深度优先遍历类似于树的先序遍历，不同之处是为了避免重复访问，采用全局数组存储结点是否已经被访问的信息，对于邻接表而言，找邻接点所需的时间取决于顶点个数和边的个数，因此时间复杂度为o(n+e)，如果把图的深度优先遍历过程所遍历的边保留，把其余边删掉，那么会形成一颗树。

typedef struct ArcNode{ //弧
    struct ArcNode* next;
    int num; //存储结点下标
}ArcNode;

typedef struct AVertype{ //顶点表
    ArcNode* firstArc;
    char data;
}Vertype;

typedef struct{ //邻接表
    Vertype AdjList[MaxSize]; // 注意：邻接表存储的是顶点信息
    int vexNum;
    int edgesNum;
}AGraph;

//邻接表的遍历（依次从每个顶点）
void AGraphTraverse(AGraph* agraph){
    for (int i = 0; i < agraph->vexNum; i++) {
        ArcNode* firstArc = agraph->AdjList[i].firstArc;
        while (firstArc) {
            cout<<agraph->AdjList[i].data<<" : "<<agraph->AdjList[firstArc->num].data<<endl;
            firstArc = firstArc->next;
        }
    }
}

//初始化邻接表
void AgraphInit(AGraph* &agraph){
    char vertex[] = {'0','1','2','3','4','5','6'}; //顶点信息
    agraph->vexNum = sizeof(vertex)/sizeof(char);
    for (int i = 0; i < agraph->vexNum; i++) {
        agraph->AdjList[i].data = vertex[i]; // 输入顶点信息
        agraph->AdjList[i].firstArc = NULL; //置边表为空
    }
    
    ArcNode* e;
    int edges[][2] = {{0,1},{0,2},{1,5},{2,3},{2,6},{3,4}};
    agraph->edgesNum = sizeof(edges)/sizeof(edges[0]);
    for (int i = 0; i < agraph->edgesNum; i++) {
        for (int j = 0; j < 1; j++) {
            int vi = edges[i][0];
            int vj = edges[i][1];
            e = new ArcNode();
            e->num = vj;
            e->next = agraph->AdjList[vi].firstArc; //头插法
            agraph->AdjList[vi].firstArc = e;
        }
    }
    AGraphTraverse(agraph);
}
//邻接表DFS
void AgraphDFS(AGraph* agraph, int i, int visit[]){
    cout<<agraph->AdjList[i].data<<endl;
    visit[i] = 1;
    ArcNode* firstArc = agraph->AdjList[i].firstArc;
    while (firstArc) {
        if (visit[firstArc->num] == 0) {
            AgraphDFS(agraph ,firstArc->num ,visit);
        }
        firstArc = firstArc->next;
    }
}

//邻接表DFS非递归算法
void AGraphDFSNoRec(AGraph* agraph, int i, int visit[]){
    int Stack[MaxSize]; //栈用下标，不要用ArcNode类型
    int top = -1;
    ArcNode* firstArc;
    Stack[++top] = i; // 该结点所有邻接结点入栈
    while (top != -1) {
        int index = Stack[top--]; //出栈
        if (visit[index] == 0) { //访问元素
            cout<<agraph->AdjList[index].data<<endl;
            visit[index] = 1;
            firstArc = agraph->AdjList[index].firstArc;
            while (firstArc) {
                Stack[++top] = firstArc->num; // 该结点所有邻接结点入栈
                firstArc = firstArc->next;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    AGraph* a = new AGraph();
    AgraphInit(a);
    int visit[a->vexNum];
    //memset(visited,0,sizeof(visited));
    for (int i = 0; i < a->vexNum; i++) {
        visit[i] = 0;
    }
    AGraphDFSNoRec(a,0,visit);
}