精华内容
下载资源
问答
  • 本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • C++实现,数据结构,的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • 深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历,直至中所有和v有路径相通的...
  • 数据结构中的结构,其中最重要的两个遍历算法——深度优先遍历与广度优先遍历
  • ALGraph.h#pragma once#include "Queue.h"/************************************************************************//* 的邻接表存储结构 *//*********************...

    ALGraph.h

    #pragma once

    #include "Queue.h"

    /************************************************************************/

    /* 图的邻接表存储结构 */

    /************************************************************************/

    #define MaxVertexNum 100

    #define QueueSize 30

    bool visited[MaxVertexNum];

    typedef char VertexType;

    typedef int EdgeType;

    typedef struct node //边表结点

    {

    int adjvex; //邻接点域

    struct node* next; //域链

    //若是要表示边上的权,则应增加一个数据域

    }EdgeNode;

    typedef struct vnode //顶点边结点

    {

    VertexType vertex; //顶点域

    EdgeNode* firstedge;//边表头指针

    }VertexNode;

    typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型

    typedef struct

    {

    AdjList adjlist; //邻接表

    int n;//图中当前顶点数

    int e;//图中当前边数

    }ALGraph; //对于简单的应用,无须定义此类型,可直接使用AdjList类型

    ALGraph* initALGraph();

    bool DFS(ALGraph* a, int i);

    bool DFSTraverseM(ALGraph* a);

    bool BFSTraverseM(ALGraph* a);

    bool BFS(ALGraph* a, int i);

    ALGraph.c

    #include "ALGraph.h"

    #include

    #include

    ALGraph* initALGraph()

    {

    ALGraph* a = NULL;

    EdgeNode* e = NULL;

    int i, j, k;

    char v1, v2;

    printf("请输入顶点数和边数(输入格式为:顶点数,边数): ");

    scanf("%d,%d", &i, &j);

    if(i<0 || j<0)

    return NULL;

    a = (ALGraph*)malloc(sizeof(ALGraph));

    if(a == NULL)

    return NULL;

    a->n = i;

    a->e = j;

    for(i=0; in; i++)

    {

    printf("请输入顶点信息 每个顶点以回车作为结束: ");

    fflush(stdin);

    scanf("%c",&(a->adjlist[i].vertex)); // 读入顶点信息

    a->adjlist[i].firstedge=NULL; // 点的边表头指针设为空

    }

    for(k=0; ke; k++)

    {

    printf("请输入边的信息(输入格式为:i,j): ");

    fflush(stdin);

    scanf("%c,%c", &v1, &v2);

    for(i=0; v1!=a->adjlist[i].vertex; i++);//找到顶点对应的存储序号

    for(j=0; v2!=a->adjlist[j].vertex; j++);//找到顶点对应的存储序号

    e = (EdgeNode*)malloc(sizeof(EdgeNode));

    e->adjvex = i;

    e->next = a->adjlist[j].firstedge;

    a->adjlist[j].firstedge = e;

    e = (EdgeNode*)malloc(sizeof(EdgeNode));

    e->adjvex = j;

    e->next = a->adjlist[i].firstedge;

    a->adjlist[i].firstedge = e;

    }

    return a;

    }

    /************************************************************************/

    /* 深度优先遍历 */

    /************************************************************************/

    bool DFS(ALGraph* a, int i)

    {

    if(a == NULL)

    return FALSE;

    printf("DFS: node %c:/n", a->adjlist[i].vertex);

    visited[i] = TRUE;

    i = a->adjlist[i].firstedge->adjvex;

    if(!visited[i])

    DFS(a, i);

    return TRUE;

    }

    bool DFSTraverseM(ALGraph* a)

    {

    int i;

    if(a == NULL)

    return FALSE;

    for(i=0; in; i++)

    visited[i] = FALSE;

    for(i=0; in; i++)

    if(!visited[i])

    DFS(a, i);

    return TRUE;

    }

    /************************************************************************/

    /* 广度优先遍历(递归实现) */

    /************************************************************************/

    bool BFS(ALGraph* a, int i)

    {

    int j, k;

    Queue *q = NULL;

    EdgeNode *e = NULL;

    if(a == NULL)

    return FALSE;

    q = initQueue();

    if(!visited[i])

    {

    printf("BFS: node %c/n", a->adjlist[i].vertex);

    visited[i] = TRUE;

    }

    j = a->adjlist[i].firstedge->adjvex;

    e = a->adjlist[i].firstedge->next;

    if(!visited[j])

    {

    enQueue(q, j);

    while(e)

    {

    k = e->adjvex;

    if(!visited[k])

    {

    enQueue(q, e->adjvex);

    printf("BFS: node %c/n", a->adjlist[k].vertex);

    visited[k] = TRUE;

    }

    e = e->next;

    }

    }

    while(q->size != 0)

    {

    j = deQueue(q);

    BFS(a, j);

    }

    }

    bool BFSTraverseM(ALGraph* a)

    {

    int i;

    if(a == NULL)

    return FALSE;

    for(i=0; in; i++)

    visited[i] = FALSE;

    for(i=0; in; i++)

    BFS(a, i);

    return TRUE;

    }

    Queue.h

    #pragma once

    typedef enum{FALSE, TRUE}bool;

    #define CAPACITY 10

    typedef int ElemType;

    typedef struct

    {

    int front;

    int rear;

    int size;

    ElemType data[CAPACITY];

    }Queue;

    Queue* initQueue();

    ElemType deQueue(Queue* q);

    bool enQueue(Queue* q, ElemType data);

    Queue.c

    #include "Queue.h"

    #include

    #include

    /************************************************************************/

    /* 初始化队列*/

    /************************************************************************/

    Queue* initQueue()

    {

    Queue *q = NULL;

    q = (Queue*)malloc(sizeof(Queue));

    if(q == NULL)

    return NULL;

    memset(q->data, 0, CAPACITY);

    q->front = q->rear = 0;

    q->size = 0;

    return q;

    }

    /************************************************************************/

    /* 队尾入队*/

    /************************************************************************/

    bool enQueue(Queue* q, ElemType data)

    {

    if(q == NULL)

    return FALSE;

    if(q->size == CAPACITY)

    return FALSE;

    q->data[q->rear] = data;

    q->rear = (q->rear+1) % CAPACITY;

    q->size++;

    return TRUE;

    }

    /************************************************************************/

    /* 队首出队*/

    /************************************************************************/

    ElemType deQueue(Queue* q)

    {

    ElemType res;

    if(q == NULL)

    exit(0);

    if(q->size == 0)

    return FALSE;

    res = q->data[q->front];

    q->front = (q->front+1) % CAPACITY;

    q->size--;

    return res;

    }

    main.c

    #include "ALGraph.h"

    int main()

    {

    ALGraph* a = initALGraph();

    BFSTraverseM(a);

    return 0;

    }

    展开全文
  • 以邻接表为存储结构,实现连通无向的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
  • 的深度优先和广度优先遍历,下载下来可直接运行。你值得拥有
  • } /************************************************************************/ /* 广度优先遍历(广度优先搜索) */ /************************************************************************/ bool BFSM...

    MGraph. h

    #pragma once

    #include "Queue.h"

    #define MaxVertexNum 100

    typedef char VertexType;

    typedef int EdgeType;

    typedef struct

    {

    VertexType vexs[MaxVertexNum];

    EdgeType edges[MaxVertexNum][MaxVertexNum];

    int n;//当前图顶点数

    int e;//当前边数

    }MGraph;

    bool visited[MaxVertexNum];

    MGraph* initMGraph();

    bool DFSTraverseM(MGraph* m);

    bool DFSM(MGraph* m, int i);

    bool BFSTraverseM(MGraph* m);

    bool BFSM(MGraph* m, int i);

    MGraph.c

    #include "MGraph.h"

    #include

    #include

    #include

    /************************************************************************/

    /* 初始化图*/

    /************************************************************************/

    MGraph* initMGraph()

    {

    MGraph* m = NULL;

    int i, j, k;

    char v1, v2;

    m = (MGraph*)malloc(sizeof(MGraph));

    memset(m->vexs, 0, MaxVertexNum);

    printf("please input the number of vertex and edges('v,e'): ");

    scanf("%d,%d", &i, &j);

    if(i<0 && j<0)

    {

    printf("error number");

    return NULL;

    }

    m->n = i;

    m->e = j;

    printf("please input the vertexs by order:/n");

    for(i=0; in; i++)

    {

    fflush(stdin);

    scanf("%c", &m->vexs[i]);

    }

    for(i=0; in; i++)

    for(j=0; jn; j++)

    m->edges[i][j] = 0;

    for(k=0; ke; k++)

    {

    printf("please input the edges by order('v1,v2'): ");

    fflush(stdin);

    scanf("%c,%c", &v1, &v2);

    for(i=0; v1!=m->vexs[i]; i++);

    for(j=0; v2!=m->vexs[j]; j++);

    m->edges[i][j] = 1;

    }

    return m;

    }

    /************************************************************************/

    /* 深度优先遍历(深度优先搜索) */

    /************************************************************************/

    bool DFSTraverseM(MGraph* m)

    {

    int i;

    if(m == NULL)

    return FALSE;

    for(i=0; in; i++)

    visited[i] = FALSE;

    for(i=0; in; i++)

    DFSM(m, i);

    return TRUE;

    }

    bool DFSM(MGraph* m, int i)

    {

    int j;

    if(m == NULL)

    return FALSE;

    if(visited[i] == FALSE)

    {

    printf("DFSM: node %c/n", m->vexs[i]);

    visited[i] = TRUE;

    }

    for(j=0; jn; j++)

    if(visited[j] == FALSE && m->edges[i][j] == 1)

    DFSM(m, j);

    return TRUE;

    }

    /************************************************************************/

    /* 广度优先遍历(广度优先搜索) */

    /************************************************************************/

    bool BFSM(MGraph* m, int i)

    {

    int j;

    Queue* q = NULL;

    if(m == NULL)

    return FALSE;

    visited[i] = TRUE;

    printf("BFSM: node %c/n", m->vexs[i]);

    q = initQueue();

    enQueue(q, i);

    while(q->size != 0)

    {

    i = deQueue(q);

    for(j=0; jn; j++)

    if(visited[i] == FALSE && m->edges[i][j] == 1)

    {

    enQueue(q, j);

    printf("BFSM: node %c/n", m->vexs[j]);

    visited[j] = TRUE;

    }

    }

    return TRUE;

    }

    bool BFSTraverseM(MGraph* m)

    {

    Queue* q = NULL;

    int i;

    if(m == NULL)

    return FALSE;

    q = initQueue();

    for(i=0; in; i++)

    visited[i] = FALSE;

    for(i=0; in; i++)

    if(visited[i] == FALSE)

    BFSM(m, i);

    return TRUE;

    }

    Queue.h

    #pragma once

    typedef enum{TRUE, FALSE}bool;

    #define CAPACITY 10

    typedef int ElemType;

    typedef struct

    {

    int front;

    int rear;

    int size;

    ElemType data[CAPACITY];

    }Queue;

    Queue* initQueue();

    ElemType deQueue(Queue* q);

    bool enQueue(Queue* q, ElemType data);

    Queue.c

    #include "Queue.h"

    #include

    #include

    /************************************************************************/

    /* 初始化队列*/

    /************************************************************************/

    Queue* initQueue()

    {

    Queue *q = NULL;

    q = (Queue*)malloc(sizeof(Queue));

    if(q == NULL)

    return NULL;

    memset(q->data, 0, CAPACITY);

    q->front = q->rear = 0;

    q->size = 0;

    return q;

    }

    /************************************************************************/

    /* 队尾入队*/

    /************************************************************************/

    bool enQueue(Queue* q, ElemType data)

    {

    if(q == NULL)

    return FALSE;

    if(q->size == CAPACITY)

    return FALSE;

    q->data[q->rear] = data;

    q->rear = (q->rear+1) % CAPACITY;

    q->size++;

    return TRUE;

    }

    /************************************************************************/

    /* 队首出队*/

    /************************************************************************/

    ElemType deQueue(Queue* q)

    {

    ElemType res;

    if(q == NULL)

    exit(0);

    if(q->size == 0)

    return FALSE;

    res = q->data[q->front];

    q->front = (q->front+1) % CAPACITY;

    q->size--;

    return res;

    }

    main.c

    #include "MGraph.h"

    #include "Queue.h"

    int main()

    {

    MGraph* m = initMGraph();

    DFSTraverseM(m);

    printf("/n");

    BFSTraverseM(m);

    return 0;

    }

    展开全文
  • 本资源是用C语言所写的,数据结构中图的创建及其相关的深度,广度遍历
  • 本程序方便的实现了的深度、广度优先遍历。是数据结构中的一部分,现与大家分享
  • #include #include #include #define N 5#define BACKSPACE() \{putchar(8); putchar(32); putchar(10);}int next_adj(int matrix[][N],int v,int u){int i;if(NULL == matrix)return ;for(i = u + 1;...

    #include

    #include

    #include

    #define N 5

    #define BACKSPACE() \

    {putchar(8); putchar(32); putchar(10);}

    int next_adj(int matrix[][N],int v,int u)

    {

    int i;

    if(NULL == matrix)

    return ;

    for(i = u + 1; i < N; i ++)

    if(matrix[v][i])

    return i;

    return -1;

    }

    int first_adj(int matrix[][N],int v)

    {

    int i;

    if (NULL == matrix )

    return -1;

    for(i = 0; i < N; i ++)

    if(matrix[v][i])

    return i;

    return -1;

    }

    void DFS(int matrix[][N],int v,int visited[])

    {

    int u;

    if(visited[v])

    return ;

    printf(" V%d,",v);

    visited[v] = 1;

    u = first_adj(matrix,v);

    while(u >= 0)

    {

    DFS(matrix,u,visited);

    u = next_adj(matrix,v,u);

    }

    return ;

    }

    int main()

    {

    int matrix[N][N] = {0};

    int visited[N] = {0};

    int v1 = -1,

    v2 = -1;

    while(1)

    {

    while(2 != scanf("%d,%d",&v1,&v2))

    getchar();

    if(v1 < 0 || v1 >= N || v2 < 0 || v1 >= N)

    continue;

    if(v1 == v2)

    break;

    matrix[v1][v2] = matrix[v2][v1] = 1;

    }

    for(v1 = 0; v1 < N; v1 ++)

    {

    printf("V%d: ",v1);

    for(v2 = 0; v2 < N; v2 ++)

    if(matrix[v1][v2])

    printf(" V%d,",v2);

    BACKSPACE();

    }

    v1 = 0;

    for(v1 = 0; v1 < N; v1++)

    DFS(matrix,v1,visited);

    BACKSPACE();

    return 0;

    }

    展开全文
  • //代码可直接运行#include #include #define maxsize 100typedef struct ArcNode {int num;struct ArcNode *next;}ArcNode;typedef struct VNode{ArcNode *firstarc;}VNode;typedef struct Graph {VNode VNodeList...

    //代码可直接运行

    #include

    #include

    #define maxsize 100

    typedef struct ArcNode {

    int num;

    struct ArcNode *next;

    }ArcNode;

    typedef struct VNode{

    ArcNode *firstarc;

    }VNode;

    typedef struct Graph {

    VNode VNodeList[maxsize];

    int n,e;

    }Graph;

    void bulidGraph(Graph *&g);

    int visitdfs[maxsize];

    void DFS(Graph *g ,int v);

    void dfs(Graph *g);

    int visit[maxsize];

    void bfs(Graph *g);

    void BFS(Graph *g ,int v);

    int main()

    {

    Graph *g;

    g=(Graph *) malloc(sizeof(Graph));

    bulidGraph(g);

    dfs(g);

    printf("\n");

    bfs(g);

    return 0;

    }

    void DFS(Graph *g ,int v){

    ArcNode *p=g->VNodeList[v].firstarc;

    visitdfs[v]=1;

    printf("%d",v);

    while (p!=NULL){

    if(visitdfs[p->num]==0)

    DFS(g,p->num);

    p=p->next;

    }

    }

    void dfs(Graph *g){

    for(int i=0;in;i++){

    if(visitdfs[i]==0)

    DFS(g,i);

    }

    }

    void BFS(Graph *g,int v){

    ArcNode *p ;

    int que [maxsize], top=0,rear=0;

    int j;

    printf("%d",v);

    visit[v]=1;

    rear =(rear+1)%maxsize;

    que[rear]=v;

    while(top!=rear){

    top =(top+1)%maxsize;

    j=que[top];

    p=g->VNodeList[j].firstarc;

    while (p!=NULL){

    if(visit[p->num]==0){

    printf("%d",p->num);

    visit[p->num]=1;

    rear=(rear+1)%maxsize;

    que[rear]=p->num;

    }

    p=p->next;

    }

    }

    }

    void bfs(Graph *g){

    for(int i=0;in;i++){

    if(visit[i]==0)

    BFS(g,i);

    }

    }

    void bulidGraph(Graph *&g){

    g->n=6;

    g->e=7;

    VNode v0,v1 ,v2, v3 ,v4 ,v5,v6;

    ArcNode *v01,*v03,*v04,*v14,*v12,*v20,*v32,*v56;

    v01=(ArcNode *) malloc(sizeof(ArcNode));

    v01->num=1;

    v03=(ArcNode *) malloc(sizeof(ArcNode));

    v03->num=3;

    v04=(ArcNode *) malloc(sizeof(ArcNode));

    v04->num=4;

    v14=(ArcNode *) malloc(sizeof(ArcNode));

    v14->num=4;

    v12=(ArcNode *) malloc(sizeof(ArcNode));

    v12->num=2;

    v20=(ArcNode *) malloc(sizeof(ArcNode));

    v20->num=0;

    v32=(ArcNode *) malloc(sizeof(ArcNode));

    v32->num=2;

    v56=(ArcNode *) malloc(sizeof(ArcNode));

    v56->num=6;

    v0.firstarc=v01;

    v1.firstarc=v14;

    v2.firstarc=v20;

    v3.firstarc=v32;

    v4.firstarc=NULL;

    v5.firstarc=v56;

    v6.firstarc=NULL;

    v01->next=v03;

    v03->next=v04;

    v14->next=v12;

    v32->next=NULL;

    v20->next=NULL;

    v12->next=NULL;

    v04->next=NULL;

    v56->next=NULL;

    g->VNodeList[0]=v0;

    g->VNodeList[1]=v1;

    g->VNodeList[2]=v2;

    g->VNodeList[3]=v3;

    g->VNodeList[4]=v4;

    g->VNodeList[5]=v5;

    g->VNodeList[6]=v6;

    }

    展开全文
  • C语言实现的深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2019-11-28 20:29:17
    的深度优先遍历和广度优先遍历图的遍历深度优先遍历广度优先遍历 的遍历 从给定中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着的边访问中所有顶点,使每个顶点仅被访问一次,这个过程称为的...
  • 邻接表存储深度优先广度优先遍历
  • 的深度优先遍历 的深度优先遍历参考 的深度优先遍历 参考 1、https://blog.csdn.net/todd911/article/details/9191481 2、https://blog.csdn.net/weixin_42109012/article/details/94199335
  • 对于一颗二叉树,深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。以上面二叉树为例,深度优先搜索的顺序为:ABDECFG。怎么实现这个顺序呢 ?深度优先搜索二叉树是先访问根...
  • 一、广度优先遍历BFS (一)树 vs ⼴度优先遍历(Breadth-First-Search, BFS)要点: ①、找到与⼀个顶点相邻的所有顶点 ②、标记哪些顶点被访问过 ③、需要⼀个辅助队列 FirstNeighbor(G,x):求G中顶点...
  • 一. 什么是深度优先遍历 深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至...广度优先遍历可定...
  • 深度优先遍历和广度优先遍历

    千次阅读 2021-10-27 15:16:43
    深度优先遍历和广度优先遍历是遍历当中所有顶点的两种方式。 深度优先遍历(DFS) 顾名思义,深度优先遍历就是找准一条路不停深入的搜索方法,当发现这条路走不通的时候就会回退到上一个探索的节点,如果上一个...
  • 注:此代码的实现需要以...深度优先遍历 深度优先遍历只需要依次访问结点即可,实现较为简单 //深度优先遍历 void DFS(LGraph* g,int *visit,int v) { printf("Node: %d\n",v); ENode* p = g->a[v]; visit[v]
  • 的深度优先遍历和广度优先遍历
  • 1. 深度优先遍历深度优先遍历(Depth First Search)的主要思想是:1、首先以一个未被访问过的顶点作为起始...1.1 无向的深度优先遍历图解以下"无向"为例: 对上无向进行深度优先遍历,从A开始:第1步:访问...
  • #include #include #include /** 邻接矩阵,深度优先遍历**/#define MAX 100#define INFINITY 65535// 结构体typedef struct {char vexs[MAX]; // 顶点的数组,顶点类型为了简单使用charint arc[MAX][MAX]; // 边...
  • 资源为数据结构之图形的两种存储形式的演示,包括邻接矩阵、邻接表,以及深度优先和广度优先遍历的两种实现,通过阅读可以提供对于更加深刻的掌握
  • 广度优先遍历-C语言 具体代码 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 #define INF 0 typedef struct Queue{ int data[MAXSIZE]; int front; int rear; int size; }Queue; ...
  • 头文件 #pragma warning( disable : 4996) #pragma once #ifndef _GRAPH_H_ #define _GRAPH_H_ #define MAX_VERTEX_NUM 20 ...//有向该值为1、无向该值为0 typedef int InfoType; typedef char VertexType; ...
  • 的引出:前面我们学了线性表和树。线性表局限于一个直接前驱和一个直接后继的关系;树也只能有一个直接前驱也就是父...2、广度优先遍历(Broad First Search)。 深度优先遍历思想:深度优先遍历是一种纵向切入..

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,032
精华内容 10,012
关键字:

图的广度优先遍历c