论坛 › 数据结构与算法 › 图的遍历：深度和广度

sampsom 发表于 2021-12-7 20:40:24

谢谢大佬，大佬真好！

rnm4000 发表于 2021-12-8 18:08:24

谢谢分享

AShengXz 发表于 2021-12-8 19:54:37

{:10_277:}

ohhohh 发表于 2021-12-9 08:34:31

{:10_254:}

ohhohh 发表于 2021-12-9 10:29:25

{:10_254:}

ohhohh 发表于 2021-12-9 16:53:18

{:10_279:}

日暮客愁新 发表于 2021-12-14 23:42:53

{:10_279:}

sunyt 发表于 2021-12-15 09:21:11

学习{:5_110:}

sunyt 发表于 2021-12-15 09:24:00

{:5_109:}

sunyt 发表于 2021-12-15 09:24:31

{:5_100:}

小bai学c 发表于 2021-12-16 09:56:10

{:10_254:}

ohhohh 发表于 2021-12-16 15:38:01

{:10_254:}

LDAJUN 发表于 2021-12-19 13:57:47

#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;//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;       
    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 = 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+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.data;    //输入顶点值
      G.vertices.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.firstB;   //头插法
      G.vertices.firstB = p1;
      p2 = new BNode;
      p2->pointPosite = m;
      p2->nextB = G.vertices.firstB;
      G.vertices.firstB = p2;
    }
}

void UDGprint(TGraph G)
{
    BNode *p;
    for(int i = 0; i < G.DNum; ++i)
    {
      cout<<G.vertices.data;
      p = G.vertices.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.data)
      {
            return i;
      }
    }
    return -1;
}

bool visited;

void deepTravel(TGraph G, string v)
{
    int b,w;
    BNode *p;
    cout<<v<<" ";
    b = LocateVex(G, v);
    visited = true;//访问第b个顶点，标志为true
    p = G.vertices.firstB;    //p指向v的边链表的第一个边结点
    while(p != NULL)            //如果p不为空
    {
      w = p->pointPosite;   //w为v的第一个边结点
      if(!visited)         //若w未被访问 则继续递归
      {
            string a;
            for(int i = 0; i < G.DNum; ++i)
            {
                if(w == i)
                {
                  a = G.vertices.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 = false;
    if(!visited)
    {
      visited = true;
      cout<<v<<" ";
      EnQueue(Q, v);
      while(!Empty(Q))
      {
            string s = DeQueue(Q, e);
            int u = LocateVex(G, s);
            p = G.vertices.firstB;
            while(p)
            {
                l = p->pointPosite;
                if(!visited)
                {
                  visited = true;
                  cout<<G.vertices.data<<" ";
                  EnQueue(Q, G.vertices.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 发表于 2021-12-19 17:37:49

{:10_266:}

55248307 发表于 2021-12-23 15:47:50

{:10_254:}

特立尼达 发表于 2021-12-24 10:21:34

好

tianlai7266 发表于 2021-12-24 22:13:32

{:10_254:}

tianlai7266 发表于 2021-12-24 22:16:00

{:10_254:}{:10_254:}

何世昭 发表于 2021-12-25 15:57:43

nb

aa623848618 发表于 2021-12-25 20:06:13

优秀啊，老板

查看完整版本: 图的遍历：深度和广度