《数据结构》实验报告六:图的表示与遍历

这篇具有很好参考价值的文章主要介绍了《数据结构》实验报告六:图的表示与遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、实验目的

1、掌握图的邻接矩阵邻接表表示

2、掌握图的深度优先广度优先搜索方法

3、理解图的应用方法

二、实验预习 

说明以下概念

1、深度优先搜索遍历:

       一种图的遍历方式:从图中任意一个起始顶点 V 出发,接着访问它的任意一个邻接顶点 W1 ;再从 W1 出发,访问与 W1 邻接的、但还未被访问过的顶点 W2 ;然后再从 W2 出发,进行相同的的访问……直至到达一个所有的邻接顶点都已经被访问过的顶点 U 。

       接着,从顶点 U 往前退回一步,回到前一次访问过的顶点,判断该顶点是否有其它没有被访问过的邻接顶点:

       如果有,则访问此邻接顶点,并再次从此顶点出发,进行与之前相同的访问;

       如果没有,则继续往前退回一步,再次进行判断。

       重复以上过程,直到连通图中所有顶点都被访问过为止。(图的深度优先搜索遍历类似树的先序遍历)

2、广度优先搜索遍历:

       一种图的遍历方式:从图中任意一个起始顶点 V 出发,依次访问该顶点的所有邻接顶点 V1、V2……Vn。所有邻接顶点访问完成后,再按照这些邻接顶点被访问的先后次序 依次访问与其相邻接所有未被访问过的顶点。重复此过程,直至所有顶点均被访问为止。(图的广度优先搜索遍历类似树的层序遍历)

3、拓扑排序:

       拓扑排序通常是针对一种特殊的图——有向无环图(DAG),拓扑排序可以将图中的所有顶点排列成一个线性序列,该线性序列满足以下要求:

       对于图 G 中任意一对顶点 u 和 v ,若弧 <u,v> ∈ E(G),则 u 在该线性序列中一定会出现在 v 之前。

4、最小生成树:

       以无向网为例,在该网的所有生成树中,使得各边的权值之和最小的生成树即该网的最小生成树,也称为最小代价生成树。

       构造最小生成树的方法有:Prim算法、Kruskal算法。

5、最短路径:

       在网图中:从某一顶点A(源点)到另一个顶点B(终点)的所有路径中,各边权值之和最小的路径即为最短路径。

       在非网图中:从某一顶点A(源点)到另一个顶点B(终点)的所有路径中,边数之和最小的路径即为最短路径。

       找出最短路径的方法有:Dijkstra算法、Floyd算法。

三、实验内容和要求

1、阅读并运行下面程序,根据输入写出运行结果。

#include<stdio.h>

#define N 20       /*图中顶点数目的最大值为N*/
#define TRUE 1
#define FALSE 0

int visited[N];    /*访问标识数组*/
typedef struct     /*队列的定义*/
{
    int data[N];
    int front,rear;
}queue;

typedef struct     /*定义图的邻接矩阵*/
{
    int vexnum,arcnum;        //图中顶点数目、边/弧的数目
    char vexs[N];             //一维数组:存储顶点信息
    int arcs[N][N];           //二维数组:存储顶点与顶点之间的关系
}graph;

void createGraph(graph *g);   /*建立一个无向图的邻接矩阵*/
void dfs(int i,graph *g);     /*从第i个顶点出发进行深度优先搜索*/
void tdfs(graph *g);          /*深度优先搜索整个图*/
void bfs(int k,graph *g);     /*从第k个顶点出发进行广度优先搜索*/
void tbfs(graph *g);          /*广度优先搜索整个图*/
void init_visit();            /*初始化访问标识数组*/

void createGraph(graph *g)    /*建立一个无向图的邻接矩阵*/
{
    int i,j;
    char v;
    g->vexnum = 0;
    g->arcnum = 0;
    i=0;
    printf("输入顶点序列(以#结束):\n");
    while((v=getchar()) != '#')
    {
        g->vexs[i] = v;        /*读入顶点信息*/
        i++;
    }
    g->vexnum = i;             /*顶点数目*/

    for(i=0;i<g->vexnum;i++)   /*邻接矩阵初始化*/
        for(j=0;j<g->vexnum;j++)
            g->arcs[i][j] = 0;

    printf("输入边的信息(以-1,…结束):\n");
    scanf("%d,%d",&i,&j);      /*读入边i,j*/
    while(i != -1)             /*读入i,j为-1时结束*/
    {
        g->arcs[i][j] = 1;
        g->arcs[j][i] = 1;
        scanf("%d,%d",&i,&j);
    }
}

void dfs(int i,graph *g)    /*从第i个顶点出发进行深度优先搜索*/
{
    int j;
    printf("%c",g->vexs[i]);
    visited[i] = TRUE;
    for(j=0;j<g->vexnum;j++)
        if((g->arcs[i][j]==1) && (!visited[j]))  //若第j个顶点与第i个顶点邻接且未被访问,则访问该顶点
            dfs(j,g);
}

void tdfs(graph *g)      /*深度优先搜索整个图*/
{
    int i;
    printf("\n从顶点%c开始深度优先搜索序列:",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i] != TRUE)
            dfs(i,g);
}

void bfs(int k,graph *g)  /*从第k个顶点出发进行广度优先搜索*/
{
    int i,j;
    queue qlist;
    queue *q;
    q = &qlist;
    q->rear = 0;
    q->front = 0;
    printf("%c",g->vexs[k]);   //访问第k个顶点
    visited[k] = TRUE;
    q->data[q->rear] = k;      //第k个顶点入队(这里是将顶点下标k入队)
    q->rear = (q->rear+1)%N;
    while(q->rear != q->front) //队列非空时
    {
        i = q->data[q->front]; //队头元素出队
        q->front = (q->front+1)%N;

        //访问出队顶点所有相邻接、未被访问过的顶点。并在访问后将其入队
        for(j=0;j<g->vexnum;j++)
            if((g->arcs[i][j]==1) && (!visited[j]))
            {
                printf("%c",g->vexs[j]);
                visited[j] = TRUE;
                q->data[q->rear] = j;
                q->rear =( q->rear+1)%N;
            }
    }
}

void tbfs(graph *g) /*广度优先搜索整个图*/
{
    int i;
    printf("\n从顶点%c开始广度优先搜索序列:",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i] != TRUE)
            bfs(i,g);
}

void init_visit()   /*初始化访问标识数组*/
{
    int i;
    for(i=0;i<N;i++)
        visited[i] = FALSE;
}

int main()
{
    graph ga;
    int i,j;
    createGraph(&ga);
    printf("无向图的邻接矩阵:\n");
    for(i=0;i<ga.vexnum;i++)
    {
        for(j=0;j<ga.vexnum;j++)
            printf("%3d",ga.arcs[i][j]);
        printf("\n");
    }
    init_visit();
    tdfs(&ga);
    init_visit();
    tbfs(&ga);
    return 0;
}

《数据结构》实验报告六:图的表示与遍历

  • 根据上图的结构验证实验,输入:

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

  • 运行结果: 

《数据结构》实验报告六:图的表示与遍历

  • 这里我对 tdfs 函数做了一点修改:
void tdfs(graph *g)      /*从图中各个顶点开始深度优先搜索整个图*/
{
    int i;
    for(i=0;i<g->vexnum;i++)
    {
        if(visited[i] != TRUE)
        {
            printf("\n从顶点%c开始深度优先搜索序列:",g->vexs[i]);
            dfs(i,g);
            printf("\n");
        }
        init_visit();  //每一轮遍历完成后需要初始化访问标识数组
    }
}
  • 同样的输入,运行结果:

《数据结构》实验报告六:图的表示与遍历

可以得到从不同的顶点出发进行DFS产生的搜索序列,同样的也可以对 tbfs 函数进行修改。

2、阅读并运行下面程序,补充拓扑排序算法。

#include<stdio.h>
#include<malloc.h>

#define N 20               /*图中顶点数目的最大值为N*/

typedef struct edgenode{   /*图的邻接表:邻接链表结点*/
    int adjvex;            /*顶点序号*/
    struct edgenode *next; /*下一个结点的指针*/
}edgenode;

typedef struct vnode{       /*图的邻接表:邻接表*/
    char data;              /*顶点信息*/
    int ind;                /*顶点入度*/
    struct edgenode *link;  /*指向邻接链表指针*/
}vnode;

void createGraph_list(vnode adjlist[],int *p);  /*建立有向图的邻接表*/
void topSort(vnode g[],int n);                  /*拓扑排序*/

void createGraph_list(vnode adjlist[],int *p){  /*建立有向图的邻接表(其中指针p返回顶点个数)*/
    int i,j,n,e;
    char v;
    edgenode *s;
    i=0;
    n=0;
    e=0;
    printf("输入顶点序列(以#结束):\n");
    while((v=getchar()) != '#')
    {
        adjlist[i].data = v;        /*读入顶点信息*/
        adjlist[i].link = NULL;     /*初始化邻接表指针*/
        adjlist[i].ind = 0;         /*初始化顶点入度*/
        i++;
    }
    n = i;   //图中顶点数目
    *p = n;  //通过p返回顶点个数

    /*建立邻接链表*/
    printf("\n请输入弧的信息(i=-1结束):i,j:\n");
    scanf("%d,%d",&i,&j);
    while(i != -1)
    {
        s = (struct edgenode*)malloc(sizeof(edgenode));
        s->adjvex = j;
        //使用头插法插入邻接结点
        s->next = adjlist[i].link;
        adjlist[i].link = s;
        adjlist[j].ind++;  /*顶点j的入度加1*/
        e++;
        scanf("%d,%d",&i,&j);
    }

    /*输出邻接链表*/
    printf("邻接表:\n顶点,入度:->邻接顶点序号");
    for(i=0;i<n;i++)
    {
        printf("\n%c,%d:",adjlist[i].data,adjlist[i].ind);
        s = adjlist[i].link;  //s指向顶点i的邻接链表结点
        while(s != NULL)
        {
            printf("->%d",s->adjvex);  //输出邻接链表结点中的顶点序号
            s = s->next;
        }
    }
}

void topSort(vnode g[],int n)  /*拓扑排序*/
{
    
}

int main()
{
    vnode adjlist[N];
    int n,*p;
    p = &n;  //n为图中顶点数
    createGraph_list(adjlist,p);
    printf("\n\n");
    topSort(adjlist,n);
    return 0;
}

拓扑排序算法代码:

//g[]为图的邻接表,n为图中顶点数
void topSort(vnode g[],int n)   /*拓扑排序*/
{
    printf("拓扑排序顶点序列:\n");
    int i,j,k,m = 0;
    int top = -1;  //初始化栈为空,栈顶指针top置为-1
    struct edgenode *p;

    //遍历图中所有顶点,将度为0的顶点都入栈
    for(i=0;i<n;i++)
    {
        if(0 == g[i].ind)
        {
            g[i].ind = top;   
            top = i;
        }
    }

    //栈非空
    while(-1 != top)
    {
        j = top;                
        printf("%c",g[j].data);  //输出栈顶顶点
        m++;                     //m为拓扑排序序列中的顶点数(可判断图中是否有环)
        top = g[j].ind;        //出栈

        //顶点j输出后还需修改邻接自j的顶点的入度(即删除顶点j和所有以它为弧尾的弧)
        p = g[j].link;           //p指向顶点j的第一个邻接结点
        while( p )
        {
            k = p->adjvex;       //k为邻接顶点序号
            g[k].ind--;          //邻接顶点入度-1

            //将入度为0的顶点入栈
            if(0 == g[k].ind)
            {
                g[k].ind = top;
                top = k;
            }
            p = p->next;         //p继续指向下一个邻接结点
        }
    }

    //如果拓扑序列中不包含图中所有顶点,则图中一定存在环
    if(m < n)
        printf("图中存在环");
}

这里的拓扑排序利用了栈,但是代码中并没有明确定义栈结构,而是采用了一种比较巧妙的方法,只通过一个栈顶指针 top 指示栈顶元素,通过修改 top 的值进行入栈/出栈操作。

  

比如在遍历图中所有顶点,并将度为0的顶点都入栈时,入栈操作是将入栈顶点的入度修改为前一位入栈顶点的序号(即栈顶顶点的序号),并将top置为入栈顶点的序号。(通过入度的指示构成了一个栈)

top = -1;

for(i=0;i<n;i++)
{
    if(0 == g[i].ind)     //度为0的顶点入栈
    {
        g[i].ind = top;   //将入栈顶点的入度置为栈顶顶点的序号(栈底顶点入度置为-1)
        top = i;             //将top置为入栈顶点的序号
    }
}

//循环结束时top=栈顶顶点的序号

而在出栈操作时将 top 置为栈顶顶点的入度,即指向下一位栈中元素。

top = g[j].ind;        //栈顶顶点出栈

  • 根据输入,输出有向图的拓扑排序序列。并画出有向图。输入: 

ABCDEF#

0,1

1,2

2,3

4,1

4,5

-1,-1

  • 该有向图应该如下图所示:

《数据结构》实验报告六:图的表示与遍历

  • 运行结果: 

《数据结构》实验报告六:图的表示与遍历

3、阅读并运行下面程序。 

【注】

以下代码和网上提供的实验代码有区别,老师提供代码的以及网上的大部分代码都有一点问题:

在求最短路径时,输出的最短路径长度正确,但是最短路径经过的顶点有问题。以下代码是在这些问题代码的基础上修改得到的。

#include<stdio.h>

#define N 20
#define TRUE
#define INF 32766       /*邻接矩阵中的无穷大元素*/
#define INFIN 32767     /*比无穷大元素大的数*/

typedef struct
{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}graph;                 /*图的邻接矩阵*/

void createGraph_w(graph *g,int flag);   /*建带权图的邻接矩阵*/
void prim(graph *g,int u);               /*Prim算法构造最小生成树*/
void dijkstra(graph g,int v);            /*dijkstra算法求单源最短路径*/
void showprim();                         /*prim算法演示*/
void showdij();                          /*dijkstra算法演示*/
void printPath(graph g,int startVex,int EndVex,int path[N][N]);
                                         /*输出两顶点间的最短路径*/

/*建带权图的邻接矩阵,若flag为1则为无向图,flag为0为有向图*/
void createGraph_w(graph *g,int flag)
{
    int i,j,w;
    char v;
    g->vexnum = 0;
    g->arcnum = 0;
    i = 0;
    printf("输入顶点序列(以#结束):\n");
    while((v=getchar()) != '#')
    {
        g->vexs[i] = v;          /*读入顶点信息*/
        i++;
    }
    g->vexnum = i;
    for(i=0;i<g->vexnum;i++)     /*邻接矩阵初始化*/
        for(j=0;j<g->vexnum;j++)
            g->arcs[i][j] = INF;
    printf("输入边/弧的信息(如果是有向图请注意弧头、弧尾顺序):i,j,weight\n");
    scanf("%d,%d,%d",&i,&j,&w);  /*读入边(i,j,w)*/
    while(-1 != i)               /*读入i为-1时结束*/
    {
        g->arcs[i][j] = w;
        if(1 == flag)
            g->arcs[j][i] = w;
        scanf("%d,%d,%d",&i,&j,&w);
    }
}

/*Prim算法构造图g的最小生成树(g为无向图,u为出发顶点)*/
void prim(graph *g,int u)
{
    int i,j,k,min;
    int lowcost[N];             //lowcost[i]为顶点i到最小生成树中所有顶点间的最小权值(lowcost[i]=0表示顶点i属于MST)
    int closest[N];             //closest[i]为最小生成树中所有顶点间到顶点i最近的一个顶点序号
    for(i=0;i<g->vexnum;i++)    /*求其他顶点到出发顶点u的权*/
    {
        lowcost[i] = g->arcs[u][i];
        closest[i] = u;
    }
    lowcost[u]=0;
    for(i=1;i<g->vexnum;i++)    /*循环求最小生成树中的各条边*/
    {
        min = INFIN;
        for(j=0;j<g->vexnum;j++) //找到不属于最小生成树,且到最小生成树中所有顶点间权值最小的顶点k
        {
            if(lowcost[j]!=0 && lowcost[j]<min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);  /*输出该边*/
        lowcost[k] = 0;           /*顶点k加入最小生成树*/

        for(j=0;j<g->vexnum;j++)  //每加入一个顶点,需更新不属于MST的顶点到MST中顶点的最小权值,以及对应的最近的顶点
        {
            if(g->arcs[k][j]!=0 && g->arcs[k][j]<lowcost[j])
            {
                lowcost[j] = g->arcs[k][j];
                closest[j] = k;
            }
        }
    }
}

/*输出图g中顶点startVex到EndVex的最短路径*/
void printPath(graph g,int startVex,int EndVex,int path[N][N])
{
    int stack[N],top = 0;    /*准备一个栈*/
    int flag[N];             /*输出路径顶点标志(1:已输出;0:未输出)*/
    int i,s,e;
    for(i=0;i<g.vexnum;i++)  //初始化flag[i]为0
        flag[i] = 0;
    s = startVex;
    e = EndVex;
    printf("%c",g.vexs[s]);
    flag[s] = 1;
    stack[top++] = e;  //终点e入栈

    while(top > 0)     /*寻找s到e的路径*/
    {
        for(i=0;i<g.vexnum;i++)   //遍历s到e的最短路径中经过的,且还未输出的顶点
        {
            if(1==path[e][i] && 0==flag[i])
            {
                if(g.arcs[s][i] != INF)   //s到i的最短路径就是s->i,不包含其它顶点
                {
                    printf("->%c(%d)",g.vexs[i],g.arcs[s][i]);
                    flag[i] = 1;
                    s = i;
                    e = stack[--top];  //出栈
                    break;
                }
                if(g.arcs[s][i]==INF && i!=e)   //s到i的最短路径包含其它顶点
                    stack[top++] = i;  //入栈
            }
        }
    }
    //判断终点e是否输出
    if(0 == flag[e])
    {
        printf("->%c(%d)",g.vexs[e],g.arcs[s][e]);
        flag[e] = 1;
    }
}

/*dijkstra算法求图g的单源最短路径,v为源点序号*/
void dijkstra(graph g,int v)
{
    int dist[N];        //dist[i]表示:源点v到顶点i的最短路径长度(初始化为INF)
    int s[N];           //s[i]表示:是否找到源点v到顶点i的最短路径(0:未找到;1:已找到)
    int path[N][N];     //path[i][j]表示:源点v到顶点i的最短路径是否经过顶点j(0:不经过;1:经过)
    int mindis;         //mindis表示:在所有还未找到最短路径的顶点中,dist[i]的最小值(即与源点最近的距离)
    int i,j,u,k;
    for(i=0;i<g.vexnum;i++)      /*初始化操作*/
    {
        dist[i] = g.arcs[v][i];
        s[i] = 0;
        for(j=0;j<g.vexnum;j++)
            path[i][j] = 0;
        //顶点v到顶点i有弧(即弧的权值小于INF),则源点v到顶点i的最短路径经过v、i
        if(g.arcs[v][i] < INF)
        {
            path[i][v] = 1;
            path[i][i] = 1;
        }
    }
    dist[v] = 0;  //自身到自身距离为0
    s[v] = 1;     //自身到自身没有最短路径
    for(i=1;i<g.vexnum;i++)
    {
        mindis = INFIN;
        for(j=0;j<g.vexnum;j++)   //遍历所有还未找到最短路径的顶点,找出dist[]值最小的顶点u,并更新mindis
        {
            if((0==s[j]) && (dist[j]<mindis))
            {
                u = j;
                mindis=dist[j];
            }
        }
        s[u]=1;   //顶点u的最短路径已找到

        //每找到一个顶点的最短路径,需判断加入其作为中间顶点后,其余未找到最短路径的顶点到源点距离是否减小,若减小则更新距离dist
        for(j=0;j<g.vexnum;j++)
        {
            if((s[j]==0) && (dist[u]+g.arcs[u][j]<dist[j]))
            {
                dist[j] = dist[u]+g.arcs[u][j]; //更新最短距离dist
                for(k=0;k<g.vexnum;k++)
                    path[j][k] = path[u][k];    //顶点u最短路径经过的所有顶点
                path[j][j] = 1;                 //顶点自身
                g.arcs[v][j] = INF;
            }
        }
    }
    //循环vexnum-1次后:
    //dist[i]的值就是通过dijkstra算法计算出的源点v到顶点i的最短路径长度
    //path[i][…]则记录了顶点i最短路径经过的所有顶点

    printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]);
    for(i=0;i<g.vexnum;i++)
    {
        printf("\n顶点%c->顶点%c:",g.vexs[v],g.vexs[i]);
        if(dist[i]==INF || dist[i]==0)
            printf("无路径");
        else
        {
            printf("最短路径长度=%d  ",dist[i]);
            printf("经过顶点:");
            //这里给printPath函数新添了一个参数path,以传入图g的path数组,不然会报错
            printPath(g,v,i,path);  /*输出v到i的路径*/
        }
    }
}

void showprim()    /*最小生成树prim算法演示*/
{
    graph ga;
    createGraph_w(&ga,1);
    printf("最小生成树:\n");
    prim(&ga,0);
}

void showdij()    /*dijstra算法演示*/
{
    graph ga;
    createGraph_w(&ga,0);
    dijkstra(ga,0);
}

int main()
{
    showprim();   /*prim算法演示*/
    getchar();
    showdij();    /*dijstra算法演示*/
    return 0;
}
  • 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图,求其最小生成树;输入的第二部分为有向图,求其最短路径。

一、最小生成树,输入:

ABCDEF#

0,1,6

0,2,1

0,3,5

1,2,5

1,4,3

2,3,5

2,4,6

2,5,4

3,5,2

4,5,6

-1,-1,-1

二、最短路径,输入:

ABCDEF#

0,2,10

0,5,100

0,4,30

1,2,5

2,3,50

3,4,20

3,5,10

4,3,20

4,5,60

-1,-1,-1

  • 运行结果:(并画出两个图)

《数据结构》实验报告六:图的表示与遍历

  • 第一个图

《数据结构》实验报告六:图的表示与遍历

  • 第二个图《数据结构》实验报告六:图的表示与遍历

一开始我是直接运行的老师提供的代码,运行结果如下:

求最小生成树是对的,但是求最短路径时出问题(网上大部分代码运行结果都如下图)

《数据结构》实验报告六:图的表示与遍历

所以不仅是让我们运行程序,还需要对这些代码进行修改才能正常工作。

可以对比一下出问题的代码,看看什么地方进行了修改,以及错误的原因。

  • 关于上面的代码,弄清楚其中各个数组代表的意义,算法的实现过程就比较清晰了

Prim算法构造最短生成树:

lowcost数组记录不属于最小生成树的顶点到属于最小生成树的顶点中的最小代价

  • lowcost[i]的值为顶点 i 到最小生成树中所有顶点间的最小权值
  • lowcost[i]=0:顶点 i 属于最小生成树

closest数组记录最小生成树中的所有顶点到其余顶点代价最小的一个

  • closest[i]的值为最小生成树中所有顶点间到顶点 i 最近的一个顶点的序号

dijkstra算法求最短路径:

dist数组记录源点到各个顶点的最短路径长度

  • dist[i]的值为源点 v 到顶点 i 的最短路径长度
  • dist[i]初始化为源点 v 到顶点 i 的弧的权值,之后再不断更新

s数组记录是否找到源点到各个顶点的最短路径

  • s[i]=0:未找到源点 v 到顶点 i 的最短路径
  • s[i]=1:找到源点 v 到顶点 i 的最短路径

path数组记录源点到各个顶点的最短路径是否包含其它顶点

  • path[i][j]=0:源点 v 到顶点 i 的最短路径不经过顶点 j
  • path[i][j]=1:源点 v 到顶点 i 的最短路径经过顶点 j

另外在printPath函数中输出最短路径经过的顶点时,需要注意:

不能直接按序号由小到大依次输出经过的顶点,那样输出的只是最短路径经过的顶点,而非正确的路径顺序。

g.arcs[s][i] != INF:s 到 i 的最短路径就是s->i,不包含其它顶点,可直接输出

g.arcs[s][i] == INF:s 到 i 的最短路径包含其它顶点,不可直接输出,暂时入栈保存文章来源地址https://www.toymoban.com/news/detail-463489.html

到了这里,关于《数据结构》实验报告六:图的表示与遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)
  • 数据结构 | 图的遍历

    使用邻接矩阵法存储图的信息,其中 一维矩阵 Vexs[] 存储节点信息 二维矩阵 Edges[][] 存储边的信息 一维矩阵 visited[] 记录当前节点是否被访问过,用于后面的遍历 本文所使用的图的结构如下: 对应的 Vexs[] 为:A,B,C,D,E,F(对应的数组下标从0到5) 对应的 Edges[][] 如下: 图的

    2024年02月04日
    浏览(40)
  • 数据结构--5.3图的遍历(广度优先遍历)

    广度优先遍历:         广度优先遍历(BreadthFirstSearch),又称为广度优先搜索,简称BFS。 要实现对图的广度遍历,我们可以利用队列来实现。  (参考队列)(上述为结构)

    2024年02月10日
    浏览(47)
  • 【数据结构】图的存储与遍历

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) 在有向图中,顶点对x, y是有序的,顶点对x,y称为顶点x到顶点y的一条边(弧),x, y和y, x是两条不同的边。 在无向图中,顶点对(x, y)是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,

    2024年02月22日
    浏览(46)
  • 【数据结构】图的定义,存储,遍历

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 🍔前言 🎁图的定义   🏳️‍🌈有向完全图 🏳️‍🌈无向完全图 🎁存储结构 🏳️‍🌈邻接矩阵  🎈代码

    2024年02月06日
    浏览(78)
  • 【数据结构】图的创建与遍历

    图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 线性表 :线性关系,由直接前驱和直接后继组成。 树 :层次关系,由父结点和孩子结点组成,每个结点最多有一个父结点(根

    2023年04月22日
    浏览(49)
  • 【数据结构】图的广度优先遍历

    广度优先遍历,类似于树的层次遍历,又是熟悉的队列实现。首先将第一个顶点添加到队列中,然后讲该顶点的所有邻接顶点都加入队列中,再将该顶点输出。如此重复直到遍历完整个图。 Q:队列,用于存放顶点。 front,rear:队头和队尾指针,用于入队和出队。 p:工作指针,用

    2024年02月05日
    浏览(49)
  • 数据结构 第六章 图——图的遍历

    在前面我们知道,树是一种非线性结构,为了方便它在计算机中的存储,对树进行遍历使它线性化。 而图同样也是一种非线性结构,但是图又是一种不同于树的多对多结构,所以在前面我们将其转换为了多个一对多的结构来描述它的存储结构。 图的遍历同树类似,也是从某

    2024年02月08日
    浏览(45)
  • 大话数据结构-图的深度优先遍历和广度优先遍历

      图的遍历分为深度优先遍历和广度优先遍历两种。   深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS,深度优先遍历,是指从某一个顶点开始,按照一定的规则,访问并记录下一个未访问顶点。对于非连通图,则是按连通分量,采用同一规则进行深度优

    2024年02月04日
    浏览(58)
  • (超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

            根据下图,编写代码实现图的深度优先遍历和广度优先遍历。          按照英文字母顺序,以邻接表为存储结构,实现图的深度优先和广度优先遍历。遍历的顺序从顶点a开始。 以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。   (1)从顶点a,

    2024年02月08日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包