tu.cpp

图的建立以及深度遍历

#include<iostream.h>

#define OK 1;

#define MAX_VERTEX_NUM 20  //最大顶点数

typedef int VertexType;

typedef int InfoType;

typedef struct ArcNode{

       int adjvex;    //该弧所指向的顶点的位置

       struct ArcNode *nextarc;  //指向下一条弧的指针

}ArcNode;

typedef struct VNode{

       VertexType data;   //顶点信息

       ArcNode  *firstarc;  //指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{

       AdjList vertices;

       int vexnum,arcnum;  //图的当前顶点和弧数

       int kind;  //图的种类标志

}ALGraph;

int CreateGraph(ALGraph &G) {//图的建立

       cout<<"CreateGraph(DG)!\n\n";

       int i,k,j,v1,v2;

       cout<<"输入顶点数目:";

       cin>>G.vexnum;

       cout<<"输入弧的数目:";

       cin>>G.arcnum;

       for(i=0;i<G.vexnum;++i)

       {

              G.vertices[i].data=i;

              G.vertices[i].firstarc=NULL;

       }       

       cout<<"\n输入弧的始点i(int)和终点j(int)!"<<endl;

       for(k=0;k<G.arcnum;++k) {

              cout<<"输入第"<<k+1<<"条弧的始点i:";

              cin>>v1;

              cout<<"输入第"<<k+1<<"条弧的终点j:";

              cin>>v2;

              i=v1;j=v2;    //确定v1,v2在G中的位置   

              while(i<1||i>G.vexnum||j<1||j>G.vexnum){

                     cout<<"输入第"<<k+1<<"条弧的始点i:";

                     cin>>v1;

                     cout<<"输入第"<<k+1<<"条弧的终点j:";

                     cin>>v2;

                     i=v1;j=v2;

              }

              i--;

              j--;

              cout<<"("<<v1<<","<<v2<<")"<<endl;

              ArcNode *p;       

              p=new ArcNode;      //申请新的弧结点

              if(!p){

                     cout<<"空间不足!";

                     return(0);

              }

              p->adjvex=j;

              p->nextarc=G.vertices[i].firstarc;   //对弧的相关信息赋值

              G.vertices[i].firstarc=p;     //将弧结点插入到对应的单链表

       }     

       cout<<"CreateGraph success!\n\n"<<endl;

       return OK;

}

void DFS(ALGraph G,int v,int *visited)       {  

       int w;

    visited[v]=1;

    cout<<v+1<<"->";

    for(w=G.vertices[v].data;

       G.vertices[v].firstarc!=NULL;

       w=G.vertices[v].firstarc->adjvex,G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc)

    if(visited[w]==0)

              DFS(G,w,visited);          

}//从第v个顶点出发,递归地深度优先遍历图G

void DFSGraph(ALGraph G){  

       int v;

    int visited[MAX_VERTEX_NUM];

    for(v=0;v<G.vexnum;++v)

              visited[v]=0;

    for(v=0;v<G.vexnum;++v)

              if(visited[v]==0)

                     DFS(G,v,visited);

}//对图G着深度优先遍历

void main()

{

       ALGraph G;

       CreateGraph(G);

       cout<<"深度优先遍历的结果:"<<"Begin->";

       DFSGraph(G);

       cout<<"End!"<<endl;

       
}