数据结构(12) -- 图的邻接矩阵的DFS和BFS

////////////////////////////////////////////////////////
//图的邻接矩阵的DFS和BFS
////////////////////////////////////////////////////////
#include <iostream>
#include <stdlib.h>
#include <queue>
#define MaxVertexNum 100 //最大顶点数
//#define INFINITY 0  //无穷大设为无符号整数的最大值
typedef char VertexType;  //顶点类型设为字符类型
typedef int EdgeType; ///边的权值设为整形
enum GraphType{DG, UG, DN, UN}; //有向图,无向图,有向网图,无向网图
using namespace std;

typedef struct
{
    VertexType Vertices[MaxVertexNum]; //顶点表
    EdgeType Edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,即边表
    int n, e; //顶点数n和边数e
    enum GraphType GType;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int  i, j, k, w;
    G->GType = UN;    /* Undirected Network  无向网图  */
    cout << "请输入顶点数和边数(输入格式为:顶点数, 边数):" << endl;
    cin >> G->n >> G->e; /* 输入顶点数和边数 */
    cout << "请输入顶点信息(输入格式为:顶点号<CR>):" << endl;
    for (i = 0; i < G->n; i++)
        cin >> &(G->Vertices[i]); /*  输入顶点信息,建立顶点表  */
    for (i = 0; i < G->n; i++)
        for (j = 0; j < G->n; j++)
            G->Edges[i][j] = 0; /* 初始化邻接矩阵 */
    cout << "请输入每条边对应的两个顶点的序号和权值,输入格式为:i, j, w:" << endl;
    for (k = 0; k < G->e; k++) {
        cin >> i >> j >> w; /* 输入e条边上的权,建立邻接矩阵 */
        G->Edges[i][j] = w;
        G->Edges[j][i] = w; /* 因为无向网图的邻接矩阵是对称的 */
    }
}

void Print(MGraph *G)
{
    cout << "   ";
    for (int i = 0; i < G->n; i++)
        cout << G->Vertices[i] << "  ";
    cout << endl;
    for (int i = 0; i < G->n; i++)
    {
        cout << G->Vertices[i] << "  ";
        for (int j = 0; j < G->n; j++)
        {
            cout << G->Edges[i][j] << "  ";
        }
        cout << endl;
    }
}

//邻接矩阵存储的图 - DFS
bool Visited[100] = { false };
void DFS(MGraph *G, int k)
{
    cout << G->Vertices[k] << " ";
    Visited[k] = true;
    for (int i = 0; i < G->n; i++)
    {
        if (G->Edges[k][i] == 1 && Visited[i] == false)
        {
            DFS(G, i);
        }
    }
}

//邻接矩阵存储的图 - BFS
void BFS(MGraph *G, int k)
{
    bool Visited[100] = { false };
    queue<int> q;
    for (int i = 0; i < G->n; i++)
        Visited[i] = false;

    if (Visited[k] == false) //如果节点未访问
    {
        Visited[k] = true;
        cout << " visit vertex: " << G->Vertices[k] << endl;
        q.push(k); //u入队列
    }
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int w = 0; w < G->n; w++)
        {
            if (G->Edges[t][w] != 0 && Visited[w] == false)
            {
                Visited[w] = true;
                cout << " visited vertex: " << G->Vertices[w] << endl;
                q.push(w);
            }
        }
    }
}
int main()
{
    MGraph *G = new MGraph;
    CreateMGraph(G);
    Print(G);
    cout << endl;
    DFS(G, 0);
    //BFS(G, 0);
    system("pause");
    return 0;
}

测试截图:

时间: 04-09

数据结构(12) -- 图的邻接矩阵的DFS和BFS的相关文章

算法导论--图的遍历(DFS与BFS)

转载请注明出处:勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51897538 图的遍历就是从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次.为了保证图中的顶点在遍历过程中仅访问一次,要为每一个顶点设置一个访问标志.通常有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS).这两种算法对有向图与无向图均适用. 以下面无向图为例: 1.深度优先搜索(DFS) 基本步骤: 1.从图中某个顶点v0出发,首先访问v

图的遍历 (dfs与bfs)x

遍历是很多图论算法的基础,所谓图的遍历( graph traversal),也称为搜索( search),就是从图中某个顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次.         遍历可以采取两种方法进行:         深度优先搜索( DFS: depth first search):         广度优先搜索( BFS: breadth first search). 对图进行存储与遍历: 输入: 第一行:顶点数n. 第二行:边数m. 以下m行,每行两个顶点编号u

java 数据结构 图中使用的一些常用算法 图的存储结构 邻接矩阵:图的邻接矩阵存储方式是用两个数组来标示图。一个一位数组存储图顶点的信息,一个二维数组(称为邻接矩阵)存储图中边或者弧的信息。 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 实例如下,左图是一个无向图。右图是邻接矩阵表示:

以下内容主要来自大话数据结构之中,部分内容参考互联网中其他前辈的博客. 图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合. 无边图:若顶点Vi到Vj之间的边没有方向,则称这条边为无项边(Edge),用序偶对(Vi,Vj)标示. 对于下图无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D}:边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}: 有向图:若

数据结构:图的实现--邻接矩阵

图结构的邻接矩阵实现 为了表现图中顶点之间的关联,我们可以使用邻接矩阵来实现图结构.所谓的邻接矩阵,就是一个反应边与边之间联系的二维数组.这个二维数组我们用matrix[numV][numV]表示,其中numV是顶点数. 对于无权图 若顶点Vi和Vj之间有边,则matrix[Vi][Vj]=1;否则matrix[Vi][Vj]=0. 对于有权图 若顶点Vi和Vj之间有边,且权值为weight,则matrix[Vi][Vj]=weight;否则matrix[Vi][Vj]=0或MAXWEIGHT(

数据结构(11) -- 邻接表存储图的DFS和BFS

/////////////////////////////////////////////////////////////// //图的邻接表表示法以及DFS和BFS /////////////////////////////////////////////////////////////// #include <iostream> #include <stdlib.h> #include <queue> using namespace std; //图的邻接表表示法

数据结构之图(一)图的存储结构

图的存储结构相对于线性表和树来说更为复杂,因为图中的顶点具有相对概念,没有固定的位置.那我们怎么存储图的数据结构呢?我们知道,图是由(V, E)来表示的,对于无向图来说,其中 V = (v0, v1, ... , vn),E = { (vi,vj) (0 <=  i, j <=  n且i 不等于j)},对于有向图,E = { < vi,vj > (0 <=  i, j <=  n且i 不等于j)}.V是顶点的集合,E是边的集合.所以我们只要把顶点和边的集合储存起来,那么

学习笔记:图的DFS和BFS的两种搜索办法

  在学习图结构的过程中,DFS和BFS是两种不同的遍历方式,其寻找元素具有不同的优点和缺陷. BFS被称作广度优先算法, 在遍历整个图的过程中,BFS将采用入队的方式进行,值得一提的是,这和树结构中的层序遍历有很大的相似之处. 在层序遍历中,将父亲节点入队后,在父亲节点出队后,将其儿子节点入队. 同理在图的BFS遍历中,先让BFS的首元素入队,在收元素入队后将他的儿子节点入队,放能够实现BFS搜索,他们的整体思想是一样的. 1 void TraversalGraph_BFS(LGraph Gr

数据结构之图的邻接表

1.邻接表的简介: 图的邻接矩阵存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构.邻接表由表头结点和表结点两部分组成,其中图中每个顶点均对应一个存储在数组中的表头结点.如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中.如词条概念图所示,表结点存放的是邻接顶点在数组中的索引.对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点.[1] 邻接

数据结构之图 Part2 - 1

邻接矩阵 网上很少有C# 写图的数据结构的例子,实际的项目中也从来没用过Array 这坨东西,随手写个,勿喷. namespace LH.GraphConsole { public struct Graph { public Graph(int vertexNumber, int edgeNumber) { VertexNumber = vertexNumber; EdgeNumber = edgeNumber; Vertexs = new string[VertexNumber]; Edges