#include
#include
#define VertexNum 5 //最大顶点数
void CreateGraph(int (*edge)[VertexNum],int start,int end);
void displayGraph(int (*edge)[VertexNum]);
void DFT(int (*edge)[VertexNum],int *VertexStatusArr);
void DFTcore(int (*edge)[VertexNum],int i,int *VertexStatusArr);
int main(void)
{
//动态创建存放边的二维数组
int (*edge)[VertexNum]=(int(*)[VertexNum])malloc(sizeof(int)*VertexNum*VertexNum);
int i,j;
for(i=0;i<VertexNum;i++)
{
for(j=0;j<VertexNum;j++)
{
edge[i][j]=0;
}
}
//存放顶点的遍历状态,0:未遍历,1:已遍历,VertexStatusArr即为顶点
int* VertexStatusArr =(int *)malloc(sizeof(int)*VertexNum);
for(i=0;i<VertexNum;i++)
{
VertexStatusArr[i]=0;
}
printf("after init:\n"); //初始化
displayGraph(edge); //打印
//创建图
CreateGraph(edge,0,3);
CreateGraph(edge,0,4);
CreateGraph(edge,3,1);
CreateGraph(edge,3,2);
CreateGraph(edge,4,1);
printf("after Create:\n"); //之后开始创建
displayGraph(edge);
//深度优先遍历
DFT(edge,VertexStatusArr);
free(edge);
return 0;
}
//创建图
void CreateGraph(int (*edge)[VertexNum],int start,int end)
{
edge[start][end]=1;
}
//打印存储的图
void displayGraph(int (*edge)[VertexNum],int start,int end)
{
int i,j;
for(i=0;i<VertexNum;i++)
{
for(j=0;j<VertexNum;j++)
{
printf("%d",edge[i][j]);
}
printf("\n");
}
}
//深度优先遍历
void DFT(int (*edge)[VertexNum],int *VertexStatusArr)
{
printf("start DFT graph:\n");
int i;
for(i=0;i<VertexNum;i++) //为了遍历有断点的一个图
{
DFTcore(edge,i,VertexStatusArr);
}
printf("\n");
}
void DFTcore(int (*edge)[VertexNum],int i,int *VertexStatusArr)
{
if(VertexStatusArr[i]==1)
{
return ;
}
printf("%d",i);
VertexStatusArr[i]=1;
int j;
for(j=0;j<VertexNum;j++)
{
if(edge[i][j]==1)
{
DFTcore(edge,j,VertexStatusArr);
}
}
}