精华内容
下载资源
问答
  • 图的深度优先遍历序列

    千次阅读 2015-07-18 10:24:13
    设V={0,1,2,……,n-1},图中结点又称为顶点(vertex),有向图(directed graph)指图中代表边偶对是有序,用(”<”u,v>)代表一条有向边(又称为弧),则u称为该边始点(尾),v称为边终点(头)。...
    • Description

    图(graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶对称为边(edge);E是G中边的有限集合。设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用(”<”u,v>)代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undirected graph)指图中代表边的偶对是无序的,在无向图中边(u,v )和(v,u)是同一条边。

    输入边构成无向图,求以顶点0为起点的深度优先遍历序列。

    • Input

    第一行为两个整数n、e,表示图顶点数和边数。以下e行每行两个整数,表示一条边的起点、终点,保证不重复、不失败。1≤n≤20,0≤e≤190

    • Output

    前面n行输出无向图的邻接矩阵,最后一行输出以顶点0为起点的深度优先遍历序列,对于任一起点,首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个空格。

    • Sample Input

    4 5
    0 1
    0 3
    1 2
    1 3
    2 3

    • Sample Output

    0 1 0 1
    1 0 1 1
    0 1 0 1
    1 1 1 0
    0 1 2 3

    #include<cstdio>
    #include<iostream>
    
    using namespace std;
    
    int map[21][21];
    int used[21];
    int n,e;
    
    void dfs(int v,int count)
    {
        int steak[210],i;
        int top=0;
        steak[top++]=v;
        printf("%d ",v);
        used[v]=1;
        while(top>0)
        {
            int x=steak[top-1];
            for(i=1;i<n;i++)
            {
                if(!used[i]&&map[x][i])
                {
                    steak[top++]=i;
                    printf("%d ",i);
                    used[i]=1;
                    count++;
                    break;
                }
            }
            if(i==n)
            top--;
        }
        if(count<n)
        {
            for(int i=1;i<n;i++)
                if(!used[i])
                    dfs(i,count);
        }
    }
    
    int main()
    {
       // freopen("in.txt","r",stdin);
        int x,y;
        scanf("%d%d",&n,&e);
        for(int i=0;i<e;i++)
        {
            scanf("%d%d",&x,&y);
            map[x][y]=map[y][x]=1;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                printf("%d ",map[i][j]);
            printf("\n");
        }
        dfs(0,0);
        printf("\n");
        return 0;
    }
    
    展开全文
  • 设V={0,1,2,……,n-1},图中结点又称为顶点(vertex),有向图(directed graph)指图中代表边偶对是有序,用<u,v>代表一条有向边(又称为弧),则u称为该边始点(尾),v称为边终点(头)。无向图...

    描述

     

    图(graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶对称为边(edge);E是G中边的有限集合。设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用<u,v>代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undirected graph)指图中代表边的偶对是无序的,在无向图中边(u,v )和(v,u)是同一条边。

    输入边构成无向图,求以顶点0为起点的深度优先遍历序列。

     

    输入

     

    第一行为两个整数ne,表示图顶点数和边数。以下e行每行两个整数,表示一条边的起点、终点,保证不重复、不失败。1n20,0e190

     

    输出

     

    前面n行输出无向图的邻接矩阵,最后一行输出以顶点0为起点的深度优先遍历序列,对于任一起点,首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个空格。

     

    样例输入

    4 5

    0 1

    0 3

    1 2

    1 3

    2 3

    样例输出

    0 1 0 1

    1 0 1 1

    0 1 0 1

    1 1 1 0

    0 1 2 3

    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    int a[20][20]={0};
    int n;
    bool *visit;
    void dfs(int k)
    {
        int i;
        visit[k]=true;
        cout<<k<<" ";
        for(i=0;i<n;i++)
        {
            if(a[k][i]&&!visit[i])
                dfs(i);
        }
        return;
    }
    int main()
    {
        int e;
        cin>>n>>e;
        int i,j;
        int x,y;
    
        for(i=0;i<e;i++)
        {
            cin>>x>>y;
            a[x][y]=a[y][x]=1;
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        visit=new bool[n];
        for(i=0;i<n;i++) visit[i]=false;
       // visit[0]=true;
        for(i=0;i<n;i++)
        {
            if(!visit[i])
                dfs(i);
        }
        cout<<endl;
        delete[]visit;
        return 0;
    }
    

      

    转载于:https://www.cnblogs.com/Rosanna/p/3436642.html

    展开全文
  • 给出一个无向图顶点和边的信息,输出这个无向图的深度优先遍历序列和广度优先遍历序列。从一个顶点出发如果2个以上的顶点可以访问时,我们约定先访问编号大的那个顶点。示例输入对应的图如下图所示: 输入 输入...

    **

    图的深度优先遍历与广度优先遍历

    **
    题目:
    给出一个无向图顶点和边的信息,输出这个无向图的深度优先遍历序列和广度优先遍历序列。从一个顶点出发如果有2个以上的顶点可以访问时,我们约定先访问编号大的那个顶点。示例输入对应的图如下图所示:

    输入
    输入的第1行有2个整数m和n。表示图g有m个顶点和n条边。
    第2行是m个以空格隔开的字符串,依次是图中第1个顶点的名字,第2个顶点的名字…第m个顶点的名字。
    此后还有n行,每行由2个字符串构成,分别是构成图中1条边的两个顶点。我们约定不会有重边。
    输出
    输出有2行。
    第1行是从第1个顶点出发对图g做深度优先遍历得到的顶点序列。
    第2行是从第1个顶点出发对图g做广度优先遍历得到的顶点序列。
    样例输入

    8 9
    v1 v2 v3 v4 v5 v6 v7 v8
    v1 v2
    v1 v3
    v1 v6
    v2 v3
    v2 v4
    v3 v4
    v4 v6
    v5 v6
    v7 v8
    

    样例输出

    v1 v6 v5 v4 v3 v2 v7 v8
    v1 v6 v3 v2 v5 v4 v7 v8
    

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    int mapp[1000][1000],a[1000],book[1000],path[1000];
    int m,n,idx;
    void dfs(int x){
    	if(book[x]){
    		return;
    	}
    	book[x]=1;
    	path[++idx]=x;
    	for(int i=m;i>=1;i--){
    		if(mapp[x][i])dfs(i);
    	}
    }
    void bfs(int x){
    	if(book[x])return;
    	queue<int> q;
    	q.push(a[x]);
    	path[++idx]=x;
    	book[x]=1;
    	while(!q.empty()){
    		for(int i=m;i>=1;i--){
    			if(!book[i]&&mapp[q.front()][i]){
    				path[++idx]=i;
    				book[i]=1;
    				q.push(i);
    			}
    		}
    		q.pop();
    	}
    }
    int main(){
    	cin>>m>>n;
    	char gg;
    	for(int i=1;i<=m;i++){
    		cin>>gg>>a[i]; 
    	}
    	for(int i=1;i<=n;i++){
    		int x,y;
    		cin>>gg>>x>>gg>>y;
    		mapp[x][y]=mapp[y][x]=1;
    	}
    	for(int i=1;i<=m;i++){
    		dfs(i);
    	}
    	for(int i=1;i<=idx;i++){
    		cout<<"v"<<path[i]<<" ";
    	}
    	idx=0;
    	memset(path,0,sizeof(path));
    	memset(book,0,sizeof(book));
    	cout<<endl;
    	for(int i=1;i<=m;i++){
    		bfs(i);
    	}
    	for(int i=1;i<=idx;i++){
    		cout<<"v"<<path[i]<<" ";
    	}
    	return 0;
    }
    
    展开全文
  • 求连通图的所有深度优先遍历序列

    千次阅读 2019-02-28 09:52:13
    如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。 ...

    在图论中,连通图基于连通的概念。在一个无向图G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

                                                                       图1-连通图

    连通分量:无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

    强连通图:有向图G=(V,E) 中,若对于V中任意两个不同的顶点 x和 y,都存在从x到 y以及从 y到 x的路径,则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连分量。

    单向连通图:设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。

    弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

    /**
    *    实验题目:
    *        求连通图的所有深度优先遍历序列
    *    实验目的:
    *        领会图的深度优先遍历算法
    *    实验内容:
    *        编写程序,假设一个连通图采用邻接表存储,输出它的所有深度优先
    *    遍历序列。
    */

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

    #define INF     32767               //定义∞
    #define MAXV    100                 //最大顶点个数

    typedef char InfoType;
    /*-------------------------以下定义邻接矩阵类型---------------------------*/
    typedef struct
    {
        int no;                         //顶点编号
        InfoType info;                  //顶点信息
    }VertexType;                        //顶点类型

    typedef struct
    {
        int edges[MAXV][MAXV];          //邻接矩阵数组(用一个二维数组存放顶点间关系(边或弧)的数据)
        int n;                          //顶点数
        int e;                          //边数
        VertexType vexs[MAXV];          //存放顶点信息(用一个一维数组存放图中所有顶点数据)
    }MatGraph;                          //完整的图邻接矩阵类型

    //邻接表表示法-将每个顶点的邻接点串成一个单链表
    /*-----------以下定义邻接表类型--------------*/
    typedef struct ArcNode
    {
        int adjvex;                     //该边的邻接点编号
        struct ArcNode *nextarc;        //指向下一条边的指针
        int weight;                     //该边的相关信息,如权值(用整型表示)
    }ArcNode;                           //边结点类型

    typedef struct VNode
    {
        InfoType info;                  //顶点其他信息
        int cnt;                        //存放顶点入度,仅用于拓扑排序
        ArcNode *firstarc;              //指向第一条边
    }VNode;                             //邻接表结点类型

    typedef struct
    {
        VNode adjlist[MAXV];            //邻接表头结点数组
        int n;                          //图中顶点数
        int e;                          //图中边数
    }AdjGraph;                          //完整的图邻接表类型

    /*-------------------------邻接矩阵的基本运算算法---------------------------*/
    /*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g--------------------*/
    void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;

        g.n = n;
        g.e = e;
        for(i = 0; i < g.n; i++)
            for(j = 0; j < g.n; j++)
                g.edges[i][j] = A[i][j];
    }

    /*------------输出邻接矩阵g--------------------*/
    void DispMat(MatGraph g)
    {
        int i, j;

        for(i = 0; i < g.n; i++)
        {
            for(j = 0; j < g.n; j++)
            {
                if(g.edges[i][j] != INF)
                    printf("%4d", g.edges[i][j]);
                else
                    printf("%4s", "∞");
            }
            printf("\n");
        }
    }

    /*-------------------------邻接表的基本运算算法---------------------------*/
    /*-------------------由边数组A、顶点数n和边数e创建图的邻接表G--------------------*/
    void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;
        ArcNode *p;

        G = (AdjGraph *)malloc(sizeof(AdjGraph));
        for(i = 0; i < n; i++)                              //给邻接表中所有头结点的指针域置初值NULL
        {
            G->adjlist[i].firstarc = NULL;
        }

        for(i = 0; i < n; i++)                              //检查邻接矩阵中的每个元素
        {
            for(j = n - 1; j >= 0; j--)
            {
                if(A[i][j] != 0 && A[i][j] != INF)          //存在一条边
                {
                    p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
                    p->adjvex = j;                          //邻接点编号
                    p->weight = A[i][j];                    //边的权重
                    p->nextarc = G->adjlist[i].firstarc;    //采用头插法插入结点p
                    G->adjlist[i].firstarc = p;
                }
            }
        }
        G->n = n;
        G->e = e;
    }

    /*-------------------输出邻接表G--------------------*/
    void DispAdj(AdjGraph *G)
    {
        ArcNode *p;

        for(int i = 0; i < G->n; i++)
        {
            p = G->adjlist[i].firstarc;
            printf("%d: ", i);
            while(p != NULL)
            {
                printf("%3d[%d]->", p->adjvex, p->weight);  //邻接点编号[权重]
                p = p->nextarc;
            }
            printf("∧\n");
        }
    }

    /*-------------------销毁图的邻接表G--------------------*/
    void DestroyAdj(AdjGraph *&G)
    {
        ArcNode *pre, *p;

        for(int i = 0; i < G->n; i++)
        {
            pre = G->adjlist[i].firstarc;                   //pre指向第i个单链表的首结点
            if(pre != NULL)
            {
                p = pre->nextarc;
                while(p != NULL)                            //释放第i个单链表的所有边结点
                {
                    free(pre);
                    pre = p;
                    p = p->nextarc;
                }
                free(pre);
            }
        }
        free(G);                                            //释放头结点数组
    }

    int visited[MAXV];                                  //全局数组

    /**
    *   功能:
    *       求图G中从顶点v出发的所有深度优先遍历序列
    *   @param path:记录访问过的顶点序列
    *   @param d:记录访问的顶点数,其初值为0,当d=n时输出path中的访问序列
    *
    */
    void DFSALL(AdjGraph *G, int v, int path[], int d)
    {
        ArcNode *p;

        visited[v] = 1;                                         //置已访问标记
        path[d] = v;
        d++;
        if(d == G->n)                                           //如果已访问所有顶点,则输出访问序列
        {
            for(int k = 0; k < d; k++)
                printf("%3d", path[k]);
            printf("\n");
        }
        p = G->adjlist[v].firstarc;                             //p指向顶点v的第一个相邻点
        while(p != NULL)
        {
            if(visited[p->adjvex] == 0)                         //若p->adjvex顶点未访问,递归访问它
            {
                DFSALL(G, p->adjvex, path, d);
            }
            p = p->nextarc;                                     //找顶点v的下一个相邻点
        }
        visited[v] = 0;
    }


    int main(void)
    {
        AdjGraph *G;
        int n = 5;                                  //图顶点数
        int e = 8;                                  //图边数
        int A[MAXV][MAXV] = {
            {0, 1, 0, 1, 1}, {1, 0, 1, 1, 0},
            {0, 1, 0, 1, 1}, {1, 1, 1, 0, 1},
            {1, 0, 1, 1, 0}
        };

        CreateAdj(G, A, n, e);
        printf("图的邻接表:\n");
        DispAdj(G);
        int path[MAXV];
        int v = 1;
        printf("从顶点%d出发的所有深度优先序列:\n", v);
        DFSALL(G, v, path, 0);
        printf("销毁图的邻接表\n");
        DestroyAdj(G);

        return 0;
    }
    输出结果:

    图G的邻接表:
    0:   1[1]->  3[1]->  4[1]->∧
    1:   0[1]->  2[1]->  3[1]->∧
    2:   1[1]->  3[1]->  4[1]->∧
    3:   0[1]->  1[1]->  2[1]->  4[1]->∧
    4:   0[1]->  2[1]->  3[1]->∧
    从顶点1出发的所有深度优先序列:
      1  0  3  2  4
      1  0  3  4  2
      1  0  4  2  3
      1  0  4  3  2
      1  2  3  0  4
      1  2  3  4  0
      1  2  4  0  3
      1  2  4  3  0
      1  3  0  4  2
      1  3  2  4  0
    销毁图的邻接表

    展开全文
  • 基于邻接表存储有向图的深度优先遍历 试编写程序,以邻接表位存储结构实现无向图的广度优先遍历操作。 (1)以图的邻接表表示为存储结构建立有向图。 (2)编写有向图的深度优先遍历函数。 (3)以用户指定的顶点为...
  • 向图_深度优先遍历

    千次阅读 2014-11-02 19:36:44
    [练习]输入边构成无向图,求以顶点0为起点的深度...前面n行输出无向图的邻接矩阵,最后一行输出以顶点0为起点的深度优先遍历序列,对于任一起点,首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个
  • 给出一个无向图顶点和边的信息,输出这个无向图的深度优先遍历序列和广度优先遍历序列。从一个顶点出发如果2个以上的顶点可以访问时,我们约定先访问编号大的那个顶点。示例输入对应的图如下图所示: 输入 ...
  • 图的深度优先遍历 如果有用的话,请点个赞哦???? 问题描述 已知无向图的邻接矩阵,以该...第一行输出为无向图的深度优先搜索遍历序列,输出为顶点编号,顶点编号之间用空格隔开;第二行为无向图的连通分量的个数。
  • /*(1)输入一组顶点,建立有向图的邻接表,进行DFS(深度优先遍历)和BFS(广度优先遍历)。 写出深度优先遍历的递归和非递归算法。 (2)根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序...
  • 图深度优先遍历 编写程序对给定的 有向图(不一定连通) 进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,...输出为一行整数,每个整数后一个空格,即该有向图的深度优先遍历结点序列
  • 1. 输入一个有向图的顶点数 n 和边数 e,设图中顶点编号为 1 到 n, 1)依次输入每个边的起点和终点,创建该图的邻接表; 2)边链表中边结点编号按照从小到大的顺序...自 v 开始的深度优先遍历序列和广度优先遍历序列
  • 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [实现提示] 设图的结点不超过30个,每个结点用一个编号表示(如果...
  • 图深度优先遍历

    2020-12-03 16:15:46
    编写程序对给定的有向图(不一定连通)进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,如果...输出为一行整数,每个整数后一个空格,即该有向图的深度优先遍历结点序列。 输入样
  • 说明: 由于本人能力有限,本文内容难免错误之处,希望各位同学不吝赐教,共同进步! 题目:图的深度优先遍历 问题描述: ...第一行输出为无向图的深度优先搜索遍历序列,输出为顶点编号,顶点编号之间用
  • 任务: 给定一个有向图,实现图的深度优先, 广度优先遍历算法,并输出相关结果。 功能要求: 输入图的基本信息,并建立图存储结构(有相应提示),输出遍历序列。 相关具体实验图形如下: 有向图信息: 顶点6个...
  • 写出附从每个顶点出发一次深度优先搜索遍历序列。 在纸上画出遍历过程和序列,提交截图,注意写上学号和姓名。 过程 从顶点A出发,访问顶点并标记为已访问 访问A邻接点,如果没有访问过,访问该顶点并标记为已...
  • 编写一个程序,输出下面带权有向图的邻接表,并根据该邻接表,实现图的遍历运算,具体要求如下: (1)从顶点0开始的深度优先遍历序列(递归算法) (2)从顶点0开始的深度优先遍历序列(非递归算法) (3)从顶点0开始的广度...
  • 编写程序对给定的有向图(不一定连通)进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,如果...输出为一行整数,每个整数后一个空格,即该有向图的深度优先遍历结点序列。 输入样例1:
  • 读入一个邻接矩阵存储的无向图,输出它的深度优先遍历序列。 输入格式 第1行1个整数n,表示图中的顶点数,2<=n<=100 接下来的n行是一个n*n的邻接矩阵,a[i][j]=1表示顶点i和顶点j之间直接边相连,a[i][j]=...
  • 编写程序对给定的有向图(不一定连通)进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,...输出为一行整数,每个整数后一个空格,即该有向图的深度优先遍历结点序列。 输入格式: 3
  • 深度优先遍历

    2014-09-24 14:57:24
    遍历规则:首先访问初始点vi ,并将其标记为已访问过,然后从vi 的任一未被访问过的邻接点(有向图的入边邻接点除外,下同)w出发进行深度优先遍历,当vi的所有邻接点均被访问过时,则回退到已被访问的顶点序列中...
  • 本实验实现有向图的邻接表存储,并输出, 以及该有向图的深度优先遍历序列。 2 实验内容 建立如图所示的有向图G的邻接表,并输出。 输出深度优先遍历序列 Code: #include<stdio.h> #include<stdlib.h&...
  • 题目(阿里笔试题):以下是一个有向图,我们从节点B开始进行深度优先遍历(DFS),那么以下5个序列中,所有正确DFS序列是__。 解析:深度优先遍历是指优先探索完一条通路后才返回倒数第二个节点继续探索另一条...
  • 设有一连通有向图,其顶点值为字符型并假设各值互不相等,采用邻接表表示法存储表示,求其广度优先遍历序列。  Input 有多组测试数据,每组数据第一行为两个整数n和e,表示n个顶点和e条边(0&lt;n&lt;...
  • 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 三、实现提示 设图的结点不超过30个,每个结点用一个编号表示(如果...
  • ②依次从V0各个未被访问邻接点出发深度优先遍历图, 直至中所有和V0路径相通顶点都被访问到。 ③若中还有顶点未被访问(非连通),另选中一个未被访问顶点作起始点,重复上述过程,直至中所有顶点...
  • (2) 从第一个顶点出发,求一个深度优先遍历序列; (3) 从第一个顶点顶点出发,求一个广度优先遍历序列。 注意:以用户输入各个顶点顺序为顶点序号。 在深度和广度优先遍历中,优先选择序号小顶点。 输入 第一行...
  • (2)输出有向图的邻接表 (3)对有向图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。 有向图如下所示: #include<iostream> #include<string.h> #include<iomanip> using ...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 171
精华内容 68
关键字:

有向图的深度优先遍历序列