精华内容
下载资源
问答
  • 图的深度优先遍历 如果有用的话,请点个赞哦???? 问题描述 已知无向图的邻接矩阵,以该矩阵为基础,给出深度优先搜索遍历序列,并且给出该无向图的连通分量的个数。在遍历时,当有多个点可选时,优先选择编号小...

    图的深度优先遍历

     如果有用的话,请点个赞哦👑
    
    • 问题描述

      已知无向图的邻接矩阵,以该矩阵为基础,给出深度优先搜索遍历序列,并且给出该无向图的连通分量的个数。在遍历时,当有多个点可选时,优先选择编号小的顶点。(即从顶点1开始进行遍历)

    • 输入格式

      第一行是1个正整数,为顶点个数n(n<100),顶点编号依次为1,2,…,n。后面是邻接矩阵,n行n列。

    • 输出格式

      共2行。第一行输出为无向图的深度优先搜索遍历序列,输出为顶点编号,顶点编号之间用空格隔开;第二行为无向图的连通分量的个数。

    • 样例输入

      6
      0 1 0 0 0 0
      1 0 0 0 1 0
      0 0 0 1 0 0
      0 0 1 0 0 0
      0 1 0 0 0 1
      0 0 0 0 1 0

    • 样例输入

      1 2 5 6 3 4
      2

    • 解题思路

      建立visit数组来区分结点是否已被访问,如果没有被访问,则访问他,修改visit,如果此节点存在邻接节点,递归访问此节点的下一个邻接节点;如果不存在邻接节点,说明此节点所在的连通分量已经被访问完,接下来按顺序判断下面的节点,并对为访问过的节点进行访问,直到所有的节点都被访问完。

    • 完整代码

    #include<stdio.h>
    int visit[100],n;
    int vexnum[100][100];
    void DFS(int i)
    {
      visit[i]=1;//访问过了
      printf("%d ",i+1);//输出节点
      for(int j=1;j<n;j++)//对i尚未访问过的邻接结点调用DFS
    	  if(visit[j]==0&&vexnum[i][j]!=0)
    		  DFS(j);
    }
    int main()
    {
    	int i,j,count;
    	count=0;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n;j++)
    			scanf("%d",&vexnum[i][j]);//邻接矩阵初始化
    		visit[i]=0;//访问标志数组初始化
    	}
    	for(i=0;i<n;i++)//将结点遍历一遍,遇到没有被访问过的结点,则访问它
    		if(!visit[i])//没有被访问过
    		{
    			/*从一个节点开始访问后,会访问到他所在连通分支的所有结点*/
    			DFS(i);//访问,当这个语句执行完,一个连通分支已经被访问完了
    			count++;//连通分量个数加一
    		}
    	printf("\n");
    	printf("%d",count);
    	return 0;
    }
    
    展开全文
  • 学完图的深度优先遍历算法后,如何将我们的逻辑思维通过代码来实现呢? 我们通过一维数组来存储图的顶点,通过邻接矩阵(二维数组)来存储边。

    前言

    学完图的深度优先遍历算法后,如何将我们的逻辑思维通过代码来实现呢?由于书中给的都是伪代码,所以这里大家实现了一下。


    一、图在计算机中如何存储呢?

    图跟其他数据结构类似也有两种存储结构那么就是,顺序存储结构和链式存储结构。

    1.顺序存储

    那么,现在有一个如下的图,需要采用顺序存储结构来存储到计算机中。是如何实现的呢?
    我们通过一维数组来存储图的顶点,通过邻接矩阵(二维数组)来存储边。 这样我们就可以通过计算机来描述这个图了。

    邻接矩阵:表示顶点间相邻关系的矩阵

    在这里插入图片描述

    一维数组

    通过一个一维数组来讲图中的ABCDE五个顶点依次存储到图中即可,如下图:
    在这里插入图片描述

    当然有时候我们顶点不仅仅只代表一个字母,或许还有更多的含义,那么我们就可以通过定义一个顶点结构体来描述顶点的信息。

    二维数组(邻接矩阵)

    图中二维数组AdjMatrix[0][1]=1 代表顶点AB之间存在边,AdjMatrix[2][0]=1 代表顶点CA之间也存在边。
    在这里插入图片描述

    代码实现顺序存储结构

    #include<stdio.h>
    #define MAX_VERTEX_NUM 20  //最大顶点数 
    /*
    *采用邻接表存储无向图 
    *无论哪种存储结构,都需要想办法来构造结构存储 顶点集和边集 
    */ 
    typedef struct{
    	char vexs[MAX_VERTEX_NUM]; //一维数组存储顶点集 
    	//int vexs[] = {1,2,3,4,5}; //根据顶点的类型来选择存储顶点的数组类型,复杂的顶点可以定义结构体来存储 
    	int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接表存储边集 
    	int vexnum,arcnum;  //图中顶点数和弧的数量 
    } MGraph; 
    

    2.链式存储结构

    见下一篇博客

    二、将图存入计算机中

    由图中我们可以看到一共有五个顶点(A、B、C、D、E)和六条边(AB 、AC 、CD 、CE 、DE 、BE )。

    1.存入顶点

    在这里插入图片描述
    在这里插入图片描述

    2.存入边

    在这里插入图片描述

    三、深度优先遍历

    我们以A顶点开始遍历那么遍历的一个结果为:【ABECD】
    在这里插入图片描述

    深度优先遍历代码实现

    #include<stdio.h>
    #define MAX_VERTEX_NUM 20  //最大顶点数 
    /*
    *采用邻接表存储无向图 
    *无论哪种存储结构,都需要想办法来构造结构存储 顶点集和边集 
    */ 
    typedef struct{
    	char vexs[MAX_VERTEX_NUM]; //一维数组存储顶点集 
    	//int vexs[] = {1,2,3,4,5}; //根据顶点的类型来选择存储顶点的数组类型,复杂的顶点可以定义结构体来存储 
    	int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接表存储边集 
    	int vexnum,arcnum;  //图中顶点数和弧的数量 
    } MGraph; 
    
    /*定位顶点在图中的位置*/
    int LocateVex(MGraph G,char vex){
    	for(int i=0;i<G.vexnum;i++){
    		if(G.vexs[i] == vex)
    			return i;
    	}
    	return -1;
    } 
    
    /*创建图*/
    void CreateGraph(MGraph &G) {
    	/*初始化图的基本信息*/
    	//输入图中顶点 
    	printf("请输入图中顶点数量:");
    	scanf("%d",&G.vexnum);
    	for(int i=0;i<G.vexnum;i++){
    		printf("请输入第%d个顶点:",i+1);
    		scanf(" %c",&G.vexs[i]);
    	}
    	//输入图中的边 
    	printf("请输入图中边的数量:");
    	scanf("%d",&G.arcnum);
    	//初始化邻接矩阵
    	for(int i=0;i<G.vexnum;i++){
    		for(int j=0;j<G.vexnum;j++){
    			G.AdjMatrix[i][j] = 0;  //初始化时顶点间都不存在边 
    		}
    	} 
    	//构造邻接矩阵
    	for(int k=0;k<G.arcnum;k++) {
    		char v1,v2;
    		printf("请输入第%d条边(如:AB):",k+1);
    		scanf(" %c%c",&v1,&v2);
    		int i = LocateVex(G,v1);  //获取边第一个顶点在图中的位置 
    		int j = LocateVex(G,v2);  //获取边第二个顶点在图中的位置 
    		G.AdjMatrix[i][j] = 1;  //存在边就设置为1 
    		G.AdjMatrix[j][i] = 1;  //由于是无向图所以相反反向也存在边 
    	}
    	printf("图创建成功!\n");	 
    }
    /*
    *G:不为空的图
    *v:需要访问的顶点 
    */
    void VisitFun(MGraph G,int v){
    	printf("%c ",G.vexs[v]);
    } 
    /*
    *G:不为空的图
    *v:其实访问的顶点 
    */
    void DFS(MGraph G,int *visited,int v){
    	visited[v] = 1;  //将访问的结点设置为1 
    	//访问这个这个顶点
    	VisitFun(G,v);
    	//寻找与这个顶点相邻的其他结点 
    	for(int k=0;k<G.vexnum;k++){
    		if(G.AdjMatrix[v][k]==1){  //有边 
    			if(visited[k]==0){  //且该顶点没有被访问过 
    				//那么久递归调用DFS去遍历与这个边邻接的顶点 
    				DFS(G,visited,k);
    			} 
    		}
    	}
    }
    main() {
    	int visited[MAX_VERTEX_NUM];
    	//初始化访问标记数组 顶点访问则设置为1 
    	for(int i=0;i<MAX_VERTEX_NUM;i++){
    		visited[i] = 0;
    	}
    	MGraph G;
    	CreateGraph(G);
    	DFS(G,visited,0);
    }
    
    展开全文
  • 设V={0,1,2,……,n-1},结点又称为顶点(vertex),有向(directed graph)指中代表边偶对是有序,用<u,v>代表一条有向边(又称为弧),则u称为该边始点(尾),v称为边终点(头)。无向(und...

    描述

    图(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<stdio.h>
    #include<malloc.h>
    
    
    typedef struct graph      //图的结构体
    {
        int Vertices;       //顶点数
        int **A;             //图的二维矩阵
    }Graph;
    
    void CreateGraph(Graph *g,int n)          //创建一个、包含了n个顶点的图
    {
        int i,j;
        g->Vertices = n;
        g->A = (int**)malloc(n*sizeof(int*));
        for(i = 0;i < n;i++)
        {
            g->A[i] = (int*)malloc(n*sizeof(int));
            for(j = 0;j < n;j++)
                g->A[i][j] = 0;
        }
    }
    
    int Add(Graph *g,int u,int v)    //在图g中添加一条边(u,v)
    {
        int n = g->Vertices;
        if(u<0||v<0||u>n-1||v>n-1||g->A[u][v]!=0)  //不知道为什么这里不要判断u==v的情况
        {
            return 0;
        }
        g->A[u][v]=1;
        return 1;
    }
    
    
    int Exist(Graph g,int u,int v)  //判断图中是否存在边(u,v)
    {
        int n;
        n = g.Vertices;
        if(u<0||v<0||u>n-1||v>n-1||g.A[u][v]==0)
            return 0;
        return 1;
    }
    
    void DFS(Graph g,int v,int *visited)   //深度遍历图
    {
        int w;
        visited[v]=1;
        printf("%d ",v);
        for(w=0;w<g.Vertices;w++)
        {
            if(Exist(g,v,w)&&visited[w]!=1)
                DFS(g,w,visited);
        }
    }
    
    
    int main()
    {
        int enumber,vnumber,one,two,i,j;
        Graph g;
        int visited[20];
        
        scanf("%d %d",&vnumber,&enumber);   //vnumber为图中顶点的个数,enumber为图中边的条数
        if(1<=vnumber<=20&&0<=enumber<=190)
        {
            CreateGraph(&g,vnumber);    //创建一个图
        }
        else 
            return 0;
        
        for(i=0;i<enumber;i++)    //向图中添加边
        {
            scanf("%d %d",&one,&two);
            Add(&g,one,two);
            Add(&g,two,one);
        }
    
        for(i=0;i<vnumber;i++)  //将图的邻接矩阵输出
        {
            for(j=0;j<vnumber;j++)
            {
                if(Exist(g,i,j))
                    printf("%d ",1);
                else
                    printf("%d ",0);
            }
            printf("\n");
        }
    
        for(i=0;i<g.Vertices;i++)   //visited[]为每个顶点的标志位,用来判断顶点是否被访问过,0表示没有被访问。
        {
            visited[i]=0;
        }
        for(i=0;i<g.Vertices;i++)
        {
            if(visited[i]!=1)      //深度遍历图
                DFS(g,i,visited);
        }
        printf("\n");
        return 1;
    }

     

    转载于:https://www.cnblogs.com/rolly-yan/p/3565310.html

    展开全文
  • 一、图的存储用邻接表法存储图,存储结构分为两部分,一部分为存储图的所有顶点的数组,另一部分为挂载在数组的...//进行图的遍历时用于标记图是否被访问过node*next;vnode(){visted= false;next=NULL;}};链表的结构...

    一、图的存储

    用邻接表法存储图,存储结构分为两部分,一部分为存储图的所有顶点的数组,另一部分为挂载在数组的每个元素后面的用来表示顶点的邻接点的链表。

    1、存储顶点的结构单元为:

    classvnode

    {public:stringnodename;boolvisted;//进行图的遍历时用于标记图是否被访问过

    node*next;

    vnode()

    {

    visted= false;

    next=NULL;

    }

    };

    链表的结构单元为:

    classnode

    {public:stringnodename;intnodeindex;//节点的索引,用于快速定位节点在顶点数组中的位置intweight;//权值,用于存储顶点之间的信息

    node*next;

    node() { next=NULL; }

    };

    2、现在声明Graph这个类,类的声明为(有关图的遍历的成员函数也以包含进来):

    classGraph

    {public:

    Graph();~Graph();bool DeepFirstSearch(intnodeindex);voidClearVisited();bool WideFirstSearch(int nodeindex);protected:

    vnode*pvnode;intvnumber;

    };

    3、下面是Graph类的成员函数的定义为(先实现关于图的存储的成员函数):

    Graph::Graph()

    {

    cout<< "请输入节点的个数:";

    cin>>vnumber;

    pvnode= newvnode[vnumber]; //通过new创建顶点数组for (int i = 0; i < vnumber; i++) //通过for循环将图的信息输入

    {

    cout<

    cout<< "请输入节点:";

    cin>>pvnode[i].nodename;stringcheck; //输入某个顶点的邻接点时,以"#"作为输入的结束标志while (1)

    {

    cout<< "请输入节点的相邻节点:";

    cin>>check;if (check == "#") { break; }//如果输入的"#"就跳出输入循环

    node*temp = newnode; //如果不是,就分配节点内存,完善相关信息

    temp->nodename =check;

    cout<< "请输入相邻节点的序号和权值:";

    cin>> temp->nodeindex >> temp->weight;

    temp->next =pvnode[i].next; //并将新输入的节点放到相应的链表中

    pvnode[i].next=temp;

    }

    }

    }

    Graph::~Graph() //释放内存时,先释放链表占用的内存,然后释放数组占用的内存

    {

    node*currentnode =NULL; //释放链表占用的内存

    node*temp =NULL;for (int i = 0; i < vnumber; i++)

    {

    currentnode=pvnode[i].next;while (currentnode !=NULL)

    {

    temp= currentnode->next; //保存当前节点的下一个节点的内存deletecurrentnode; //释放当前节点的内存

    currentnode=temp; //下一个节点作为当前的节点

    }

    }delete[]pvnode; //释放数组占用的内存

    }

    二、图的遍历

    1、深度优先遍历

    深度优先遍历通过递归的算法实现

    下面是实现图的深度优先遍历的成员函数的实现:

    bool Graph::DeepFirstSearch(intnodeindex)

    {if (nodeindex < 0 || nodeindex >=vnumber) //判断指定的起始节点是否合法

    {

    cout<< "The nodeindex does not exist..";return false;

    }if (pvnode[nodeindex].visted == false) //判断当前节点是否被访问过,如果没有,则继续

    {

    cout<< pvnode[nodeindex].nodename << " "; //输出节点的名字

    pvnode[nodeindex].visted= true; //修改访问记录

    node*currentnode=pvnode[nodeindex].next; //找到当前节点相邻的一个节点while (currentnode !=NULL)

    {

    DeepFirstSearch(currentnode->nodeindex); //通过递归继续上述操作

    currentnode= currentnode->next; //换当前节点的另一个相邻节点试试

    }

    }return true;

    }

    2、广度优先遍历

    广度优先遍历需要借助队列这种数据结构。

    代码实现:

    bool Graph::WideFirstSearch(intnodeindex)

    {if (nodeindex < 0 || nodeindex >=vnumber) //判断输入的节点索引是否合法

    {

    cout<< "The nodeindex does not exist..";return false;

    }

    Queuequeue(vnumber);

    cout<< "广度优先搜索的遍历结果为:";

    cout<< pvnode[nodeindex].nodename << " "; //将起始节点的名字打印出来

    pvnode[nodeindex].visted= true; //更改起始节点的访问记录

    queue.EnQueue(nodeindex); //起始节点入队列int temp=0;

    node*currentnode =NULL;while (queue.QueueEmpty() == false) //对于每一个入队的节点,

    {

    queue.DeQueue(temp);

    currentnode=pvnode[temp].next; //按入队顺序访问其相邻的全部节点while (currentnode!=NULL)

    {if (pvnode[currentnode->nodeindex].visted == false)

    {

    cout<< currentnode->nodename << " ";

    pvnode[currentnode->nodeindex].visted = true; //已经访问过的节点更改访问记录并入队

    queue.EnQueue(currentnode->nodeindex);

    }

    currentnode= currentnode->next;

    }

    }

    cout<

    }

    3、由于这两种算法都需要对节点的访问记录进行修改,所以每次用这两种的某一种算法实现遍历后需要初始化访问记录才能继续使用。

    初始化访问记录的函数代码实现为:

    voidGraph::ClearVisited()

    {for (int i = 0; i < vnumber; i++)

    {

    pvnode[i].visted= false;

    }

    }

    注:完整的代码在下面赋上,另附上实现队列的完整代码

    展开全文
  • 图的深度优先遍历c语言版 受益良多 可参考数据结构|(清华版 主编 严蔚敏)
  • } /************************************************************************/ /* 深度优先遍历(深度优先搜索) */ /************************************************************************/ bool ...
  • 以下是老师作为数据结构课作业要求,没有什么实际...宽度优先遍历: 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 6 #define _...
  • 无向 深度优先遍历 c语言实现

    千次阅读 2015-06-22 17:00:47
    无向图的深度优先遍历的实现,无向图用邻接表表示无向图的表示:邻接矩阵和邻接表。程序使用的示例图为: 实现要点: 每个节点有三种状态-1,0,1,分别表示未发现,已经发现,已经处理。代码如下:#include #...
  • 图的深度优先遍历C语言数据结构)C语言的代码,可用visual C++进行编译
  • 图的深度优先遍历C语言实现.pdf维普资讯九 江 职 业 技 术 学 院 学 报JournalofJiujiangVocational&TechnicalCollege 2004.2· 26 ·图的深度优先遍历C语言实现杜 恒 ‘龚茜茹(河南32业职业技术学院,河南...
  • C语言实现图的深度优先遍历和广度优先遍历

    千次阅读 多人点赞 2019-11-28 20:29:17
    图的深度优先遍历和广度优先遍历图的遍历深度优先遍历广度优先遍历 图的遍历 从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中所有顶点,使每个顶点仅被访问一次,这个过程称为图的...
  • 数据结构中的图结构,其中最重要两个遍历算法——深度优先遍历与广度优先遍历
  • /* 深度优先遍历 */   /************************************************************************/   bool  DFS(ALGraph* a,  int  i)  {    if (a == NULL)    return  FALSE; ...
  • void dfs(int cur,int dis) //cur是当前所在顶点编号,dis是当前已经走过路程 { int j; if(dis>min) //如果当前走过路程已经大于之前最短路,则没必要继续尝试了,立即返回 return ; if(cu
  • MGraph. h #pragma once #include "Queue.h" #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs... //当前顶点数 int e; /
  • c语言实现图的深度优先遍历和广度优先遍历

    万次阅读 多人点赞 2016-06-11 20:55:42
    c语言实现图的深度优先遍历和广度优先遍历
  • 当一个为稀疏时,使用邻接矩阵会浪费大量存储空间。...1)对图G每个顶点vi建立一个单链表,第i个单链表中结点表示依附于顶点vi边(对于有向则是以顶点vi为尾弧)。这个单链表就称为顶点v...
  • 试实现邻接矩阵存储图的深度优先遍历。 函数接口定义: void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); 其中MGraph是邻接矩阵存储的图,定义如下: typedef struct GNode *PtrToGNode; struct GNode{ ...
  • //代码可直接运行#include #include #define maxsize 100typedef struct ArcNode {int num;struct ArcNode *next;}ArcNode;typedef struct VNode{ArcNode *firstarc;}VNode;typedef struct Graph {VNode VNodeList...
  • (2)对邻接矩阵表示的图实现深度优先遍历深度优先遍历的基本思想: ① 选择一个起始点出发,并访问之; ②一次从起始点未访问过邻接点出发,深度遍历,直到中与起始点有 路径相通顶点都被访问过...
  • ALGraph.h#pragma once#include "Queue.h"/************************************************************************//* 图的邻接表存储结构 *//*********************...
  • 图的深度优先遍历-C语言实现

    万次阅读 多人点赞 2014-10-16 18:41:11
    void DFS(int i,ALGraph &G) //图的深度优先遍历的递归运算 {  printf("%s ",G.adjList[i].vertex);  visit[i]=1;  ArcNode *p;  p=G.adjList[i].link;  while(p!=NULL)  {  if(G.adjList...
  • 注:此代码实现需要以...深度优先遍历 深度优先遍历只需要依次访问结点即可,实现较为简单 //深度优先遍历 void DFS(LGraph* g,int *visit,int v) { printf("Node: %d\n",v); ENode* p = g->a[v]; visit[v]
  • 读入一个邻接矩阵存储的无向,输出它的深度优先遍历序列。 输入格式 第1行1个整数n,表示中的顶点数,2<=n<=100 接下来的n行是一个n*n的邻接矩阵,a[i][j]=1表示顶点i和顶点j之间有直接边相连,a[i][j]=...
  • c语言的数据结构图的深度优先遍历和广度优先遍历
  • 图的深度优先遍历是最直观的。 详情见:https://blog.csdn.net/zuihongyan518/article/details/80823924 摘抄如下: 深度遍历算法的基本思想: 图的深度遍历算法粗略的可以分为以下三步骤: (1)首先选定一个未...
  • C语言非连通图的深度优先遍历

    千次阅读 2017-01-20 17:20:02
    非连通图的深度优先遍历算法

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 351
精华内容 140
关键字:

图的深度优先遍历c语言

c语言 订阅