图的遍历：深度和广度

sampsom

谢谢大佬，大佬真好！

rnm4000

谢谢分享

AShengXz

ohhohh

ohhohh

ohhohh

日暮客愁新

sunyt

学习

sunyt

sunyt

小bai学c

ohhohh

LDAJUN

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX 100     //最大顶点数
typedef struct BNode
{
    int pointPosite;             //该边所指向顶点的位置
    struct BNode *nextB;         //指向下一条边的指针
    int info;                             //和边相关的信息
}BNode;
typedef struct DNode
{
    string data;                   //存放顶点信息
    BNode *firstB;              //指针指向第一条依附该顶点的边
}DNode,AdjList[MAX];//AdjList表领接表类型``

typedef struct
{
    AdjList vertices;           //顶点向量
    int DNum, BNum;             //图的当前顶点数和边数
}TGraph;

typedef struct
{
    string *base;          //存储空间的基地址
    int front;                //头指针
    int rear;                //尾指针
}SqQueue;

void InitQueue(SqQueue &Q)
{//构造一个空队列
    Q.base = new string[MAX];       
    if(!Q.base)
    {
        cout<<"内存分配失败"<<endl;
    }
    Q.front = Q.rear = 0;
}
void EnQueue(SqQueue &Q, string e)
{
    if((Q.rear+1)%MAX == Q.front)
    {
        cout<<"队列已满"<<endl;
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1)%MAX;
}
string DeQueue(SqQueue &Q, string &e)
{
    if(Q.front == Q.rear)
    {
        cout<<"队列为空"<<endl;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAX;
    return e;
}
bool Empty(SqQueue Q)
{
    if(Q.front == Q.rear)
    {
        return true;
    }
    return false;
}

void CreateUDG(TGraph &G)       //无向图UDG
{
    string v1,v2;
    cout<<"请输入所要创建图的总顶点数和总边数：";
    cin>>G.DNum>>G.BNum;         //输入总顶点数和总边数
    for(int i = 0; i < G.DNum; ++i) //输入各点，构造表头结点表
    {
        cout<<"请输入第"<<i+1<<"个顶点的值：";
        cin>>G.vertices[i].data;    //输入顶点值
        G.vertices[i].firstB = NULL;//初始化表头结点指针域为空
    }
    for(int k = 0; k < G.BNum; ++k) //输入各边，构造领接表
    {
        BNode *p1,*p2;
        cout<<"请输入第"<<k+1<<"条边的信息：";
        cin>>v1>>v2;                //输入一条边依附的两个顶点
        int m = LocateVex(G, v1); int n = LocateVex(G, v2); //得到v1 v2在G.vertices中的序号
        p1 = new BNode;         //生成一个新的边结点*p1
        p1->pointPosite = n;    //邻接点序号为n
        p1->nextB = G.vertices[m].firstB;   //头插法
        G.vertices[m].firstB = p1;
        p2 = new BNode;
        p2->pointPosite = m;
        p2->nextB = G.vertices[n].firstB;
        G.vertices[n].firstB = p2;
    }
}

void UDGprint(TGraph G)
{
    BNode *p;
    for(int i = 0; i < G.DNum; ++i)
    {
        cout<<G.vertices[i].data;
        p = G.vertices[i].firstB;
        while(p)
        {
            cout<<"->";
            cout<<p->pointPosite;
            p = p->nextB;
        }
        cout<<endl;
    }
}


int LocateVex(TGraph G, string v)
{
    for(int i = 0; i < G.DNum; ++i)
    {
        if(v == G.vertices[i].data)
        {
            return i;
        }
    }
    return -1;
}

bool visited[MAX];

void deepTravel(TGraph G, string v)
{
    int b,w;
    BNode *p;
    cout<<v<<" ";
    b = LocateVex(G, v);
    visited[b] = true;  //访问第b个顶点，标志为true
    p = G.vertices[b].firstB;    //p指向v的边链表的第一个边结点
    while(p != NULL)            //如果p不为空
    {
        w = p->pointPosite;     //w为v的第一个边结点
        if(!visited[w])         //若w未被访问 则继续递归
        {
            string a;
            for(int i = 0; i < G.DNum; ++i)
            {
                if(w == i)
                {
                    a = G.vertices[i].data;
                }
            }
            deepTravel(G, a);
        }
        p = p->nextB;       //否则p指向下一个v的边结点
    }
}

void breadthTravel(TGraph G, string v)
{
    BNode *p;
    int l;
    string e;
    int b = LocateVex(G, v);
    SqQueue Q;
    InitQueue(Q);
    for(int i = 0; i < G.DNum; i++)
        visited[i] = false;
    if(!visited[b])
    {
        visited[b] = true;
        cout<<v<<" ";
        EnQueue(Q, v);
        while(!Empty(Q))
        {
            string s = DeQueue(Q, e);
            int u = LocateVex(G, s);
            p = G.vertices[u].firstB;
            while(p)
            {
                l = p->pointPosite;
                if(!visited[l])
                {
                    visited[l] = true;
                    cout<<G.vertices[l].data<<" ";
                    EnQueue(Q, G.vertices[l].data);
                }
                p = p -> nextB;
            }
        }
    }
}

int main()
{
    string ch;
    TGraph G;
    CreateUDG(G);
    cout<<"建立的邻接表如下： "<<endl;
    UDGprint(G);
    cout<<"请输入遍历开始的结点：";
    cin >> ch;
    cout<<"深度遍历序列为： ";
    deepTravel(G, ch);
    cout<<"\n广度遍历序列为： ";
    breadthTravel(G, ch);
    return 0;
}

rnm4000

55248307

特立尼达

好

tianlai7266

tianlai7266

何世昭

nb

aa623848618

优秀啊，老板