图的深度优先遍历：邻接表实现

这里用邻接表实现图的深度优先遍历，采用递归实现。

#include<iostream>
using namespace std;
#define VERTEXNUM 5//结点数
struct  edgenode
{
    int to;
    int weight; // 边的权值
    edgenode *next;
};
struct vnode
{
    int from;
    edgenode *first;
};
void createGraph(vnode *adjilist, int start, int end,int weight);
void displayGraph(vnode *adjilist,int nodeNum);
void DFT(vnode *adjilist,int* vertexStatusArr,int nodeNum);
void DFTcore(vnode *adjilist,int i,int* vertexStatusArr);
/*更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/*/
int main(void){  

        //创建图
        vnode adjilist[VERTEXNUM];
        int nodeNum=VERTEXNUM;
        for(int i=0;i<nodeNum;i++)
            adjilist[i].first=NULL;
        int vertexStatusArr[VERTEXNUM]={0};
        cout<<vertexStatusArr[4]<<endl;
        createGraph(adjilist,0,3,0);
        createGraph(adjilist,0,4,0);
        createGraph(adjilist,3,1,0);
        createGraph(adjilist,3,2,0);
        createGraph(adjilist,4,1,0);  

        printf("after create:\n");
        displayGraph(adjilist,nodeNum);
        //深度优先遍历
        DFT(adjilist,vertexStatusArr,nodeNum);
        system("pause");
        return 0;
}
//创建图,采取前插法
void createGraph(vnode *adjilist, int start, int end,int weight)
{
    adjilist[start].from=start;
    edgenode *p=new edgenode;
    p->to=end;
    p->weight=weight;
    p->next=adjilist[start].first;
    adjilist[start].first=p;
}
//打印存储的图
void displayGraph(vnode *adjilist,int nodeNum)
{
    int i,j;
    edgenode *p;
    for(i=0;i<nodeNum;i++)
    {
        p=adjilist[i].first;
        while(p)
        {
            cout<<'('<<adjilist[i].from<<','<<p->to<<')'<<endl;
            p=p->next;
        }
     }
}
//深度优先遍历
void DFT(vnode *adjilist, int* vertexStatusArr,int nodeNum)
{
        printf("start BFT graph:\n");
        int i;
        for(i=0;i<nodeNum;i++){
                DFTcore(adjilist,i,vertexStatusArr);
        }
        printf("\n");
}
void DFTcore(vnode *adjilist,int i,int* vertexStatusArr)
{
    if(vertexStatusArr[i] == 1)
        return;
    printf("%d ",i);
    vertexStatusArr[i] = 1;
    edgenode *p;
    for(p=adjilist[i].first;p;p=p->next)
    {
        DFTcore(adjilist, p->to, vertexStatusArr);
    }
}

时间复杂度为O(V+E)。

作者：csdn博客 Duplan

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， int
， 深度
， 图的深度遍历
， dft
， void
， 遍历表
深度遍历
，以便于您获取更多的相关知识。