hnust 1963: 邻接矩阵表示法

hnust 1963: 邻接矩阵表示法

题目描述
输入一个图，用邻接矩阵存储，并实现一些操作。
拷贝下面的代码，按要求完成其中的FirstAdjVex，NextAdjVex和CreateUDG操作，其他地方不得改动。

//邻接矩阵表示图
#include <iostream>
#include <iomanip>
#include <cstdio>
using namespace std;

#define MVNum 100     //最大顶点数
typedef string VerTexType; //假设顶点的数据类型为字符串
typedef int ArcType;             //假设边的权值类型为整型

//------------图的邻接矩阵------------------
typedef struct {
   VerTexType vexs[MVNum];            //顶点表
   ArcType arcs[MVNum][MVNum];      //邻接矩阵
   int vexnum, arcnum;                //图的当前点数和边数
} Graph;

//得到顶点i的数据
VerTexType Vertexdata(const Graph &g, int i)
{
   return g.vexs[i];
}

int LocateVex(const Graph &g, VerTexType v)
{
   //确定点v在G中的位置
   for(int i = 0; i < g.vexnum; ++i)
      if(g.vexs[i] == v)
         return i;
   return -1;
}//LocateVex

int FirstAdjVex(const Graph &g, int v)
{
   //返回v的第一个邻接点编号，没有返回-1
   /****在此下面完成代码***************/


   /***********************************/
}//FirstAdjVex

int NextAdjVex(const Graph &g, int v, int w)
{
   //返回v相对于w的下一个邻接点，没有返回-1
   /****在此下面完成代码***************/


   /***********************************/
}//NextAdjVex

void CreateUDG(Graph &g)
{
   //采用邻接矩阵表示法，创建无向图G
   /****在此下面完成代码***************/


   /***********************************/
}//CreateUDN

void DestroyUDG(Graph &g)
{
   //you should do this
}


//输出邻接矩阵
void PrintUDG(const Graph& g)
{
   int i, j;
   cout << "    ";
   for(i = 0; i < g.vexnum; i++) {
      cout << setw(4) << g.vexs[i] ;
   }
   cout << endl;
   for(i = 0; i < g.vexnum; i++) {
      cout << setw(4) << g.vexs[i];
      for(j = 0; j < g.vexnum; j++) {
         cout << setw(4) << g.arcs[i][j];
      }
      cout << endl;
   }
}

int main()
{
   Graph g;
   CreateUDG(g);
   //输出各个顶点的邻接点
   for(int i = 0; i < g.vexnum; i++) {
      cout << Vertexdata(g, i) << ":";
      for(int w = FirstAdjVex(g, i); w >= 0; w = NextAdjVex(g, i, w)) {
         cout << ' ' << Vertexdata(g, w);
      }
      cout << endl;
   }
   PrintUDG(g);
   DestroyUDG(g);
   return 0;
}//main

输入
输入的第一行是两个整数，分别是图的总顶点数n和总边数e

第二行是n个空格分开的字符串，是顶点的名字，依次对应编号0~n-1。

随后有e行，每行两个空格分开的顶点名字，表示一条边的两个顶点。

具体见样例。

输出
首先输出n行，每行是第i个顶点的邻接顶点。

再输出该图的邻接矩阵。

具体见样例。

样例输入 Copy
8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v7
样例输出 Copy
v1: v2 v3
v2: v1 v4 v5
v3: v1 v6 v7
v4: v2 v8
v5: v2 v8
v6: v3 v7
v7: v3 v6
v8: v4 v5
      v1  v2  v3  v4  v5  v6  v7  v8
  v1   0   1   1   0   0   0   0   0
  v2   1   0   0   1   1   0   0   0
  v3   1   0   0   0   0   1   1   0
  v4   0   1   0   0   0   0   0   1
  v5   0   1   0   0   0   0   0   1
  v6   0   0   1   0   0   0   1   0
  v7   0   0   1   0   0   1   0   0
  v8   0   0   0   1   1   0   0   0

提示
样例对应教材6.5的图G4

解题过程

数组(邻接矩阵)表示法
定义
图没有顺序存储结构，但可以借助二维数组来表示元素间的关系

在无向图的邻接矩阵中，它的特点：
无向图的邻接矩阵是对称的
顶点 i 的度 = 第 i 行/列 中 1 的个数

有向图的邻接矩阵
第 i 行含义：以节点 Vi 为尾的弧(即出度边)
第 i 列含义：以节点 Vi 为头的弧(即入度边)

在有向图的邻接矩阵中，它的特点：
有向图的邻接矩阵可能是不对称的
顶点的出度 = 第 i 行元素之和
顶点的入度 = 第 i 列元素之和
顶点的度 = 第 i 行元素之和 + 第 i 列元素之和
网(即有权图)的邻接矩阵表示法
定义为：A.arcs[i][j] = Wij 存在从 i 顶点到 j 顶点的弧或者边的权，否则 A.arcs[i][j] = 无穷大

邻接矩阵的优缺点
优点：
直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有邻接点(右边直接相连的顶点)
方便计算任一顶点的度(从该点发出的边数为出度，指向该点的边数为入度)
无向图：对应行(或列)非0元素的个数
有向图：对应行非0元素的个数是出度；对应列非0元素的个数是入度

缺点：
不便于增加和删除顶点
浪费空间-存稀疏图(点很多而边很少)有大量无效元素
对稠密图(特别是完全图)还是很合算的
浪费时间-统计稀疏图中一共有多少条边

这段C++代码实现了无向图的创建、遍历和销毁，使用了邻接矩阵来表示图。下面是对代码的详细解析：

1. 头文件和命名空间

• 包含<bits/stdc++.h>，提供标准库支持。
• 使用using namespace std;简化代码。

2. 宏定义和类型定义

• MVNum定义了最大顶点数。
• VerTexType和ArcType分别定义了顶点和边的数据类型。

3. 图结构定义

• Graph结构体定义了图的邻接矩阵表示，包含顶点数组、邻接矩阵以及顶点数和边数。

4. 函数定义

• LocateVex：查找顶点在图中的位置，如果找到则返回索引，否则返回-1。
• FirstAdjVex：返回顶点的第一个邻接点的索引，如果没有邻接点则返回-1。
• NextAdjVex：返回顶点相对于给定邻接点的下一个邻接点的索引，如果没有则返回-1。

5. 图的创建函数CreateUDG

• 读取顶点数和边数。
• 读取顶点信息并存储到顶点数组中。
• 循环读取边的信息，使用LocateVex找到顶点的索引，并在邻接矩阵中相应位置设置边的信息。

6. 图的销毁函数DestroyUDG

• 使用memset将邻接矩阵的所有元素设置为0，销毁图。

7. 图的输出函数PrintUDG

• 输出图的邻接矩阵，格式化输出顶点和对应的邻接点。

8. 主函数main

• 创建图g并调用CreateUDG函数。
• 遍历所有顶点，输出每个顶点及其邻接点。
• 调用PrintUDG函数输出整个图的邻接矩阵。
• 调用DestroyUDG函数销毁图。

代码逻辑分析

• 代码首先定义了图的数据结构和相关操作函数。
• 使用CreateUDG函数根据用户输入创建图。
• 使用FirstAdjVex和NextAdjVex函数遍历每个顶点的邻接点。
• 使用PrintUDG函数输出图的邻接矩阵，以便于观察。
• 最后，使用DestroyUDG函数清理图占用的资源。

潜在问题

• CreateUDG函数中，如果输入的边信息中顶点不在顶点数组中，程序将不会报错，但这些顶点不会在图中表示。
• DestroyUDG函数中，只销毁了邻接矩阵的数据，没有销毁顶点数组。

改进建议

• 在CreateUDG函数中添加对输入边的顶点是否存在的检查。
• 考虑动态分配顶点数组和邻接矩阵的内存，并在DestroyUDG函数中释放这些内存。
• 考虑添加更多图操作的函数，如搜索、路径查找等。
• 考虑使用std::vector来代替固定大小的数组，以提高代码的灵活性和安全性。

部分代码

typedef struct
{
    VerTexType vexs[MVNum];            //顶点表,用以存储顶点
    ArcType arcs[MVNum][MVNum];      //邻接矩阵
    int vexnum, arcnum;                //图的当前点数和边数
} Graph;

int LocateVex(const Graph &g, VerTexType v)
{
    //确定点v在G中顶点表的位置
    for(int i = 0; i < g.vexnum; ++i)
        if(g.vexs[i] == v)
            return i;
    return -1;
}//LocateVex

int FirstAdjVex(const Graph &g, int v)
{
    //返回顶点v的第一个邻接点编号，没有返回-1
    /****在此下面完成代码***************/
    for(int i=0; i<g.vexnum; i++)if(g.arcs[v][i])return i;
    return -1;
    /***********************************/
}//FirstAdjVex
  

int NextAdjVex(const Graph &g, int v, int w)
{
    //返回顶点v相对于w的下一个邻接点，没有返回-1
    /****在此下面完成代码***************/
    for(int i=w+1; i<g.vexnum; i++)if(g.arcs[v][i])return i;
    return -1;
    /***********************************/
}//NextAdjVex

void CreateUDG(Graph &g)
{
    //采用邻接矩阵表示法，创建无向图G
    /****在此下面完成代码***************/
    cin>>g.vexnum>>g.arcnum;
    for(int  i=0; i<g.vexnum; i++)cin>>g.vexs[i];
    while(g.arcnum--)
    {
        string x1,x2;
        cin>>x1>>x2;
        int m=LocateVex(g,x1),n=LocateVex(g,x2);
        if(m!=-1&&n!=-1)g.arcs[m][n]=g.arcs[n][m]=1;
    }
  
  
    /***********************************/
}//CreateUDN

void DestroyUDG(Graph &g)
{
    memset(g.arcs,0,sizeof(g.arcs));
}
  

//输出邻接矩阵
void PrintUDG(const Graph& g)
{
    int i, j;
    cout << "    ";
    for(i = 0; i < g.vexnum; i++)
    {
        cout << setw(4) << g.vexs[i] ;
    }
    cout << endl;
    for(i = 0; i < g.vexnum; i++)
    {
        cout << setw(4) << g.vexs[i];
        for(j = 0; j < g.vexnum; j++)
        {
            cout << setw(4) << g.arcs[i][j];
        }
        cout << endl;
    }
}

AC代码

#include<bits/stdc++.h>
using namespace std;
  
#define MVNum 100     //最大顶点数
typedef string VerTexType; //假设顶点的数据类型为字符串
typedef int ArcType;             //假设边的权值类型为整型
  
//------------图的邻接矩阵------------------
typedef struct
{
    VerTexType vexs[MVNum];            //顶点表,用以存储顶点
    ArcType arcs[MVNum][MVNum];      //邻接矩阵
    int vexnum, arcnum;                //图的当前点数和边数
} Graph;
int LocateVex(const Graph &g, VerTexType v)
{
    //确定点v在G中顶点表的位置
    for(int i = 0; i < g.vexnum; ++i)
        if(g.vexs[i] == v)
            return i;
    return -1;
}//LocateVex
  
int FirstAdjVex(const Graph &g, int v)
{
    //返回顶点v的第一个邻接点编号，没有返回-1
    /****在此下面完成代码***************/
    for(int i=0; i<g.vexnum; i++)if(g.arcs[v][i])return i;
    return -1;
    /***********************************/
}//FirstAdjVex
  
int NextAdjVex(const Graph &g, int v, int w)
{
    //返回顶点v相对于w的下一个邻接点，没有返回-1
    /****在此下面完成代码***************/
    for(int i=w+1; i<g.vexnum; i++)if(g.arcs[v][i])return i;
    return -1;
    /***********************************/
}//NextAdjVex
  
void CreateUDG(Graph &g)
{
    //采用邻接矩阵表示法，创建无向图G
    /****在此下面完成代码***************/
    cin>>g.vexnum>>g.arcnum;
    for(int  i=0; i<g.vexnum; i++)cin>>g.vexs[i];
    while(g.arcnum--)
    {
        string x1,x2;
        cin>>x1>>x2;
        int m=LocateVex(g,x1),n=LocateVex(g,x2);
        if(m!=-1&&n!=-1)g.arcs[m][n]=g.arcs[n][m]=1;
    }
  
  
    /***********************************/
}//CreateUDN
  
void DestroyUDG(Graph &g)
{
    memset(g.arcs,0,sizeof(g.arcs));
}
  
  
//输出邻接矩阵
void PrintUDG(const Graph& g)
{
    int i, j;
    cout << "    ";
    for(i = 0; i < g.vexnum; i++)
    {
        cout << setw(4) << g.vexs[i] ;
    }
    cout << endl;
    for(i = 0; i < g.vexnum; i++)
    {
        cout << setw(4) << g.vexs[i];
        for(j = 0; j < g.vexnum; j++)
        {
            cout << setw(4) << g.arcs[i][j];
        }
        cout << endl;
    }
}
  
int main()
{
    Graph g;
    CreateUDG(g);
    //输出各个顶点的邻接点
    for(int i = 0; i < g.vexnum; i++)
    {
        cout << g.vexs[i] << ":";
        for(int w = FirstAdjVex(g, i); w >= 0; w = NextAdjVex(g, i, w))
        {
            cout << ' ' << g.vexs[w];
        }
        cout << endl;
    }
    PrintUDG(g);
    DestroyUDG(g);
    return 0;
}