邻接表|DFS|BFS

结构定义

#define INIFINITY 1000              // 最大值
#define MAX_VERTEX_NUM 20               //最大顶点数
#include<string> 

using namespace std;
typedef enum{DG,DN,UDG,UDN} GraphKind;  //图的四种类型
typedef string VertexType;
typedef int  InfoType;
typedef  struct ArcNode{
     int adjvex;
     InfoType weight;
     struct ArcNode *nextarc;
}ArcNode;

typedef struct Vnode{
      VertexType  data;
      ArcNode      *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM ]; 

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

创建无向图

Status CreateUDG(ALGraph &G) { //建立无向图的邻接表
    int i,j,k;
    VertexType v1,v2;
    ArcNode *p,*q;
    cout<<endl<<"输入图的顶点数(VEX)和边数(ARC)："<<endl;
    cout<<"vexnum|顶点数:";
    cin>>G.vexnum;
    cout<<"arcnum|边数:";
    cin>>G.arcnum;
    cout<<endl;
    cout<<"输入图的顶点信息："<<endl;
    for (i=0; i<G.vexnum; i++) {
        cout<<"VEX "<<i<<":";
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }

    cout<<endl;
    cout<<"输入边的信息v1,v2"<<endl;
    for (k=0; k<G.arcnum; k++) {
        cout<<endl<<"V1:";
        cin>>v1;

        cout<<"V2:";
        cin>>v2;
        i=LocateVex(G,v1);
        cout<<"find v1："<<i<<endl;
        j=LocateVex(G,v2);
        cout<<"find v2："<<j<<endl;
        //if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum) {
        if(i!=-1&&j!=-1) {
            p=(ArcNode *)malloc (sizeof(ArcNode ));
            p->adjvex=j;
            p->nextarc=G.vertices[i].firstarc;
            G.vertices[i].firstarc=p;

            q=(ArcNode *)malloc (sizeof(ArcNode ));
            q->adjvex=i;
            q->nextarc=G.vertices[j].firstarc;
            G.vertices[j].firstarc=q;
        }

        else {
            cout<<"节点输入错误 请重新输入"<<endl;
            k = k-1;
            continue;
        }
    }//for k
    return OK;
}//CreateUDG

输出

void PrintGraph(ALGraph G) {
    int i,j;
    ArcNode *p;
    cout<<endl<<"图的顶点数和边数：";
    cout<<setw(3)<<G.vexnum<<setw(3)<<G.arcnum;
    cout<<endl<<"图的顶点信息："<<endl;
    for (i=0; i<G.vexnum; i++) cout<<setw(3)<<G.vertices[i].data;
    cout<<endl<<"图的邻接表："<<endl;
    for (i=0; i<G.vexnum; i++) {
        cout<<setw(3)<<G.vertices[i].data<<"的邻接点：";
        p=G.vertices[i].firstarc;
        while (p) {
            j=p->adjvex;
            cout<<G.vertices[j].data;
            p=p->nextarc;
        }//while
        cout<<endl;
    }//for

    cout<<endl;
}

DFS

int visited[MAX_VERTEX_NUM];
void DFS(ALGraph &G,int v) {
    visited[v] = true;
    cout<<G.vertices[v].data<<" ";
    ArcNode *p = G.vertices[v].firstarc;
    while(p) {
        if(!visited[p->adjvex])
            DFS(G,p->adjvex);
        p = p->nextarc;
    }
}

void DFSTraverse(ALGraph &G) {
    for(int i=0; i<G.vexnum; i++)
        visited[i] = false; //初始化访问数组
    for(int i=0; i<G.vexnum; i++) {
        if(!visited[i])
            DFS(G,i);
    }
}

BFS

void BFSTraverse(ALGraph &G) {
    for(int i=0; i<G.vexnum; i++)
        visited[i] = false;
    queue<int>q;
    for(int i=0; i<G.vexnum; i++) {
        if(!visited[i]) {
            visited[i] = true;
            q.push(i);
            cout<<G.vertices[i].data<<" ";

            while(!q.empty()) {
                int x = q.front();
                q.pop();
                ArcNode*p = G.vertices[i].firstarc;
                while(p) {
                    if(!visited[p->adjvex]) {
                        //  p的邻接点未被访问过
                        visited[p->adjvex] = true;
                        cout<<G.vertices[p->adjvex].data<<" ";
                    }
                    p = p->nextarc;
                }
            }
        }
    }
}