实验一、图的代数表示

一、实验内容及要求

编写用于表示有向图的数据结构，以及不同表示方法之间相互转换的程序。

从文件读入一个有向图（带权，n个结点，m条边）的权矩阵表示，输出这个图的关联矩阵、边列表、正向表、邻接表表示。

二、设计思路

【数据结构】

二维数组A：保存文件输入，即图的权矩阵

二维数组B：关联矩阵

3个数组Ae, Be, Ze：边列表

3个数组Ap, Bp, Zp：正向表

链表向量adjacent：邻接表

【算法】

根据图的各种代数表示的定义直接计算。

三、程序编译环境的说明

Windows 10环境Code::Blocks17.12 IDE下开发调试，

清橙OJ（http://www.tsinsen.com/）MinGW g++ 2.7.4下测试通过。

四、关键代码分析

1. 文件读写

#include<fstream>

ifstream fin("input.txt");
ofstream fout("output.txt");

fin >> …;
fout << …;

fin.close();
fout.close();

2. 初始化

2.1 二维动态数组初始化及其内存释放（不推荐使用，推荐用vector类模板）

int **B = new int*[N]();                        
for (i=0; i<N; i++)
{
    B[i] = new int[M]();
}

for (i=0; i<N; i++)
{
    delete []B[i];
}
delete []B;

2.2 链表向量的声明、使用与遍历（类模板的嵌套）

vector< list<int> > adjacent(N);                          // 创建N个链表组成的向量

adjacent[i].push_back(A[i][j]);
adjacent[i].push_back(j+1);

for (vector< list<int> >::iterator iter_0 = adjacent.begin(); iter_0 != adjacent.end(); iter_0++)
{
	for (list<int>::iterator iter_1 = (*iter_0).begin(); iter_1 != (*iter_0).end(); iter_1++)
	{
		fout << *iter_1 <<" ";
	}
	fout << endl;
}

3. 核心算法

       从左到右、从上到下扫描邻接矩阵的每一个元素，若该元素非0，则：

（1）将1和-1填入关联矩阵的下一列；

（2）在边列表A、B、Z数组中分别填入边的起始点、终止点和权值；

（3）在正向表B、Z数组中分别填入边的终止点和权值；

（4）在邻接表中该行对应的链表后增加一个结点。

       开始扫描一行之前，将当前累计边数加1填入正向表A数组的对应位置。

五、实验结果与分析 

1. 一般情形样例

输入：

输出：

2. 边界情形样例

输入：

输出：

#include<stdio.h>
#include<vector>
#include<list>
using namespace std;

int main()
{
    int N, i=0, j=0, aij, M=0;                          // M: edge counter, N: # of nodes
    scanf_s("%d", &N);
    int **A = new int*[N];                              // A: input adjacent matrix
    for (i=0; i<N; i++)
    {
        A[i] = new int[N];
    }
    // compute # of edges
    for (i=0; i<N; i++)
    {
        for (j=0; j<N; j++)
        {
            scanf_s("%d", &aij);
            A[i][j] = aij;
            if(aij!=0)
            {
                M++;
            }
        }
    }
    // initialize
    int *Ae = new int[M]();
	int *Be = new int[M]();
	int *Ze = new int[M]();                         // 边列表
    int *Ap = new int[N+1]();                                 // 正向表
    int *Bp = new int[M](); 
	int *Zp = new int[M]();                              // 正向表
    int **B = new int*[N]();                                  // 关联矩阵
    for (i=0; i<N; i++)
    {
        B[i] = new int[M]();
    }
    vector< list<int> > adjacent(N);                          // 邻接表
    // compute parameters
    int cnt=0;
    Ap[0] = 1;
    Ap[N] = M+1;
    for (i=0; i<N; i++)
    {
        Ap[i] = cnt+1;
        for (j=0; j<N; j++)
        {
            if(A[i][j]!=0)
            {
                B[i][cnt] = 1;
                B[j][cnt] = -1;
                Ae[cnt] = i+1;
                Be[cnt] = j+1;
                Ze[cnt] = A[i][j];
                Bp[cnt] = j+1;
                Zp[cnt] = A[i][j];
                adjacent[i].push_back(A[i][j]);
                adjacent[i].push_back(j+1);
                cnt++;
            }
        }
    }
    // output
    // 关联矩阵
    for (i=0; i<N; i++)
    {
        for (j=0; j<M; j++)
        {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }

    // 边列表
    for (i=0; i<M; i++)
    {
        printf("%d ", Ae[i]);
    }
    printf("\n");
    for (i=0; i<M; i++)
    {
        printf("%d ", Be[i]);
    }
    printf("\n");
    for (i=0; i<M; i++)
    {
        printf("%d ", Ze[i]);
    }
    printf("\n");

    // 正向表
    for (i=0; i<N+1; i++)
    {
        printf("%d ", Ap[i]);
    }
    printf("\n");
    for (i=0; i<M; i++)
    {
        printf("%d ", Bp[i]);
    }
    printf("\n");
    for (i=0; i<M; i++)
    {
        printf("%d ", Zp[i]);
    }
    printf("\n");

    // 邻接表
    for (vector< list<int> >::iterator iter_0 = adjacent.begin(); iter_0 != adjacent.end(); iter_0++)
    {
        for (list<int>::iterator iter_1 = (*iter_0).begin(); iter_1 != (*iter_0).end(); iter_1++)
        {
            printf("%d ", *iter_1);
        }
        printf("\n");
    }
    // free memory
    delete []Ae;
    delete []Be;
    delete []Ze;
    delete []Ap;
    delete []Bp;
    delete []Zp;
    for (i=0; i<N; i++)
    {
        delete []B[i];
    }
    delete []B;
    return 0;
}