dfs.cpp

有向图从邻接矩阵转换为邻接表后再深度优先遍历

//把邻接矩阵该为邻接表后再遍历之深度优先遍历
#include<iostream.h>
struct node   /*单链表中结点结构*/
{int num;     /*图中结点编号*/
 int val;     /*求值函数*/
 struct node *next;/*指针域*/
};

struct gpnode/*顺序存储空间结点结构*/
{char data;  /*结点值*/
struct node*link;/*指针域*/
};

struct gpnode *creatgp(char d[],int n)/*该函数返回顺序存储空间的首地址*/
{
struct gpnode *head=NULL;
struct node *p=NULL	;
int k,m,v;
head=new gpnode();/*建立存储空间*/
for(k=0;k<n;k++)/*依次对图中的每一个结点建立连接所有后件的单链表*/
{ 
	(head+k)->data=d[k];/*置顺序存储空间的结点值*/
    (head+k)->link=NULL;/*置顺序存储空间结点的指针域为空*/
    cout<<"请输入结点编号和权值"<<endl;
    cin>>m>>v;/*输入第K个结点的信息*/
    while(m>=0)/*输入信息未结束*/
	{
		p=new node();/*分配单链表结点*/
        p->num=m;p->val=v;/*置后件结点编号与权值*/
        p->next=(head+k)->link;/*新结点指针指向原头结点*/
        (head+k)->link=p;/*将结点连接到单链表头*/
        cout<<"请输入结点编号和权值"<<endl;
        cin>>m>>v;/*继续输入后件信息*/
	}
}
 return(head);
}

void dfs(struct gpnode *head,int k,int*mark)/*递归函数*/
{
	struct node *p=NULL;
	cout<<(head+k-1)->data;/*输出当前结点值*/
	mark[k-1]=1;/*记录当前结点的查询标志*/
	p=(head+k-1)->link;/*当前结点的第一个后件结点*/
	while(p!=NULL)/*还存在后件结点*/
	{if(mark[(p->num)-1]==0)/*该后件结点未查访过*/
	dfs(head,p->num,mark);/*递归调用*/
	p=p->next;/*下一个后件结点*/
	}
	
}

void dfsgp(struct gpnode *head,int n)
{
	
    int k,*mark=NULL;
    mark=new int;/*定义标志数组空间*/
	for(k=0;k<n;k++)/*标志数组初始化*/
		mark[k]=0;
	k=0;
	dfs(head,k,mark);
	cout<<endl;
	delete mark;/*释放标志数组空间*/
	
}


void main()
{
	struct gpnode* head=NULL;
	int n;
	cout<<"请输入结点个数"<<endl;
	cin>>n;
	char d[100];
	cout<<"请初始化数组"<<endl;
	for(int i=0;i<n;i++)
		cin>>d[i];
	head=creatgp(d,n);
	dfsgp(head,n);
}