#include
#include
#define Max 100
#define Wu 0
typedef struct
{
int vexs[Max];
int arcs[Max][Max];
int vexnum;
}MGraph;
int visited[Max];
void CreateGraph(MGraph *G,int n)
{
int i,j,e,u,v,value;
for(i=0;i<n;i++)
{
printf("输入第%d个顶点信息:",i+1);
scanf("%d",&G->vexs[i]);
for(j=0;j<n;j++)
G->arcs[i][j]=Wu;
}
for(i=0;i<n;i++)
G->arcs[i][j]=0;
printf("请输入边的个数:");
scanf("%d",&e);
for(i=0;i<e;i++)
{
printf("输入边所依附的两个顶点和值:<u,v,value>:");
scanf("%d%d%d",&u,&v,&value);
G->arcs[u][v]=value;
G->arcs[v][u]=value;
}
printf("邻接矩阵结构为:\n");
for(i=0;i<n;i++)
printf("%4d",G->vexs[i]);
printf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%4d",G->arcs[i][j]);
printf("\n");
}
}
int GetFirstVex(MGraph G,int v)
{
int col;
if(vG.vexnum)
{
printf("参数v越界出错!\n");
exit(1);
}
for(col=0;col<=G.vexnum;col++)
if(G.arcs[v][col]>0&&G.arcs[v][col]
return col;
return -1;
}
int GetNextVex(MGraph G,int v1,int v2)
{
int col;
if(v1G.vexnum||v2G.vexnum)
{
printf("参数v1或v2越界出错!\n");
exit(1);
}
for(col=v2+1;col<=G.vexnum;col++)
if(G.arcs[v1][col]>0&&G.arcs[v1][col]<Wu)
return col;
return -1;
}
void DFS(MGraph G,int v)
{
int w;
printf("%4c",G.vexs[v]);
visited[v]=1;
w=GetFirstVex(G,v);
while(w!=-1)
{
if( !visited[w])
DFS(G,w);
w=GetNextVex(G,v,w);
}
}
void DFST(MGraph G)
{
int i;
for(i=0;i<G.vexnum;i++)
visited[i]=0;
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFS(G,i);
}
void main()
{
MGraph G;
int n;
printf("输入顶点数:");
scanf("%d",&n);
CreateGraph(&G,n);
printf("深度优先遍历为:");
DFST(G);
printf("\n");
}