《数据结构与算法》——图

luciferzf

图：
1）图是由点的集合和边的集合组成的一个多对多的关系，通常可以表示为G（V，E），其中V是点的集合，E是边的集合，点的集合要求有穷非空
2）简单图：图中不存在顶点到自身的边，并且两个点之间只有一条边
3）无向完全图：任意2个顶点间都存在无向边
4）有向完全图：任意2个顶点间都存在两条方向相反的有向边
5）连通图：图中任意两个点都连通；强连通图则要求任意两个点都存在路径

图的存储结构：
1）我们定义一个一维数组存放顶点，一个二维数组存放边，对于二维数组元素T[a][b]表示点a和b的关系，若T[a][b]值为1，表示a和b之间有边，若为0，则无边
2）对于无向图，边的储存数组相当于一个对称矩阵，一个顶点的度等于该顶点在矩阵中对应行的1的个数
3）对于网，储存边的数组中的值不再只是0和1，而是每条边的权，若两个点间不存在边，则定义数组对应元素的值为无穷大（即一个比其他元素值都大的静态值）

邻接表：
首先定义一个顺序表用来存储各个节点，然后利用链表的形式，将各个相邻点在顺序表中的下标依次连接在顺序表里各个点上。对于有向表来说，这样就易于得到点的出度。
十字链表：相比于邻接表，十字链表将出度和入度分开，十字链表的顺序表中的各个点不仅储存了出度的点的下标，还有入度的点的下标，对于有向图，更易于得到入度和出度。
邻接多重表：在边表结构中，我们储存了一条边的两个点的下标，以及分别指向与两个点相邻的另外两条边的指针

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define N 100

class edgenode
{
public:
        int index;
        edgenode *np=NULL;

};

class node
{
public:
        char data;
        int flag = 0;
        edgenode *np=NULL;
}vertex[N];


void Input()
{
        int T;
        cout << "Input vertex:";
        cin >> T;
        vertex[0].data = T;
        for (int i = 1; i < T+1; i++)
        {
                cin >> vertex[i].data;
        }
        cout << "Input edges:";
        cin >> T;
        for (int i = 1; i < T+1; i++)
        {
                int a, b;
                edgenode *cp = NULL;
                cin >> a >> b;
                if (vertex[a].np == NULL)
                {
                        cp = new edgenode;
                        vertex[a].np = cp;
                }
                else
                {
                        cp = vertex[a].np;
                        while (cp->np != NULL)
                        {
                                cp = cp->np;
                        }
                        edgenode *p = cp;
                        cp = new edgenode;
                        p->np = cp;
                }
                cp->index = b;
        }
}

void research()
{
        int n = vertex[0].data;
        for (int i = 1; i <= n; i++)
        {
                edgenode *p=vertex[i].np;
                cout << vertex[i].data << "——>" << vertex[p->index].data;
                while (p->np != NULL)
                {
                        p = p->np;
                        cout << "——>" << vertex[p->index].data;
                }
                cout << endl;
        }
}

int main()
{
        Input();
        research();
        system("PAUSE");
}