邻接矩阵实现图

àì夳堔傛蜴生んèń 2022-02-16 20:11 268阅读 0赞

## 图 ##

Node.h

#ifndef NODE_H_
    #define NODE_H_
    class Node
    {
    public:
    	Node(char data = 0);
    	char m_cData;
    	bool m_bIsVisited;
    };
    
    #endif // !NODE_H_

Node.cpp

#include "Node.h"
    
    Node::Node(char data)
    {
    	m_cData = data;
    	m_bIsVisited = false;
    }

CMap.h

#ifndef CMAP_H_
    #define CMAP_H_
    #include "Node.h"
    #include <vector>
    using namespace std;
    
    class CMap
    {
    public:
    	CMap(int capacity);
    	~CMap();
    	bool addNode(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 depthFirstTraverse(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;     //用来存放邻接矩阵
    
    };
    
    
    #endif // !CMAP_H_
    #pragma once

CMap.cpp

#include "CMap.h"
    #include <iostream>
    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];
    	//初始化内部数据  将所有成员设置为0
    	memset(m_pMatrix, 0, m_iCapacity*m_iCapacity * sizeof(int));
    	//等效于
    	//for (int i = 0; i < m_iCapacity*m_iCapacity; i++)
    	//{
    	//	m_pMatrix[i] = 0;
    	//}
    }
    
    CMap::~CMap()
    {
    	delete[] m_pNodeArray;
    	delete[] m_pMatrix;
    
    }
    
    bool CMap::addNode(Node * pNode)
    {
    	if (!pNode||m_iNodeCount==m_iCapacity)
    	{
    		return true;
    	}
    	m_pNodeArray[m_iNodeCount++] = pNode->m_cData;
    	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)
    {
    	//row代表行  col代表列
    	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;
    }
    
    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::depthFirstTraverse(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&& !m_pNodeArray[i].m_bIsVisited)  //有与其连接的点  没有被访问过
    		{
    			depthFirstTraverse(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++)
    	{//遍历vector数组中的数
    		//判断当前结点与其他结点是否有连接
    		for (int i=0;i <m_iCapacity;i++ )
    		{
    			getValueFromMatrix(preVec[j], i, value);
    			if (value&&!m_pNodeArray[i].m_bIsVisited)
    			{
    				cout << m_pNodeArray[i].m_cData << " ";
    				m_pNodeArray[i].m_bIsVisited = true;
    				curVec.push_back(i);
    			}
    		}
    	}
    	if (curVec.size() != 0)
    	{
    		breadthFirstTraverseImpl(curVec);
    	}
    }
    
    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;
    }

demo.cpp

#include <iostream>
    #include <cstdlib>
    #include "CMap.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->addNode(pNodeA);
    	pMap->addNode(pNodeB);
    	pMap->addNode(pNodeC);
    	pMap->addNode(pNodeD);
    	pMap->addNode(pNodeE);
    	pMap->addNode(pNodeF);
    	pMap->addNode(pNodeG);
    	pMap->addNode(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->depthFirstTraverse(0);
    	pMap->resetNode();
    	cout << endl;
    	pMap->breadthFirstTraverse(0);
    
    
    	delete pMap;
    	system("pause");
    	return 0;
    }