数据结构图

图遍历

最小生成树

地图，路径规划 ...

权重，加权

边

邻接点

连通图

顶点

Graph
GraphQL

deepth

broadf

doing edge

dingdian

ten linked

ten linked

how to code

all map

map of

struct

symmetry

array real

array

great

看！虎头虎尾

prim算法是：假设从顶点A开始， 先选距离A最近的顶点（比如F），然后把把F点放入已涉及顶点集合当中，A-F边放入已选边的集合中。之后将A和F看作一个整体，再去找理这个整体最近的点和边。

kruskal算法是：先把所有的边找到，每一次都去找所有边中最短的那一条。不断的把顶点连接起来，直到所有的顶点都放入顶点集合中 并且通过边形成同一个集合为止。

2种算法都要在选边的过程中不断判断选择的边是否会和已有边形成闭环，如果形成闭环就要舍弃

十字链表方式存储图的数据结构和存储内容

链式存储图的一些表示方法。

存储的数据比较多

邻接表-链式存储

• 顶点的表示：顶点索引+出弧链表头指针+顶点数据

• 弧：弧头顶点索引+下一条弧指针+弧数据

• 逆邻接表：记录的是 入弧链表头指针 和 弧尾顶点索引

• struct Node{顶点索引；该顶点弧链表的头结点；顶点数据；}

• struct Arc{指向的顶点索引；指向下一条弧的指针；弧信息；}

• struct Map{顶点数组；}

顶点：  

顶点索引               出弧链表头指针                         顶点数据

    |                                  |                                           |

顶点索引      第一个出弧的指针(可以是NULL)         顶点数据

弧的表示方法：

弧头顶点索引                下一条弧指针                  弧数据

         |                                    |                                |

弧头顶点(指向的点)        一个点有多个弧              弧数据

                               每个弧保存下一条弧的指针

连通图：对于任何顶点都有通往其它顶点的边，即任意两个点之间都是连通的

完全图：任意顶点与其它顶点之间都能直接连接，边数与顶点间的数量关系：n(n-1)/2

生成树：顶点和仅能够连接这些顶点的边组成的，边数与顶点间的数量关系：n-1

main.cpp:


#include <iostream>
#include "CMap.h"

int main() {
    CMap *pMap = new CMap(6);

    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');


    pMap->addNode(pNodeA);
    pMap->addNode(pNodeB);
    pMap->addNode(pNodeC);
    pMap->addNode(pNodeD);
    pMap->addNode(pNodeE);
    pMap->addNode(pNodeF);


    //设置邻接矩阵
    pMap->setValueToMatrixForUndirectedGraph(0,1,6);
    pMap->setValueToMatrixForUndirectedGraph(0,4,5);
    pMap->setValueToMatrixForUndirectedGraph(0,5,1);
    pMap->setValueToMatrixForUndirectedGraph(1,2,3);
    pMap->setValueToMatrixForUndirectedGraph(1,5,2);
    pMap->setValueToMatrixForUndirectedGraph(2,5,8);
    pMap->setValueToMatrixForUndirectedGraph(2,3,7);
    pMap->setValueToMatrixForUndirectedGraph(3,5,4);
    pMap->setValueToMatrixForUndirectedGraph(3,4,2);
    pMap->setValueToMatrixForUndirectedGraph(4,5,9);

    pMap->primTree(0);




//    pMap->printMatrix();
//
//    cout<<endl;
//
//    pMap->depthFirstTraverse(0);
//    cout<<endl;
//    //广度遍历之前，由于之前的点都被表示为已经访问过
//    pMap->resetNode();
//    pMap->breadthFirstTraverse(0);
    return 0;
}

CMap.h:


#ifndef INC_0214_CMAP_H
#define INC_0214_CMAP_H

#include <vector>
#include "Node.h"
#include "Edge.h"
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);   //广度优先遍历

    void primTree(int nodeIndex);//Prim生成树

private:
    bool getValueFromMatrix(int row,int col,int &val);  //从矩阵中获取权值
    void breadthFirstTraverseImp(vector<int> preVec);    //广度优先遍历实现函数
    int getMinEdge(vector<Edge> edgeVec);//找最小边函数
private:
    int m_iCapacity;    //图中最多可以容纳的顶点数
    int m_iNodeCount;   //已经添加的顶点（结点）个数
    Node *m_pNodeArray; //用来指向一段内存，这段内存用来存放顶点数组
    int *m_pMatrix;     //用来存放邻接矩阵

    Edge *m_pEdge;//用于保存最小边，需要在cpp文件中申请一段内存
};

#endif //INC_0214_CMAP_H

CMap.cpp:
#include "CMap.h"
#include "Node.h"
#include <iostream>
#include <vector>
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));//需要初始化将这个矩阵的各元素初始化为0；
//也可以用for循环进行初始化：但是注意m_pMatrix是一个一维数组
//    for(int i = 0;i < m_pMatrix*m_pMatrix;i++){
//        m_pMatrix[i] = 0;
//    }
    //存放最小边的空间大小
    m_pEdge = new Edge[m_iCapacity - 1];

}

CMap::~CMap() {//针对析构函数中申请的内存进行释放
    delete []m_pNodeArray;
    delete []m_pMatrix;
}


bool CMap::addNode(Node *pNode) {  //向图中加入顶点（结点）
    if(pNode == NULL){
        return NULL;
    }
    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) {     //为有向图设置邻接矩阵,函数声明时是int val = 1，但是定义时不加=1
    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;
    }
}

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::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 == 1){
            if(m_pNodeArray[i].m_bIsVisited){
                continue;
            } else{
                depthFirstTraverse(i);
            }
        } else{
            continue;
        }
    }
}

void CMap::breadthFirstTraverse(int nodeIndex){
    cout << m_pNodeArray[nodeIndex].m_cData << " ";
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    //需要用数组来保存被访问过的结点的索引，这里使用vector,标准模板库需要将头文件加入
    vector<int> curVec;
    curVec.push_back(nodeIndex);

    breadthFirstTraverseImp(curVec);
}


void CMap::breadthFirstTraverseImp(vector<int> preVec){
    int value = 0;//用于去邻接矩阵取值，看是否为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{
        breadthFirstTraverseImp(curVec);
    }
}

void CMap::primTree(int nodeIndex) {//Prim生成树
    int value = 0;
    int edgeCount =0;
    vector<int> nodeVec;//存储点的集合
    vector<Edge> edgeVec;//存储边的集合
    //打印
    cout << m_pNodeArray[nodeIndex].m_cData <<endl;

    nodeVec.push_back(nodeIndex);
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    //
    while (edgeCount < m_iCapacity - 1){
        int temp = nodeVec.back();
        //寻找与该结点连接的所有的边
        for(int i = 0; i < m_iCapacity;i++){
            getValueFromMatrix(temp,i,value);
            if(value != 0){
                if(m_pNodeArray[i].m_bIsVisited) {//看点被访问过没，而不是边
                    continue;
                } else{
                    //若这条边还没有被访问过，放进数组
                    Edge edge(temp,i,value);//用构造函数实例化一个边的对象
                    edgeVec.push_back(edge);
                }
            }
        }
        //此时与temp连接的边都放入了备选边中，不会重复放入同一条边

        //从可选边集合中找出最小的边，连着这条边的另一个顶点就放入点的集合中
        //从可选边集合中找出最小的边函数：
        int edgeIndex = getMinEdge(edgeVec);
        edgeVec[edgeIndex].m_bSelected = true;//把选中的边置为true

        //打印一下这个边
        cout << edgeVec[edgeIndex].m_iNodeIndexA << "----" << edgeVec[edgeIndex].m_iNodeIndexB;
        cout << " " << edgeVec[edgeIndex].m_iWeightValue << endl;

        //再把这条边放入最小生成树边的集合中
        m_pEdge[edgeCount] = edgeVec[edgeIndex];
        edgeCount++;
        //连着这条边的另一个顶点就放入点的集合中
        int nextNodeIndex = edgeVec[edgeIndex].m_iNodeIndexB;

        nodeVec.push_back(nextNodeIndex);//放入点时需要将访问置为true
        m_pNodeArray[nextNodeIndex].m_bIsVisited = true;
        //打印下一个点
        cout<<m_pNodeArray[nextNodeIndex].m_cData << endl;
    }
}

int CMap::getMinEdge(vector<Edge> edgeVec){
    int minWeight = 0;
    int edgeIndex = 0;
    int i = 0;
    for(; i < edgeVec.size();i++){

        if(!edgeVec[i].m_bSelected){//先看selected是不是为假
            minWeight = edgeVec[i].m_iWeightValue;
            //还需要记录最小边的索引
            edgeIndex = i;
            break;//找到第一个点之后就要跳出循环
        }
    }

    if(minWeight == 0){//找最小边失败，返回-1
        return -1;
    }

    for(;i < edgeVec.size();i++){
        if(edgeVec[i].m_bSelected){//若为true
            continue;
        } else{
            if(minWeight > edgeVec[i].m_iWeightValue){
                minWeight = edgeVec[i].m_iWeightValue;
                edgeIndex = i;
            }
        }
    }

    return edgeIndex;
}

Node.h:



#ifndef INC_0214_NODE_H
#define INC_0214_NODE_H

class Node{
public:
    Node(char data =0);
    char m_cData;
    bool m_bIsVisited;//访问过了是true
};

#endif //INC_0214_NODE_H

Node.cpp:



#include "Node.h"

Node::Node(char data) {
    m_cData = data;
    m_bIsVisited = false;
}

Edge.h:

#ifndef INC_0214_EDGE_H
#define INC_0214_EDGE_H


class Edge{
public:
    Edge(int nodeIndexA = 0,int nodeIndexB = 0,int weightValue = 0);
    int m_iNodeIndexA;
    int m_iNodeIndexB;
    int m_iWeightValue;
    bool m_bSelected;

};

#endif //INC_0214_EDGE_H

Edge.cpp:



#include "Edge.h"
Edge::Edge(int nodeIndexA,int nodeIndexB,int weightValue){
    m_iNodeIndexA = nodeIndexA;
    m_iNodeIndexB = nodeIndexB;
    m_iWeightValue = weightValue;
    m_bSelected = false;//false为未访问过
}

Prim算法：

选了F点后：

Kruskal算法：（最先选最小的边，再选次笑的边，前提是选边后不要造成闭环）

因为选的边没有交集，所以点集合分为两个集合

图的遍历：深度搜索（前序遍历）和广度搜索

深度搜索（前序遍历）：

广度搜索（较好理解，一层一层地搜索）

不同的搜索方式得到的生成树不同，上述较为简单，未涉及到权的问题。

若有权：最小生成树

两种算法：Prim算法 & Kruskal算法

十字链表：https://www.cnblogs.com/wkfvawl/p/9985083.html

十字链表，用结构体来存储：

邻接多重表—链式存储（无向图）

邻接矩阵用数组进行表达，相对来说比较简单。

邻接表和十字链表都是用链表表达，主要用于表示有向图。

邻接多重表则用于表示无向图。

领接矩阵：

自身不能到达自身，所以为0，以上是有向图，无向图的矩阵是对称的，所以克制抵只记录上或者下三角矩阵

数据结构用代码进行表示：

邻接表（记录出弧的链表的头指针）：逆-入弧

这样的数据结构方式如何通过数据结构的代码来实现呢？