[color=008000]自尊心很受打击[/color]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INFINITY -1
#define OK 1
#define ERROR 0
#define MAX_VERTEX_NUM 20
#define INFEASIBLE -1

typedef struct ArcCell
{
    int adj;  //对于有权图，为权值；对于无权图，用1和0表示
    //InfoType *info; //该弧相关的信息，如果没有，此句可以删除
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct 
{
    char vexs[MAX_VERTEX_NUM];  //顶点向量
    AdjMatrix arcs;      //邻接矩阵
    int vexnum,arcnum;   //图的顶点数和弧数    
}MGraph;
//////////////////////////////////////////清空///////////////////////////////////////////////
void flush_stdin( void )  // 清空“输入缓冲区” 
{
    int c;
    if ( !feof(stdin) ) 
    {
        while( ( c=getchar() ) != '\n' && c != EOF );
    }
} 
///////////////////////////////****辅助函数****//////////////////////////////////////////////
int Locate(MGraph G, char v)   //1.定位
{
    int i=0;
    int x=0;
    for(i=0;i<G.vexnum;i++)
    {
        if(v==G.vexs[i])
        {
            x=i;
            break;
        }
    }    
    if(x==G.vexnum)
    {
        printf("请确定你的输入无误，图中无相关顶点...\n");
        exit(-1);
    }
    return x;
}

char GetVex(MGraph G, char v)  //2.返回v的值
{
    int i;
    if( (i=Locate(G,v)) <0 )
    {
        printf("图中没有该点...\n");
        exit(-1);
    }
    else
        return G.vexs[i];
    
}

int PutVex(MGraph G, char v)  //3.对v赋值
{
    int i;
    if( (i=Locate(G,v)) < 0 )
    {
        printf("图中没有该点...\n");
        exit(-1);
    }
    else
    {
        printf("请你输入v的新值...\n");
        scanf("%d",&G.vexs[i]);
    }
    return OK;
}

int InsertVex(MGraph &G,char v) //4.在图中新建顶点v
{
    if(  (G.vexnum+1) > MAX_VERTEX_NUM )  //顶点个数多于初定义的值
    {
        return INFEASIBLE;
    }
    G.vexs[++G.vexnum ]=v;
    return OK;
}

int DeleteVex(MGraph &G,char v) //5.在图中删除顶点v
{
    int n=G.vexnum;
    int m,i;
    char temp;
    if((m=Locate(G,v))<0)
    {
        return ERROR;
    }
    temp=G.vexs[m];
    G.vexs[m]=G.vexs[n];
    G.vexs[n]=temp;
    for(i=0;i<n;i++)
    {
        G.arcs[i][m]=G.arcs[i][n];
        G.arcs[m][i]=G.arcs[n][i];
    }    
    G.arcs[m][m].adj =-1;
    G.vexnum--;
    return OK;
}

int InsertArc(MGraph &G,char v,char w) //6.在图中插入一条边或弧
{
    int i,j;
    if( (i=Locate(G,v)) <0)
        return ERROR;
    if( (j=Locate(G,w)) <0)
        return ERROR;
    if(i==j)
        return ERROR;
    puts("请你输入新弧的权值...\n");
    scanf("%d",&G.arcs[i][j].adj);
    G.arcnum++;    
    return OK;
}

int DeleteArc(MGraph &G,char v,char w) //7.在图中删除一条边或者弧
{
    int i,j;
    if( (i=Locate(G,v)) <0 )
        return ERROR;
    if( (j=Locate(G,w)) <0 )
        return ERROR;
    G.arcs[i][j].adj=-1;
    G.arcnum--;
    return OK;
}

char FirstAdjVex(MGraph G, char v) //8.返回v的第一个邻接顶点
{
    int i,j;
    char mark;
    if( (i=Locate(G,v)) < 0 )
    {
        puts("图中没有此点...\n");
        exit('0');
    }
    for(j=0;j<G.vexnum;j++)
    {
        if(G.arcs[i][j].adj!=-1)
        {
            mark=G.vexs[j];
            break;
        }
    }    
    if(j==G.vexnum)
        return '0';
    return mark;
}

char NextAdjVex(MGraph G,char v,char w) //9.返回v的(相对于w的)下一个邻接顶点(第二个邻接点)
{
    int i,j,m;
    char mark;
    if( (i=Locate(G,v)) <0 )
        return ERROR;
    if( (j=Locate(G,w)) <0 )
        return ERROR;
    for(m=j+1; m<G.vexnum; m++)
    {
        if(G.arcs[i][m].adj!=-1)
        {
            mark=G.vexs[m];
            break;    
        }
    }
    if(m==G.vexnum)
    {        
        return '0';
    }
    return mark;

}

//////////////////////////////******遍历函数******//////////////////////////////////////
int visited[MAX_VERTEX_NUM];
int v;

void DFS(MGraph G, char  ch)  //1.从第v个顶点出发递归深度优先遍历图G
{
    char w;
    visited[v]=1;
    printf("%c ",ch);
    for( w=FirstAdjVex(G,ch); w!='0'; w=NextAdjVex(G,ch,w))
    {
        if(!visited[w])   //如果该点没有被访问
            DFS(G,w);    //递归调用DFS()
    }
}

void DFSTraverse(MGraph G,char ch)
{
    int v;
    for(v=0;v<G.vexnum;v++)
    {
        visited[v]=0;    //访问标志数组初始化
    }
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])
        {
            DFS(G,ch);  
        }
    }


}

///////////////////////////////******功能函数*******////////////////////////////////////
int CreateUDN(MGraph &G)   //1.构造无向网
{
int i,j,k;
char v1,v2;
int w;
printf("请你输入该网的顶点数和弧数...\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
for(i=0;i<G.vexnum;i++)    //构造顶点向量
{
    printf("请输入各顶点...\n");
    scanf("%c",&G.vexs[i]);
    flush_stdin();
}
for(i=0;i<G.vexnum;i++)   //初始化邻接矩阵
{
    for(j=0;j<G.vexnum;j++)
    {
        G.arcs[i][j].adj=-1;
        //G.arcs[i][j].info=NULL;
    }
}
for(k=0;k<G.arcnum;k++)
{
    printf("请输入一条边上的两个顶点及其权值...\n");
    scanf("%c%c%d",&v1,&v2,&w);
    flush_stdin();
    i=Locate(G,v1);
    j=Locate(G,v2);
    G.arcs[i][j].adj=w;   //<v1,v2>的权值
    G.arcs[j][i]=G.arcs[i][j];
}
return OK;
}


//////////////////////////////*****main函数******/////////////////////////////////
void main()
{
    MGraph G;
    char ch;
    CreateUDN(G);
    printf("深度遍历图G...\n");
    printf("请问你想从哪个顶点开始遍历...\n");
    scanf("%c",&ch);
    DFSTraverse(G ,ch);
}