这是一个C++的无向图邻接矩阵,深度优先和广度优先遍历,实在不知道哪里不对,求大神解答
 #include<iostream>
 using namespace std;
const int MaxSize=10;//图中的最多顶点个数
template <class T>
classMGraph
{
    public:
        MGraph(T a[],int n,int e);//构造函数,建立具有n个顶点e条边的图
        ~MGraph(){}               //析构函数为空
        void DFSTraverse(int v);  //深度优先遍历图
        void BFSTraverse(int v);  //广度优先遍历图
        void Setvisited();       //
    private:
        T vertex[MaxSize];          //存放图中顶点的数组
        int arc[MaxSize][MaxSize];  //存放图中边的数组
        int vertexNum,arcNum;              //图的顶点数和边数
        int visited[MaxSize];       //
};

template<class T>
void MGraph<T>::Setvisited()
{
    for(int i=0;i<vertexNum;i++)    
        visited[i]=0;      

}

template<class T>
MGraph<T>::MGraph(T a[],int n,int e)
{
    int i,j,k;
    vertexNum=n;arcNum=e;
    for(i=0;i<vertexNum;i++)    
        vertex[i]=a[i];        
    for(i=0;i<vertexNum;i++)      //初始化邻阶矩阵
        for(j=0;j<vertexNum;j++)
            arc[i][j]=0;
        for(k=0;k<arcNum;k++)    //依次输入每一条边
        {
            cout<<"putin bianhao";
            cin>>i>>j;              //输入边依附的两个顶点的编号
            arc[i][j]=1;arc[j][i]=1;//置有边标志
        }
}

template<class T>
void MGraph<T>::DFSTraverse(int v)
{
    int j;
    cout<<vertex[v];visited[v]=1;
    for(j=0;j<vertexNum;j++)
        if(arc[v][j]==1&&visited[j]==0)
            DFSTraverse(j);
}

template<class T>
void MGraph<T>::BFSTraverse(int v)
{
    int j,front,rear;
    int Q[MaxSize];
    front=rear=-1;//初始化队列,假设队列采用顺序存储且不会发溢出
    cout<<vertex[v];visited[v]=1;Q[++rear]=v;//当访问顶点入队
    while(front!=rear)                      //当队列非空时
    {
        v=Q[++front];
            for(j=0;j<vertexNum;j++)         //将队头元素出队并送到v中   
                if(arc[v][j]==1&&visited[j]==0)
                {
                    cout<<vertex[j];visited[j]=1;Q[++rear]=j;
                }
    }
}

int main()
{
    int n,e;
    cout <<"putin dian:";
    cin>>n;
    cout<<"putin edge:";
    cin>>e;
    char a[MaxSize];
    cin>>a;
    MGraph<char> m(a,n,e);
    m.Setvisited();
    cout<<"DFST:";
    m.DFSTraverse(1);
    cout<<endl;
    m.Setvisited();
    cout<<"BFST:";
    m.BFSTraverse(1);
    cout<<endl;
    return 0;
}

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C++ 图的邻接矩阵表示以及深度优先和广度优先遍历
Node.h 声明顶点类 #pragma once class Node { public: Node(char data=0); char m_cData; bool m_bIsVisited; }; Node.cpp 实现顶点的成员以及操作函数 #include &quot;Node.h&quot; Node::Node(char data) { m_cData = data; m_b...
无向图的邻接矩阵,深度优先遍历和广度优先遍历的递归与非递归算法
/*(1)输入一组顶点,建立无向图的邻接矩阵。 进行DFS(深度优先遍历)和BFS(广度优先遍历)。 写出深度优先遍历的递归和非递归算法。*/ #include #define max 40 //最大顶点个数 #define M 10000 //无穷 #include typedef struct ArcCell{ int adj; //1/0表示是否有边。网中表示权值 }ArcCell
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。测试数据:教科书p168图7.13(a)。
图的邻接矩阵表示、广度优先遍历和深度优先遍历
如上如的所示,对图节点进行编号,每个节点又有相应的编号和值。因此图可以有一个二阶矩阵来记录各个节点的联通关系,由一个数组来记录各个节点的内容。图的广度优先遍历和深度优先遍历。 输出如下: 深度优先遍历: 1 2 4 8 5 6 3 7 广度优先遍历: 1 2 3 4 5 6 7 8 代码如下: import java.util.ArrayD
邻接矩阵深度优先和广度优先遍历(DFS和BFS)
/*邻接矩阵的广度遍历算法*/ #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 1 #define FALSE 0 #define TRUE 1 typedef int Status; //Status是函数的类型,其值是函数结果状态代码 typedef int Boolean;//Boolean是布尔类型,其
c语言编程 输出一个无向图的邻接表,邻接矩阵,进行深度和广度优先遍历
#include #include #include #include #define MAXVERTEX 10 //最大顶点数 typedef struct ArcNode //表结点的类型定义 { int adjvex; //边指向的顶点的位置 struct ArcNode *nextarc; //指示下一个与该顶
C语言实现邻接矩阵创建无向图&图的深度优先遍历
/* '邻接矩阵' 实现无向图的创建、深度优先遍历*/ #include &amp;lt;stdio.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; #define MaxVex 100 //最多顶点个数 #define INFINITY 32768 //表示极大值,即 ∞ #define TRUE 1 #define F...
图的邻接矩阵表示以及深度、广度优先遍历
图是一种重要的数据结构,主要由顶点和边组成,一般根据边是否为双向分为无向图和有向图。G1为无向图,G2为有向图。1、深度优先遍历假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点...
邻接矩阵存储结构广度遍历
存储结构:邻接矩阵; 实现功能:广度遍历; 博客中的代码实现
数据结构---图的邻接表(创建、打印、深度优先遍历,广度优先遍历C语言)
当一个图为稀疏图时,使用邻接矩阵会浪费大量存储空间。 邻接表法结合了顺序存储和链式存储方法,减少了不必要的浪费。 参照博文:https://blog.csdn.net/qq_39630587/article/details/77409869 邻接表 1)对图G的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点v...
数据结构与算法(Java描述)-20、图、图的邻接矩阵、有向图的广度优先遍历与深度优先遍历
一、图的基本概念图:是由结点集合及结点间的关系集合组成的一种数据结构。结点和边:图中的顶点称作结点,图中的第i个结点记做vi。有向图: 在有向图中,结点对<x ,y>是有序的,结点对<x,y>称为从结点x到结点y的一条有向边,因此,<x,y>与<y,x>是两条不同的边。有向图中的结点对<x,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边也称作弧。无向图 :在无向图中,结点...
基于邻接表存储的图的深度优先遍历和广度优先遍历
邻接表实现代码:https://blog.csdn.net/ASCIIdragon/article/details/84635236 c语言实现代码 /** 邻接表深度优先遍历和广度优先遍历 **/ #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;stdlib.h&amp;gt; #define MaxVex 255 #define TRUE 1 #defin...
无向图邻接表的深度优先遍历
#include #include #define Max 50 int visited[Max]; //边表节点 typedef struct EdgeNode { int adjvex;//储存对应顶点的下标 int weight;//用于储存权值 struct EdgeNode * p;//指向下一个边表节点 }EdgeNode;
建立图(邻接矩阵、邻近表任选其一)的存储结构、实现图的深度优先遍历和广度优先遍历。
#include &amp;lt;iostream&amp;gt;#include &amp;lt;stdlib.h&amp;gt;using namespace std;const int DefaultVertices=100;const int maxWeight=1000;typedef int E;typedef char T;class Graphmtx{private:    T *VerticesList;   ...
无向图的深度优先遍历和广度优先遍历(邻接链表)
我选的是邻接链表,建立如下图所示的图: 我把它画出来,图是这样子的: 对于深度优先遍历:是从一个顶点v出发,一步一步地向前推进,当找不到未访问过的顶点时,也是一步一步地回退。其过程类似于用栈求解迷宫问题的搜索方式。 比如上面这个图:我从4这个顶点开始遍历,它先访问它第一个邻接点1,然后1访问它的第一个邻接点4,发现4已经访问过了,然后访问第二个邻接点2
C++实现图的邻接矩阵的创建以及其深度优先遍历和广度优先遍历
C++实现图的邻接矩阵的创建以及其深度优先遍历和广度优先遍历
无向图的深度和广度优先遍历 - C++
无向图的深度和广度优先遍历 - C++标签(空格分隔): 算法无向图的深度和广度优先遍历 - C 需要解决的问题 需要了解和学习的点 代码 本文来自《啊哈!算法》第5章第1节 点击下载PDF文件查看需要解决的问题一个无向图,怎么从深度和广度来遍历这个图,也就是怎么个走法需要了解和学习的点 图的邻接矩阵存储法(就是一个二维数组) 回溯 (这里要理解循环能给递归产生回溯的效果) 图的生成树 代码深度优先
数据结构中用邻接矩阵方式储存图,广度优先,深度优先遍历
以下是作业,用它用实现用邻接矩阵的方式来进行广度优先和深度优先的遍历。 代码比较简单,用了两个小时来写出来。   /**用邻接矩阵的方式来储存图,用广度优先方式进行遍历 **/ #include &quot;stdio.h&quot; #define max_matrix 10 int visited[max_matrix],matrix[max_matrix][max_matrix]; int n...
无向图的广度优先遍历和深度优先遍历
public class MGraph { private char[] vexs;// 顶点 private int[][] edge;// 存储边的二维数组 private int arcNum;// 边的数目 private boolean[] visited;// 访问标志数组 // 确定顶点在图中的位置 public int locataVex(char ve...
图:图的邻接表创建、深度优先遍历和广度优先遍历代码实现
邻接表介绍邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构比较较浪费存储空间。如果不想浪费存储空间,大家肯定会先到链表。需要空间的时候再才想内存去申请,同样适用于图的存储。我们把这种数组与链表相结合的存储方式成为邻接表(Adjacency List)。关于邻接矩阵的详细介绍请看:图:图的邻接矩阵创建、深度优先遍历和广度优先遍历详解 。邻接表创建图我们创建边表的单链...
以邻接矩阵为存储结构,采用深度优先遍历或广度优先遍历,输出图的所有顶点的值(C语言)
题目: 以邻接矩阵为存储结构,采用深度优先遍历,输出图的所有顶点的值 测试数据 输入: 6 6 A B C D E F A B A C B E C E A D D F 输出:BACEDF #include&amp;amp;amp;lt;iostream&amp;amp;amp;gt; using namespace std; #define MAXNUM 100 char visited1[MAXNUM]; typedef st...
无向图邻接矩阵的储存和深度优先遍历
#include int visited[Maxsize]; #define Maxsize 50 #define M 500//定义无穷数值为5000 //标记顶点是否被访问,1为访问,0为未访问 typedef struct { int vex[Maxsize];//顶点表 int arc[Maxsize][Maxsize];//矩阵表 int numVertexes,numEdges;
Java实现图:邻接矩阵表示、深度优先搜索、广度优先搜索、无向图的最小生成树
程序中用到的栈和队列实现请参见另外的博文。 package test2; class Vertex{ private char vertexName; public boolean wasVisited; public Vertex(char name){ vertexName = name; wasVisited = false; } public void dis
C++实现无向图的邻接矩阵存储 及 深度优先遍历
方一:依次输入所有顶点的关系    方二:手动两两输入相连的顶点 #include &amp;lt;iostream&amp;gt; using namespace std; #define MAX_VERTEX 20 //最多允许创建20个顶点的图 typedef char DataType; typedef struct { int vertexNum,edgeNum; DataT...
数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
图有两种表示方法:邻接矩阵和l邻接表,这里使用java实现一个简单的邻接矩阵。 来个栗子尝一尝: 使用邻接矩阵来表示该图 首先定义顶点数组,以及二维数组代表邻接矩阵: private int MAXVEX = 0;//顶点个数,顶点数组长度 private VertexArray&amp;lt;T&amp;gt;[] vertexArray = null;//顶点数组 pr...
图的邻接矩阵表示,深度优先遍历,广度优先遍历实现
C++实现图的邻接矩阵表示,深度优先遍历,广度优先遍历实现
C语言以邻接矩阵为存储结构的图的构造以及广度优先,深度优先遍历
#include #include #define MAX_VALUE 10 #define HAVE_PATH 1 #define NO_PATH 0 typedef struct{ char vexs[MAX_VALUE];//存储顶点元素 int arc[MAX_VALUE][MAX_VALUE];//存储图结构路径的矩阵 int vexnum ;//当前定点数
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
求连通图的深度优先生成树和广度优先生成树
深度优先遍历就是先根遍历,用到辅助栈;广度优先遍历就是层次遍历,用到辅助队列。 一、树(自由树)、无序树和有根树 自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根,则成为一棵通常的树)。 从根开始,为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序,则它就成为一棵有序树。 在图的应用中,常常需要求给定图的一个子图,使该子图是一棵树。 二、生成树 1、生成树 ...
算法与数据结构实验5:图的深度和广度优先遍历(邻接矩阵)
Akatsuki
数据结构---图的邻接矩阵(创建,打印,深度优先遍历,广度优先遍历,C语言)
  邻接矩阵法   用一维数组图中顶点的信息,用一个二维数组存储图中边的信息(各顶点之间的邻接关系)。存储顶点之间邻接关系的二维数组称为邻接矩阵。      结点数为n的图G=(V,E)的邻接矩阵A是n*n的,将G的顶点编号为v1,v2,......vn。若(vi,vj)∈E,则A[i][j]=1,否则A[i][j]=0。   对于带权图而言,若顶点vi,vj之间有边相连,则邻接矩阵...
深度广度优先遍历最小生成树
怎么用图的深度和广度优先遍历来遍历树呢?我是这样想的,把树构造成图就行了。 // 图的遍历.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "LinkQueue.h" #include #include #define VRType int//在这里是权值类
java 图 邻接表 深度优先遍历 广度优先遍历 最短路径
用Java描述的图,以邻接表存储,包含常用算法
深度优先算法和广度优先算法(基于邻接矩阵)
1.写在前面   图的存储结构有两种:一种是基于二维数组的邻接矩阵表示法。             另一种是基于链表的的邻接表。   在邻接矩阵中,可以如下表示顶点和边连接关系:      说明:   将顶点对应为下标,根据横纵坐标将矩阵中的某一位置值设为1,表示两个顶点向联接。   图示表示的是无向图的邻接矩阵,从中我们可以发现它们的分布关于斜对角线对称。
图的邻接矩阵以及深度优先遍历 + 广度优先遍历
图的邻接矩阵表示法非常简单,一个定点数组,一个二维数组搞定,类似与这样 下面简单实现一个邻接矩阵表示的方法的图,以及遍历的两种方式。 Graph.h #pragma once #define MAX_SIZE 30 templateclass T,class E> class Graph { public: Graph(size_t size); virtual ~
数据结构之图的深度优先遍历和广度优先遍历
1.图的简单介绍 上图就是一个图(无线图),由顶点和连线组成 图可以分为无向图和有向图(这个又有出度、入度的概念)、网,一般来说图有两种常用的表示方式,邻接矩阵(用二维数组的形式表示)和邻接表(主要是数组+链表的形式表示),图常用的遍历方式有深度优先遍历(DFS)和广度优先遍历(BFS)。 由于等会代码是用邻接矩阵来实现DFS和BFS,这里主要介绍一下邻接矩阵的表示方法:两个顶点相邻,则
邻接矩阵的深度优先遍历与广度优先遍历——代码详解
由于比较仓促所以直接以代码的形式来讲解,所用为c++中的模板类。· 首先是此代码中用到的头文件:#include&amp;lt;iostream&amp;gt; #include&amp;lt;stdlib.h&amp;gt; #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;cstring&amp;gt;· 初始矩阵大小:const int MaxSize=100;· 因为邻接矩阵的广度优先遍历会用到队列,所以我...
图的邻接表创建及深度优先遍历和广度优先遍历
最近在学图,写个笔记。 图的创建一般有邻接矩阵和邻接表两种方法,邻接矩阵对于边数相对于顶点较少的图会有极大的浪费,所以用邻接表,用数组与链表相配合 顶点用一维数组储存 所有顶点的邻接点构成一个线性表,因为邻接点的个数不确定,所以用单链表 图的深度优先搜索是对先序遍历的推广 一个递归的过程,沿着一个方向遍历,一直到最后,然后再回来到另一个结点沿着一个方向。 广度优先遍历就是一层一层的遍历。如上图 ...
图 | 深度优先生成树和广度优先生成树
本章的第一节中,介绍了有关生成树和生成森林的有关知识,本节来解决对于给定的无向图,如何构建它们相对应的生成树或者生成森林。 其实在对无向图进行遍历的时候,遍历过程中所经历过的图中的顶点和边的组合,就是图的生成树或者生成森林。 图 1 无向图 例如,图 1 中的无向图是由 V1~V7 的顶点和编号分别为 a~i 的边组成。当使用深度优先搜索算法时,假设 V1 作为遍历的起始点,涉及到的顶点和...
C语言实现图的邻接矩阵存储结构及深度优先遍历和广度优先遍历
在Dev C++中调试运行通过。 用下图进行了测试。 #include #define MaxVertexNum 50 #define QueueSize 50 typedef enum{FALSE,TRUE}shifou; shifou visited[MaxVertexNum];
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 java大神班 大数据大神班