#include"stdio.h"
#include"stdlib.h"
#define MAXSIZE 50
#define MAXVALUE 32767
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType Vertex[MAXSIZE];
EdgeType Edge[MAXSIZE][MAXSIZE];
int vertexnum,edgenum;
int isTrav[MAXSIZE];
int GraphType;
}*MGraph,Graph;
typedef struct
{
int Data[MAXSIZE];
int top;
}Stack,*PStack;
PStack Init_Stack()
{
PStack S;
S=(PStack)malloc(sizeof(Stack));
S->top=-1;
return S;
}
void Push_Stack(PStack S,int temp)
{
if(S->top==MAXSIZE-1)
printf("栈满，溢出！\n");
else
{
S->top++;
S->Data[S->top]=temp;
}
}
int Empty_Stack(PStack S)
{
if(S->top==-1)
return 1;
else
return 0;
}
void Pop_Stack(PStack S,int*temp)
{
if(Empty_Stack(S))
return ;
else
{
*temp=S->Data[S->top];
S->top--;
}
}
void Destory_Stack(PStack*S)
{
if(*S)
free(*S);
*S=NULL;
}
MGraph Create_Graph()
{
int i,j,k,weight;
char start,end;
MGraph G;
G=(MGraph)malloc(sizeof(Graph));
printf("请选择想要创建的图形：'0':无向图,'1':有向图\n");
scanf("%d",&(G->GraphType));
printf("请输入图的定点数和图的边数： ");
scanf("%d%d",&G->vertexnum,&G->edgenum);
for(i=0;i<G->vertexnum;i++)
{
getchar();
printf("输入第%d个节点： ",i+1);
scanf("%c",&G->Vertex[i]);
}
for(i=0;i<G->vertexnum;i++)
for(j=0;j<G->vertexnum;j++)
if(i==j)
G->Edge[i][j]=0;
else
G->Edge[i][j]=MAXVALUE;
printf("输入构成各边的两个顶点及权值(用逗号分隔):\n");
for(k=0;k<G->edgenum;k++)
{
getchar();
printf("第%d条边： ",k+1);
scanf("%c,%c,%d",&start,&end,&weight);
for(i=0;start!=G->Vertex[i];i++); //在已有顶点中查找始点
for(j=0;end!=G->Vertex[j];j++); //在已有顶点中查找结终点
G->Edge[i][j]=weight;
if(G->GraphType==0)
G->Edge[j][i]=weight;
}
return G;
}
void OutMatrix(MGraph G)
{
int i,j;
for(i=0;i<G->vertexnum;i++)
printf("\t%c",G->Vertex[i]);
printf("\n");
for(i=0;i<G->vertexnum;i++)
{
printf("%c\t",G->Vertex[i]);
for(j=0;j<G->vertexnum;j++)
{
if(G->Edge[i][j]>=MAXVALUE)
printf("∞\t");
else
printf("%d\t",G->Edge[i][j]);
}
printf("\n");
}
}
void DFS(MGraph G,int k)
{
int i=0,temp=k;
PStack S;
S=Init_Stack();
printf("%c->",G->Vertex[temp]);
Push_Stack(S,temp);
while(!Empty_Stack(S))
{
for(i=0;i<G->vertexnum;i++)
if(G->Edge[k][i]!=MAXSIZE&&!G->isTrav[i])
break;
if(i>=G->vertexnum)
{
Pop_Stack(S,&temp);
k=temp;
}
else
{
G->isTrav[i]=1;
temp=i;
k=temp;
printf("%c->",G->Vertex[temp]);
Push_Stack(S,temp);
}
}
Destory_Stack(&S);
}
void main()
{
int i=0;
MGraph G;
G=Create_Graph();
OutMatrix(G);
for(i=0;i<G->vertexnum;i++)
G->isTrav[i]=0;
for(i=0;i<G->vertexnum;i++)
if(!G->isTrav[i])
{
G->isTrav[i]=1;
DFS(G,i);
}
printf("\n");
}
