最小生成树||最短路径 邻接矩阵实现prim算法C++代码

对于一个数据结构研究生才接触的学弱来说，这是第二次学习数据结构了。当初老师安排写一个最短路径问题，网上查了很多博客感觉鱼龙混杂的。我写这个博客目的之一就是给那些和我一样的小白一点点解惑的帮助，另外更是为了自己以后复习起来方便。

一、最小生成树VS最短路径

区分这两个概念非常重要，因为网上一堆prim算法, dijkstra算法，克鲁斯卡尔算法等，让人摸不着头脑他们之间有什么主要的区别和适用性。

我们要明白：

• 最小生成树的概念是对于一个图，要形成一个可以连接所有节点的权重最小的树。相关算法有：prim算法，克鲁斯卡尔算法；
• 最短路径问题比较常用，概念为对于一个图，找到图中任意两点间最短路径的树，该树不一定包括所有节点。相关算法：Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。
• （以下来自百度百科）
• 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
  1. 确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。
  2. 确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  3. 确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径。
  4. 全局最短路径问题- 求图中所有的最短路径。适合使用Floyd-Warshall算法。
• Dijkstra

  求单源、无负权的最短路。时效性较好，时间复杂度为O（VV+E)。源点可达的话，$O（V*lgV+E*lgV）=>O（E*lgV）$O（V∗lgV+E∗lgV）=>O（E∗lgV）。

  当是稀疏图的情况时，此时E=VV/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

• Floyd

  求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。

  　　Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。

  Floyd-Warshall算法的时间复杂度为O(N^{3)，空间复杂度为O(N}2)。

• Bellman-Ford

  求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。

  单源点的最短路径问题是指：

  　　给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

  与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

• SPFA

  是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。

  与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。

  SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。

  与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。

  在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。

  SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。

二、Prim算法

Prim算法伪代码

* 边类：节点A，节点B， 权重；
* 结点类：索引，是都被访问；
* 图类：prim（）函数
prim（int index）
{
        将index对应结点置为已访问；
        定义当前访问结点索引c_index，初值为传入值Index;
        while（已选边数目小于结点数目减一）
        {
                for(i=0,i<capacity)
                {
                        找到与所有与当前c_index相关联的边，并将边（index, x, weight）加入边集合vector向量中。
                }
                找到边集合中权重最小的边，拿出后将边的尾结点的是否访问置为true。
                将该边加入到最小边集合中。
                将c_index更新为新选的结点索引，进入下一轮循环。             
        }
}
找到边集合中权重最小的边的函数（vector<Edge> ee）
{
        遍历ee中所有元素，如果某一边的尾结点验证为访问过，则表示该条边已经被选入最小边集合，则不考虑。从剩下的边中选出值最小的。这里有必要解释下为什么将尾结点是否被访问过所为筛选条件，因为我们在存入一条边时，一定时按照当前访问结点和其边的尾节点，及该边权重 这样的顺序来存储的，所以边集合中的边的头结点一定都被访问过了，尾结点不一定。但是如果判断尾结点也被访问过了，可以说明这条边要么是形成的环的最后一条边，要么是已访问过的边，所以以 尾节点 是否被访问过作为筛选条件可以同时防止形成环和去除已访问过的边。
}

完整代码如下

//Node.h
#pragma once
#include<iostream>
using namespace std;
class Node
{
public:
        Node(int d=0);
        ~Node();
        //int index;
        int data;
        bool is_vis;
private:
};
//Node.cpp
#include"Node.h"
Node::Node(int d)
{
        //index = i;
        data = d;
        is_vis = false;
}
Node::~Node()
{
}

//Edge.h
#pragma once
#include<iostream>
using namespace std;
class Edge
{
public:
        Edge(int a=0, int b=0,int w=0);
        ~Edge();
        int nodeA;
        int nodeB;
        int weight;
private:

};


//Edge.cpp
#include"Edge.h"
Edge::Edge(int a, int b,int w)
{
         nodeA=a;
         nodeB=b;
         weight=w;
}

Edge::~Edge()
{
}
//Graph.h
#pragma once
#include"Node.h"
#include<vector>
#include"Edge.h"
class Graph
{
public:
        Graph(int c);
        ~Graph();
        bool add_node(Node *n);
        bool reset_node();
        void print_matrix();
        bool insert_edge(int row, int column, int wei=1);
        int get_matrix_value(int row, int column);
        void depth_search(int index);
        void width_search(int index);
        void prim(int index);
        Edge find_min_edge(vector<Edge> ee);
private:
        int capacity;
        vector<Edge> e_selected;
        vector<Edge>  e_not_sel;
        int node_count;
        Node* node_array;
        int* node_matrix;

};



//Graph.cpp
#include"Graph.h"
#include<queue>
Graph::Graph(int c)
{
        capacity=c;
        node_count=0;
        node_array=new Node[c];//初始化node数组
        node_matrix=new int[c*c];//n个节点
        memset(node_matrix, 0, c * c * sizeof(int));//初始化
}
bool Graph::add_node(Node* n)
{
                //node_array[node_count].index = node_count;
                node_array[node_count].data = n->data;//data就是节点编号
                cout << node_count <<"  "<< n->data << endl;
                node_count++;
                return true;       
}
void Graph::print_matrix()
{
        for (int i=0;i<capacity;i++)
        {
                for (int j=0;j<capacity;j++)
                {
                        cout << node_matrix[i * capacity + j]<<" ";
                }
                cout << endl;
        }
        cout<<"================================================================"<<endl;
}
bool Graph::insert_edge(int row, int column, int wei)
{
        if (row < 0 || row >= capacity) { return false; }
        if (column < 0 || column >= capacity) { return false; }
        //Edge e(row, column);
        node_matrix[row * capacity + column] = wei;
        node_matrix[column * capacity + row] = wei;
        return true;
}
int Graph::get_matrix_value(int row, int column)
{
        if (row < 0 || row >= capacity) { return 0; }
        if (column < 0 || column >= capacity) { return 0; }
        return node_matrix[row * capacity + column];
}
bool Graph::reset_node()
{
        for (int i = 0; i < node_count; i++)
        {
                node_array[i].is_vis = false;
        }
        return true;
}
void Graph::depth_search(int index)
{
        cout << node_array[index].data << " ";
        node_array[index].is_vis = true;
        for (int i = 0; i < capacity; i++)
        {
                if (get_matrix_value(index, i)==1)
                {
                        if (!node_array[i].is_vis)
                        {
                                depth_search(i);
                        }
                        else
                        {
                                continue;
                        }
                }
        }
}

void Graph::width_search(int index)
{
        cout << node_array[index].data << "\n"<<endl;
        node_array[index].is_vis = true;//第一个节点访问，并置为已访问
        queue<int> q;
        q.push(index);
        int pre_q = 1;//统计第一层节点的个数，首节点当然个数为1；
        while (!q.empty())
        {
                int value = 0;
                int cur_q = 0;//记录下一层元素的个数
                for (int i = 0; i < pre_q; i++)//注意这的截至条件是pre_q，说明每次循环都只会将上一层加入的节点取出，然后保存下一层的节点，根据先进先出原则，正好把上一层的取出完毕
                {
                        int num = q.front();//得到先进入的第一个元素
                        q.pop();
                        for (int j = 0; j < capacity; j++)
                        {
                                value = node_matrix[num* capacity + j];
                                if (value)
                                {
                                        if (!node_array[j].is_vis)//判断元素是否访问过。
                                        {
                                                cout << node_array[j].data << endl;
                                                node_array[j].is_vis = true;
                                                cur_q++;
                                                q.push(j);//将下一层的节点入队
                                        }
                                }                                
                        }
                }
                pre_q = cur_q;//将本层元素个数作为下一层循环的父节点个数
                cout << endl;
        }
        return;
}
void Graph::prim(int index)
{
        node_array[index].is_vis = true;
        int edge_count=0;
        int value = 0;
        int c_index = index;
        while (edge_count < (node_count - 1))
        {
                for (int i = 0;i < capacity;i++)//将新节点所涉及的所有边加入到新集合
                {
                        value = node_matrix[c_index * capacity + i];
                        if (value)
                        {
                                if (!node_array[i].is_vis)
                                {
                                        Edge e(c_index, i,value);
                                        e_not_sel.push_back(e);
                                        //node_array[i].is_vis = true;
                                }
                        }
                }
                //找出边中值最小的边
                Edge min_edge = find_min_edge(e_not_sel);
                e_selected.push_back(min_edge);
                int a = min_edge.nodeB;
                node_array[a].is_vis = true;
                cout << "nodeB" << a << endl;
                c_index = a;
                edge_count++;
        }
        for (int i = 0; i < e_selected.size(); i++)
        {
                cout << e_selected[i].nodeA << "  " << e_selected[i].nodeB << endl;
        }
}
Edge Graph::find_min_edge(vector<Edge> ee)
{
        int value=0;
        int min_value = 100000;
        int min_num = 0;
        for (int i = 0; i < ee.size(); i++)
        {
                        int b = ee[i].nodeB;
                        if (!node_array[b].is_vis)
                        {
                                value = ee[i].weight;
                                if (value < min_value)
                                {
                                        min_num = i;
                                        min_value = ee[i].weight;
                                }
                        }                        
        }
        return ee[min_num];

}
Graph::~Graph()
{
        delete[]node_array;
        delete[]node_matrix;
}
//main.cpp
#include"Graph.h"

int main()
{
        Graph g(8);
        Node* n1 = new Node(1);
        Node* n2 = new Node(2);
        Node* n3 = new Node(3);
        Node* n4 = new Node(4);
        Node* n5 = new Node(5);
        Node* n6 = new Node(6);
        Node* n7 = new Node(7);
        Node* n0 = new Node(0);

        g.add_node(n0);
        g.add_node(n1);
        g.add_node(n2);
        g.add_node(n3);
        g.add_node(n4);
        g.add_node(n5);
        g.add_node(n6);
        g.add_node(n7);
        

        //设置连接关系
        g.insert_edge(0, 1,3);
        g.insert_edge(2, 1,1);
        g.insert_edge(2, 3,5);
        g.insert_edge(0, 4,4);
        g.insert_edge(4, 3,6);
        g.insert_edge(4, 5,8);
        g.insert_edge(5, 7,10);
        g.insert_edge(5, 6,7);
        g.insert_edge(6, 7,2);
        cout << endl;
        g.prim(6);

        //g.depth_search(0);
        //g.reset_node();
        cout << endl;
        //g.width_search(0);
        //宽度遍历
        return 0;
}

三、Dijkstra算法

下一篇实现dijkstra算法