这是一个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
无向图的深度和广度优先遍历 - C++
无向图的深度和广度优先遍历 - C++标签(空格分隔): 算法无向图的深度和广度优先遍历 - C 需要解决的问题 需要了解和学习的点 代码 本文来自《啊哈!算法》第5章第1节 点击下载PDF文件查看需要解决的问题一个无向图,怎么从深度和广度来遍历这个图,也就是怎么个走法需要了解和学习的点 图的邻接矩阵存储法(就是一个二维数组) 回溯 (这里要理解循环能给递归产生回溯的效果) 图的生成树 代码深度优先
无向图-邻接矩阵-宽度优先遍历-BFS C代码实现
一、BFS算法思路本算法以无向图为例,存储方式采用邻接矩阵1)将该网以邻接矩阵的方式存储,由于这里的示例采用无向图,因此它是一个对称阵2)选取A点为起始点,访问此顶点,用一个visit的bool型数组记录访问状态(false表示未被访问,true表示已访问)3)从A的未被访问的邻接点出发,宽度优先遍历图,直到图中所有和v有路径相通的顶点都被访问到宽度优先遍历需要借助队列,思想与二叉树的层序遍历类似...
图的邻接矩阵表示,深度优先遍历,广度优先遍历实现
C++实现图的邻接矩阵表示,深度优先遍历,广度优先遍历实现
无向图邻接矩阵的储存和深度优先遍历
#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;
邻接矩阵实现图+深度/广度优先遍历+最小生成树
用邻接矩阵存放图中顶点的关系,实现无向图的邻接矩阵存储。 1)图的建立,删除(添加,删除边/顶点) 2)广度和深度优先遍历 3)prim最小生成树 1,成员变量,构造函数,以及数组扩展 实现策略:维护一个顶点的数组,以及一个二维的数组来表示顶点之间的关系,维护2个基本变量记录顶点和边的数量。 重点是:1)可以动态扩展顶点数组,并保持数组的连续性,这意味着删除顶点时后
邻接矩阵深度优先和广度优先遍历(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是布尔类型,其
无向图的深度优先遍历和广度优先遍历(邻接链表)
我选的是邻接链表,建立如下图所示的图: 我把它画出来,图是这样子的: 对于深度优先遍历:是从一个顶点v出发,一步一步地向前推进,当找不到未访问过的顶点时,也是一步一步地回退。其过程类似于用栈求解迷宫问题的搜索方式。 比如上面这个图:我从4这个顶点开始遍历,它先访问它第一个邻接点1,然后1访问它的第一个邻接点4,发现4已经访问过了,然后访问第二个邻接点2
建立图(邻接矩阵、邻近表任选其一)的存储结构、实现图的深度优先遍历和广度优先遍历。
#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;   ...
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历
数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
Java实现图:邻接矩阵表示、深度优先搜索、广度优先搜索、无向图的最小生成树
程序中用到的栈和队列实现请参见另外的博文。 package test2; class Vertex{ private char vertexName; public boolean wasVisited; public Vertex(char name){ vertexName = name; wasVisited = false; } public void dis
C++编程练习(9)----“图的存储结构以及图的遍历“(邻接矩阵、深度优先遍历、广度优先遍历)
图的存储结构 1)邻接矩阵 用两个数组来表示图,一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中边或弧的信息。 2)邻接表 3)十字链表 4)邻接多重表 5)边集数组 本文只用代码实现用邻接矩阵方式存储图。忘见谅。 图的遍历 1)深度优先遍历(Depth_First_Search,DFS) 从图中某个顶点 v 出发,访问此顶点,然后从 v 的未被访问的邻接点出发深
数据结构中用邻接矩阵方式储存图,广度优先,深度优先遍历
以下是作业,用它用实现用邻接矩阵的方式来进行广度优先和深度优先的遍历。 代码比较简单,用了两个小时来写出来。   /**用邻接矩阵的方式来储存图,用广度优先方式进行遍历 **/ #include &quot;stdio.h&quot; #define max_matrix 10 int visited[max_matrix],matrix[max_matrix][max_matrix]; int n...
有向图和无向图邻接矩阵的输入输出,深度深度优先搜索,广度优先搜索
#include&amp;lt;iostream&amp;gt; #include&amp;lt;stdlib.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; #include&amp;lt;queue&amp;gt; #define MAXLEN 100 using namespace std; typedef char DataType; bool visited[MAXLEN]; typedef struct{ ...
C++实现图的邻接矩阵的创建以及其深度优先遍历和广度优先遍历
C++实现图的邻接矩阵的创建以及其深度优先遍历和广度优先遍历
邻接表存储图的深度优先、广度优先遍历非递归算法
邻接表存储图的深度、广度优先非递归遍历
建立图的邻接表储存并实现深度优先和广度优先遍历
#include <stdio.h> #include <stdlib.h> #define MAX 20 typedef int Vextype; typedef struct Vnode{ Vextype data; struct Vnode *next; }Vnode;//顶点的结点结构 typedef Vnode Lgraph[MAX];//一维数组类型标识符 //定义队列 typedef
无向图的构建及广度优先遍历---邻接表实现
无向图的构建及广度优先遍历---邻接表实现
图的邻接矩阵表示以及深度、广度优先遍历
图是一种重要的数据结构,主要由顶点和边组成,一般根据边是否为双向分为无向图和有向图。G1为无向图,G2为有向图。1、深度优先遍历假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点...
数据结构---图的邻接矩阵(创建,打印,深度优先遍历,广度优先遍历,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之间有边相连,则邻接矩阵...
深度优先算法和广度优先算法(基于邻接矩阵)
1.写在前面   图的存储结构有两种:一种是基于二维数组的邻接矩阵表示法。             另一种是基于链表的的邻接表。   在邻接矩阵中,可以如下表示顶点和边连接关系:      说明:   将顶点对应为下标,根据横纵坐标将矩阵中的某一位置值设为1,表示两个顶点向联接。   图示表示的是无向图的邻接矩阵,从中我们可以发现它们的分布关于斜对角线对称。
基于邻接矩阵的广度优先遍历
数据结构实验之图论一:基于邻接矩阵的广度优先搜索遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss Problem Description 给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点,节点编号小的优先遍历)
无向图的深度和广度优先搜索遍历(C)
无向图的深度和广度优先搜索遍历(C)   以邻接表作为图的存储结构,实现连通无向图的深度优先和广度优先遍历。以指定的结点作为起点,分别输出每种遍历下的结点访问序列。   #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #d
基于邻接表存储的图的深度优先遍历和广度优先遍历
邻接表实现代码: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...
深度广度优先遍历最小生成树
怎么用图的深度和广度优先遍历来遍历树呢?我是这样想的,把树构造成图就行了。 // 图的遍历.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "LinkQueue.h" #include #include #define VRType int//在这里是权值类
java 图 邻接表 深度优先遍历 广度优先遍历 最短路径
用Java描述的图,以邻接表存储,包含常用算法
图的遍历之深度优先搜索算法&&广度优先优先算法的实现
一.序 和树的遍历类似,我们希望从图中的某一个顶点出发访问图中其余顶点,保证每个顶点只被访问一次,这一过程叫做图的遍历。图的遍历算法是求解图的连通性问题(最小生成树),拓扑排序,求关键路径的基础。 而为了保证同一个顶点不被访问多次,在遍历图的的过程中,必须记下访问过的顶点。为此,需要设立一个辅助数组visited[0..n-1],初始值设置为0或假,这样其不为0或者为真时,表示此顶点已经被访问过
图 | 深度优先生成树和广度优先生成树
本章的第一节中,介绍了有关生成树和生成森林的有关知识,本节来解决对于给定的无向图,如何构建它们相对应的生成树或者生成森林。 其实在对无向图进行遍历的时候,遍历过程中所经历过的图中的顶点和边的组合,就是图的生成树或者生成森林。 图 1 无向图 例如,图 1 中的无向图是由 V1~V7 的顶点和编号分别为 a~i 的边组成。当使用深度优先搜索算法时,假设 V1 作为遍历的起始点,涉及到的顶点和...
邻接矩阵深度优先广度优先遍历
#include &amp;lt;iostream&amp;gt;#include&amp;lt;queue&amp;gt;#include&amp;lt;string&amp;gt;using namespace std;int visited[100];typedef struct{    string ch;}phen[100];typedef struct{    int arc[30][30];    int arcnum;    i...
C语言实现图的邻接矩阵存储结构及深度优先遍历和广度优先遍历
在Dev C++中调试运行通过。 用下图进行了测试。 #include #define MaxVertexNum 50 #define QueueSize 50 typedef enum{FALSE,TRUE}shifou; shifou visited[MaxVertexNum];
数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
图有两种表示方法:邻接矩阵和l邻接表,这里使用java实现一个简单的邻接矩阵。 来个栗子尝一尝: 使用邻接矩阵来表示该图 首先定义顶点数组,以及二维数组代表邻接矩阵: private int MAXVEX = 0;//顶点个数,顶点数组长度 private VertexArray&amp;lt;T&amp;gt;[] vertexArray = null;//顶点数组 pr...
广度优先生成树(无向图,邻接矩阵,BFS)
1、题目:  Problem Description 设有一连通无向图,其顶点值为字符型并假设各值互不相等,采用邻接矩阵表示法存储表示。利用BFS算法求其广度优先生成树(从下标0的顶点开始遍历),并在遍历过程中输出广度优先生成树的每一条边。  Input 有多组测试数据,每组数据的第一行为两个整数n和e,表示n个顶点和e条边(0  Output
实验四——图的基本操作及应用
题目一: 图的遍历(* 必做题) 实验内容和要求 [问题描述]           对给定图,实现图的深度优先遍历和广度优先遍历。 [基本要求]    以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 【测试数据】  由学生依据软件工程的测试技术自己确定。 主要思想     先用邻接表创建无向图,输入顶点作为表头...
图:图的邻接表创建、深度优先遍历和广度优先遍历代码实现
邻接表介绍邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构比较较浪费存储空间。如果不想浪费存储空间,大家肯定会先到链表。需要空间的时候再才想内存去申请,同样适用于图的存储。我们把这种数组与链表相结合的存储方式成为邻接表(Adjacency List)。关于邻接矩阵的详细介绍请看:图:图的邻接矩阵创建、深度优先遍历和广度优先遍历详解 。邻接表创建图我们创建边表的单链...
图算法:1、邻接表实现图的深度优先遍历,广度优先遍历
原文网址:http://blog.csdn.net/codeforme/article/details/6036864# ALGraph.h [cpp] view plaincopy #pragma once   #include "Queue.h"   /****************************************
无向图邻接表的深度优先遍历
#include #include #define Max 50 int visited[Max]; //边表节点 typedef struct EdgeNode { int adjvex;//储存对应顶点的下标 int weight;//用于储存权值 struct EdgeNode * p;//指向下一个边表节点 }EdgeNode;
邻接表实现无向图的深度和广度遍历
/*/* DFS深度优先遍历邻接表 */ #include &amp;lt;iostream&amp;gt; #include &amp;lt;malloc.h&amp;gt; using namespace std; #define MAX 20 typedef struct e_node//表节点 { int vex;//索引值 struct e_node *next; }*enode; typedef ...
文章热词 设计制作学习 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 java大神班 大数据大神班