算法与数据结构(13): 图(1)——图的存储及遍历
·
文章目录
注：转载请标明原文出处链接：https://xiongyiming.blog.csdn.net/article/details/100918881
1 图简介
图 (Graph) 结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行(自动机)等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。
图分为 有向图 和 无向图，如下图所示：
有向图，如下图所示，对于顶点V1：初度=2，入度=1.
弧：有向图中顶点和顶点之间的连线。
无向图，如下图所示：
边：无向图中，顶点和顶点之间的连线。
2 图的存储
要想使用图去解决实际问题，那么就需要知道，图是如何进行存储的。
在存储有向图和无向图有一定的差别。
如下图所示，图的存储结构有：邻接矩阵、邻接表、十字链表和邻接多重表。其中，邻接矩阵使用数组表示，主要表达无向图和有向图；而邻接表和十字链表使用链表进行表示，主要表达有向图。邻接多重表使用链表进行表示，主要表达无向图。
2.1 邻接矩阵——数组
邻接矩阵由数组进行存储.
对于有向图：
对于无向图：
2.2 邻接表——链表
邻接表由链表进行存储.
2.3 十字链表——链表
十字链表由链表进行存储.
2.4 邻接多重表——链表
2.5 图的遍历
图的遍历分为：深度优先搜索 和 广度优先搜索
(1) 深度优先搜索
相当于前序遍历
(2) 广度优先搜索
(3) 代码示例
要求
图的遍历
深度优先遍历
广度优先遍历
Node.h
#pragma once
class Node
{
public:
Node(char data = 0);
char m_cData;
bool m_bIsVisited;
};
Node.cpp
#include<iostream>
#include"Node.h"
using namespace std;
Node::Node(char data)
{
m_cData = data;
m_bIsVisited = false;
}
CMap.h
#pragma once
#include<iostream>
#include<vector>
#include"Node.h"
using namespace std;
class CMap
{
public:
CMap(int capacity);
~CMap();
bool addNote(Node *pNode);
void resetNode();
bool setValueToMatrixForDirectedGraph(int row, int col, int val = 1);//为有向图设置邻接矩阵
bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);//为无向图设置邻接矩阵
void printMatrix();//打印邻接矩阵
void depthFristTraverse(int nodeIndex);//深度优先遍历
void breadthFirstTraverse(int nodeIndex);//广度优先遍历
private:
bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
void breadthFirstTraverseImpl(vector<int>preVec);//广度优先遍历函数
private:
int m_iCapacity;//图中最多可以容纳的顶点数
int m_iNodeCount;//已经添加的顶点(结点)个数
Node *m_pNodeArray;//用来存放顶点数组
int *m_pMatrix;//用来存放邻接矩阵
};
CMap.cpp
#include<iostream>
#include<vector>
#include"CMap.h"
using namespace std;
CMap::CMap(int capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArray = new Node[m_iCapacity];
m_pMatrix = new int[m_iCapacity*m_iCapacity];
memset(m_pMatrix, 0, m_iCapacity*m_iCapacity * sizeof(int));
}
CMap::~CMap()
{
delete[]m_pNodeArray;
delete[]m_pMatrix;
}
bool CMap::addNote(Node *pNode)
{
if (pNode == NULL)
{
return false;
}
m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void CMap::resetNode()
{
for (int i = 0; i < m_iNodeCount; i++)
{
m_pNodeArray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
return true;
}
bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
m_pMatrix[col*m_iCapacity + row] = val;
return true;
}
bool CMap::getValueFromMatrix(int row, int col, int &val)//从矩阵中获取权值
{
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
val = m_pMatrix[row*m_iCapacity + col];
return true;
}
void CMap::printMatrix()//打印邻接矩阵
{
for (int i = 0; i < m_iCapacity; i++)
{
for (int k = 0; k < m_iCapacity; k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
//深度优先遍历
void CMap::depthFristTraverse(int nodeIndex)
{
int value = 0;
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//通过邻接矩阵判断是否与其他的顶点有连接
for (int i = 0; i < m_iCapacity; i++)
{
getValueFromMatrix(nodeIndex, i, value);
if (value != 0)
{
//再判断该点是否被访问过
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
depthFristTraverse(i);//递归
}
}
}
}
//广度优先遍历
void CMap::breadthFirstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
vector<int>curVec;
curVec.push_back(nodeIndex);
breadthFirstTraverseImpl(curVec);
}
//广度优先遍历函数
void CMap::breadthFirstTraverseImpl(vector<int>preVec)
{
int value = 0;
vector<int>curVec;
for (int j = 0; j < (int)preVec.size(); j++)
{
for (int i = 0; i <= m_iCapacity; i++)
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
//再判断该点是否被访问过
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.size() == 0)
{
return;
}
else
{
breadthFirstTraverseImpl(curVec);
}
}
main.cpp
#include<iostream>
#include<vector>
#include"CMap.h"
#include"Node.h"
using namespace std;
/*******************************************
图的遍历
深度优先遍历
广度优先遍历
A
/ \
B D
/\ /\
C F G H
\ /
E
**********************************************/
int main()
{
CMap *pMap = new CMap(8);
Node *pNodeA = new Node('A');
Node *pNodeB = new Node('B');
Node *pNodeC = new Node('C');
Node *pNodeD = new Node('D');
Node *pNodeE = new Node('E');
Node *pNodeF = new Node('F');
Node *pNodeG = new Node('G');
Node *pNodeH = new Node('H');
pMap->addNote(pNodeA);
pMap->addNote(pNodeB);
pMap->addNote(pNodeC);
pMap->addNote(pNodeD);
pMap->addNote(pNodeE);
pMap->addNote(pNodeF);
pMap->addNote(pNodeG);
pMap->addNote(pNodeH);
pMap->setValueToMatrixForUndirectedGraph(0, 1);
pMap->setValueToMatrixForUndirectedGraph(0, 3);
pMap->setValueToMatrixForUndirectedGraph(1, 2);
pMap->setValueToMatrixForUndirectedGraph(1, 5);
pMap->setValueToMatrixForUndirectedGraph(3, 6);
pMap->setValueToMatrixForUndirectedGraph(3, 7);
pMap->setValueToMatrixForUndirectedGraph(6, 7);
pMap->setValueToMatrixForUndirectedGraph(2, 4);
pMap->setValueToMatrixForUndirectedGraph(4, 5);
pMap->printMatrix();
cout << endl;
//深度优先遍历
pMap->resetNode();
cout << "深度优先遍历: " ;
pMap->depthFristTraverse(0);
cout << endl;
cout << endl;
//广度优先遍历
pMap->resetNode();
cout << "广度优先遍历: " ;
pMap->breadthFirstTraverse(0);
cout << endl;
cin.get();
return 0;
}
运行结果
3 最小生成树
参考资料
[1] 数据结构探险之图篇
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
8
0- 0
已为社区贡献2条内容
所有评论(0)