内容纲要

1.图的简介

图(Graph)是表示物件与物件之间的关系的数学对象,是图论的基本研究对象。一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。对于一个拥有n个顶点的无向连通图,它的边数一定多于n-1条。若从中选择n-1条边,使得无向图仍然连通,则由n个顶点及这 n-1条边(弧)组成的图被称为原无向图的生成树。(百度百科

2.有向图与无向图

如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。

3.图的邻接矩阵

设有图G=(V,E),图中有n个顶点,可用两个数组表示这个图,一个一维数组存储图中顶点信息,一个二维数组存储图中的边或弧的信息,该二维数组成为邻接矩阵。对于一个有n个顶点的图,其邻接矩阵是一个nxn的方阵,定义为:Arc[i][j]=1,若(vi,vj)∈E或<vi,vj>∈E,反之等于0。若图带有边权,则邻接矩阵中存储权值。如图所示,是无向图图的邻接矩阵表示法:
无向图邻接矩阵
如图是有向图的邻接矩阵表示法:
有向图邻接矩阵

4.图的邻接表

图的邻接表存储方法是一种顺序与链式相结合的存储方法。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点i的边(对有向图是以顶点i为尾的边)。每个单链表上附设一个表头节点。其中,表节点由三个域组成,adjvex指示与顶点i邻接的点在图中的位置,nextarc指示下一条边或弧的节点,info存储与边或弧相关的信息,如权值等。表头节点由两个域组成,data存储顶点i的名称或其他信息,firstarc指向链表中第一个节点。(摘自这里,侵删)如图是图的邻接表:
图的邻接表(出处见图片,侵删)

5.图的存储实现

  • 邻接矩阵
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn = 1e2+6;

template <class T>
class graph
{
public:
    graph(); //构造
    ~graph(); //析构
    void create(); //创建
    void print_list(); //输出邻接矩阵
private:
    map<T,int> vertex; //顶点信息
    int arc[maxn][maxn]; //邻接矩阵
    int ver_num,arc_num; //顶点个数与边的个数
};

template <class T>
graph<T>::graph() //归零邻接矩阵,下同
{
    memset(arc,0,sizeof(arc));
    ver_num = 0;
    arc_num = 0;
}

template <class T>
graph<T>::~graph()
{
    memset(arc,0,sizeof(arc));
    ver_num = 0;
    arc_num = 0;
}

template <class T>
void graph<T>::create()
{
    int v,a;
    cout << "Input the number of vertexes: "; cin >> v;
    cout << "Input the number of arcs: "; cin >> a;
    ver_num = v;
    arc_num = a;
    for(int i = 0;i < ver_num;++i)
    {
        T tmp;
        cout << "Input the data of the " << i + 1 << "th vertex: ";
        cin >> tmp;
        vertex[tmp] = i; //利用map结构作为哈希表
    }
    char flag;
    cout << "Directed graph?(Y/n) "; cin >> flag;
    if(flag == 'Y')
    {
        for(int i = 0;i < arc_num;++i)
        {
            T st,ed;
            cout << "Input the starting point and the ending point of the " << i + 1 << "th arc: ";
            cin >> st >> ed;
            int sta = vertex[st];
            int edd = vertex[ed];
            arc[sta][edd] = 1;
        }
    }
    else
    {
        for(int i = 0;i < arc_num;++i)
        {
            T st,ed;
            cout << "Input the starting point and the ending point of the " << i + 1 << "th arc: ";
            cin >> st >> ed;
            int sta = vertex[st];
            int edd = vertex[ed];
            arc[sta][edd] = 1;
            arc[edd][sta] = 1;
        }
    }
}

template <class T>
void graph<T>::print_list()
{
    cout << ver_num << endl;
    for(int i = 0;i < ver_num;++i)
    {
        for(int j = 0;j < ver_num;++j)
            cout << arc[i][j] << " ";
        cout << endl;
    }
}

int main()
{
    graph<int> G;
    G.create();
    G.print_list();

    return 0;
}
  • 邻接表
    注意:邻接表代码没写打表,因为没意义,也因此无法系统debug,如果你发现以下代码有bug,请联系我。(菜鸡经常写bug)
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn = 1e2+6;

struct node //邻接表节点
{
    int loc; //图中位置
    node* next;
};

template <class T>
struct vertex //节点结构体
{
    T data; //数据
    node* first_arc;
};

template <class T>
class graph
{
public:
    graph(); //构造
    ~graph(); //析构
    void create(); //创建图
private:
    vertex<T>* ver[maxn]; //节点数组
    int ver_num; //节点数
    int arc_num; //弧数
};

template <class T>
graph<T>::graph() //构造方法
{
    for(int i = 0;i < maxn;++i) //分配内存,初始化指针
    {
        ver[i] = new vertex<T>;
        ver[i]->first_arc = NULL;
    }
}

template <class T>
graph<T>::~graph() //析构方法
{
    for(int i = 0;i < maxn;++i) //释放内存
    {
        while(true)
        {
            if(ver[i]->first_arc == NULL)
                break;
            node* p;
            p = ver[i]->first_arc;
            ver[i]->first_arc = p->next;
            delete p;
        }
        delete ver[i];
    }
}

template <class T>
void graph<T>::create()
{
    int v,a;
    cout << "Input the number of vertexes: "; cin >> v;
    cout << "Input the number of arcs: "; cin >> a;
    ver_num = v;
    arc_num = a;
    for(int i = 0;i < ver_num;++i)
    {
        T tmp;
        cout << "Input the data of the " << i + 1 << "th vertex: ";
        cin >> tmp;
        ver[i]->data = tmp;
    }
    char flag;
    cout << "Directed graph?(Y/n) "; cin >> flag;
    if(flag == 'Y') //有向图情况
    {
        for(int i = 0;i < arc_num;++i)
        {
            T st,ed;
            cout << "Input the starting point and the ending point of the " << i + 1 << "th arc: ";
            cin >> st >> ed;
            for(int i = 0;i < ver_num;++i)
            {
                if(ver[i]->data == st)
                {
                    int edd;
                    for(int j = 0;j < ver_num;++j)
                        if(ver[j]->data == ed)
                        {
                            edd = j;
                            break;
                        }
                    node* new_node = new node; //头接
                    new_node->loc = edd;
                    new_node->next = ver[i]->first_arc;
                    ver[i]->first_arc = new_node;
                    // cout << ver[i]->first_arc->loc << endl;
                    break;
                }
            }
        }
    }
    else //无向图情况
    {
        for(int i = 0;i < arc_num;++i)
        {
            T st,ed;
            cout << "Input the starting point and the ending point of the " << i + 1 << "th arc: ";
            cin >> st >> ed;
            for(int i = 0;i < ver_num;++i)
            {
                if(ver[i]->data == st)
                {
                    int edd;
                    for(int j = 0;j < ver_num;++j)
                        if(ver[j]->data == ed)
                        {
                            edd = j;
                            break;
                        }
                    node* new_node = new node;
                    new_node->loc = edd;
                    new_node->next = ver[i]->first_arc;
                    ver[i]->first_arc = new_node;
                    node* new_node_2 = new node;
                    new_node_2->loc = i;
                    new_node_2->next = ver[edd]->first_arc;
                    ver[edd]->first_arc = new_node_2;
                    break;
                }
            }
        }
    }
}

int main()
{
    graph<int> G;
    G.create();

    return 0;
}

总提纲:《数据结构》期末提纲小结

发表评论

电子邮件地址不会被公开。 必填项已用*标注