graph.cpp

用c做的图的数据结构的作业,建立有向图,深度广度搜索,分为递归和非递归方式.

#include <iostream>
using namespace std;
#include <cstdlib>
#define MAX 20
typedef char  DATATYPE;
typedef int   INFO;
//有向图
 
typedef struct ArcNode
{
        char           adjvex;
        INFO           info;
        //INFO           location;  
        struct ArcNode *nextarc;               
}ArcNode;

typedef struct VNode
{
        DATATYPE       data;
        int            du;
        ArcNode        *firstarc; 
}VNode, AdjList[MAX];

typedef struct 
{
        AdjList vertices;
        int     vexnum,arcnum;
       // int     kind;
}ALGraph;

//位置确定 
int Locate(ALGraph G,char ch)
{
        int i;
        for (i = 0; i < G.vexnum; i++)
        {
                if (ch == G.vertices[i].data)
                        return i;                               
        }
        return -1;
}

int visited[MAX];
//有向图创建 
int Creat_Graph(ALGraph &G)
{
        char ar, as;
        int info;
        ArcNode *p, *q;
        cout<<"顶点个数，边数>>"<<endl;
        cin>>G.vexnum>>G.arcnum;       
        for (int i = 0; i < G.vexnum; i++)
        {
                G.vertices[i].du = 0;
                G.vertices[i].data = 0;
                G.vertices[i].firstarc = NULL;
        }
        
        cout<<"顶点信息"<<endl;        
        for (int i = 0; i < G.vexnum; i++)
        {
                cin>>G.vertices[i].data;
        }
        
        cout<<"边的始点、终点及权值"<<endl;        
        for (int i = 0; i < G.arcnum; i++)
        {
                cin>>ar>>as>>info;
                p = (ArcNode *)malloc(sizeof(ArcNode));                 
                if (!p)
                {
                        cout<<"ERROR!"<<endl;
                        exit(0);
                }
                
                p->adjvex = as;
                p->info = info;                
                if (!G.vertices[Locate(G,ar)].firstarc)
                {
                        G.vertices[Locate(G,ar)].firstarc = p;
                        q = p;
                        G.vertices[Locate(G,ar)].du++;
                }
                else
                {                      
                        q = G.vertices[Locate(G,ar)].firstarc;
                        while (q->nextarc)
                                q = q->nextarc;                                 
                        q->nextarc = p;
                        q = p;
                        G.vertices[Locate(G,ar)].du++;
                }   
                
                p->nextarc = NULL;                                                                                                                 
        }
        
        p->nextarc = NULL;
        return 1;                               
}

//有向图输出 
int Show(ALGraph G)
{
        ArcNode *p = NULL;
        system("cls");
        for (int i = 0; i < G.vexnum; i++)
        {
               cout<<G.vertices[i].data<<"|"<<G.vertices[i].du;
               p = G.vertices[i].firstarc;
               while (p)
               {
                        cout<<" "<<p->adjvex<<"|"<<p->info;
                        p = p->nextarc;
               }
               
               cout<<endl;                       
        }             
        return 1; 
}

//递归深度搜索
//*********************************************************  
void DFS1(ALGraph G, char ch)
{
        int i;
        if ((i = Locate(G,ch)) < 0)
        {
                cout<<"no this word!"<<endl;
                exit(0);                
        }
        ArcNode *p;
        p  = G.vertices[i].firstarc;
        visited[i] = true;
        cout<<"  "<<ch<<endl;
        while (NULL != p)
        {
                if (!visited[Locate(G,p->adjvex)])
                {
                        DFS1(G,p->adjvex);                        
                }
                p = p->nextarc;            
        } 
}

void DFSF(ALGraph G)
{

        char ch;
        cout<<"ch>>"<<endl;
        cin>>ch;                                                                                          
        for (int i = 0; i < G.vexnum; i++)
        {
                visited[i] = false; 
        }
        for (int ii = 0; ii < G.vexnum; ii++)
        {
                if (!visited[ii])
                {
                        DFS1(G, ch);
                }
        }       
}
//**********************************************************

int DFSTraverse(ALGraph G)
{
        char *stack,ch;
        int top=-1,v;
        ArcNode *p=NULL;
        cout<<"ch>>"<<endl;
        cin>>ch;
        for (int i=0; i<G.vexnum; i++)
        {
                visited[i]=false;
        }
        if (!(stack = (char *)malloc(G.vexnum*sizeof(char))))
        {
                cout<<"ERROR"<<endl;
                exit(0);
        }
        visited[Locate(G,ch)] = true;
        cout<<" "<<ch<<endl;
        stack[++top] = ch;
        for (int i=0; i<G.vexnum; i++)
        {                             
                        while (top != -1)
                        {
                                p = G.vertices[Locate(G,stack[top])].firstarc;
                                while (p != NULL)
                                {                                        
                                        if (!visited[Locate(G,p->adjvex)])
                                        {
                                                visited[Locate(G,p->adjvex)] = true;
                                                cout<<" "<<p->adjvex<<endl;
                                                stack[++top] = p->adjvex;
                                                break;                                                                            
                                        }
                                        p = p->nextarc;
                                }
                                if (p == NULL)
                                {                                               
                                         --top;
                                }                              
                        }            
        }
        return 0;               
        
}

int BFSTraverse(ALGraph G)
{
        ArcNode *p = NULL;
        char ch;
        for (int i = 0; i < G.vexnum; i++)
        {
                visited[i] = false;
        }
        int *queue, front, rear;
        front = rear = 0; 
        if (!(queue = (int *)malloc(G.vexnum*sizeof(int))))
        {
                cout<<"ERROR!"<<endl;
                exit(0);
        } 
        
        for (int v = 0; v < G.vexnum; v++)
        {
                if (!visited[v])
                {
                        visited[v] = true;
                        cout<<G.vertices[v].data<<endl;
                        queue[rear] = G.vertices[v].data;
                        rear = (rear+1)%G.vexnum;
                        while (front != rear)
                        {                               
                                ch = queue[front];                        
                                front = (front + 1)%G.vexnum;
                                p = G.vertices[Locate(G,ch)].firstarc;
                                while (p != NULL)
                                {
                                       if (!visited[Locate(G,ch)])
                                        {
                                                visited[Locate(G,ch)] = true;
                                                cout<<ch<<" ";                               
                                                queue[rear] = p->adjvex;
                                                rear = (rear+1)%G.vexnum;
                                                p = p->nextarc;
                                        }
                                        else
                                        {
                                                if (!visited[Locate(G,p->adjvex)])
                                                {
                                                        cout<<p->adjvex;
                                                        visited[Locate(G,p->adjvex)]=true;
                                                } 
                                                queue[rear] = p->adjvex;
                                                rear = (rear+1)%G.vexnum;
                                                p = p->nextarc;
                                        }
                                }                                                
                        }
                cout<<endl;
                }               
        }

        cout<<endl;                            
}
//**********************************************************

int main(void)
{
        int a;
        while(true) 
        {
                gg:
                {                       
                        cout<<"   --------1 创建图--------------"<<endl;
                        cout<<"   --------2 输出图--------------"<<endl;
                        cout<<"   --------3 搜索----------------"<<endl; 
                        cout<<"   --------4 退出----------------"<<endl; 
                        cin>>a;
                }               
                switch (a)
                {
                        case 1:
                                ALGraph G;
                                Creat_Graph(G);
                                cout<<"Creat graph success !"<<endl;
                                goto gg;
                        case 2:
                                Show(G);
                                goto gg;
                        case 3:
                                int tag;
                                ll:
                                {                                                                       
                                        cout<<"1 深度搜索(递归)"<<endl;
                                        cout<<"2 深度搜索(非递归)"<<endl;
                                        cout<<"3 广度搜索"<<endl;
                                        cout<<"4 退出"<<endl;
                                        cin>>tag;
                                }
                                switch (tag)
                                {
                                        case 1:
                                                DFSF(G);
                                                goto ll;  
                                        case 2:
                                                DFSTraverse(G);
                                                goto ll;
                                        case 3:
                                                BFSTraverse(G);
                                                goto ll;
                                        case 4:
                                                goto gg;
                                        default:
                                                cout<<"Wrong enter!"<<endl;
                                                break;
                                } 
                                break;                                                             
                        case 4:
                                return 0;
                        default:
                                cout<<"Wrong enter!"<<endl; 
                                break;                                                                                  
                }
                getchar();
        }
        
        system("pause");
        return 0;
}