数据结构-使用邻接矩阵创建无向图

野性酷女 2022-12-25 11:51 206阅读 0赞

## 1.邻接矩阵 ##

邻接矩阵（Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

## 2.程序分析 ##

W i,j表示边上的权值；∞表示计算机允许的，大于所有边权值的数。

用邻接矩阵表示法表示图，除了用一个存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。

//采用邻接矩阵表示法创建无向网
    
    #include <iostream>
    using namespace std;
    
    #define MaxInt 32767                    	//表示极大值，即∞
    #define MVNum 100                       	//最大顶点数
    #define OK 1	
     						
    typedef char VerTexType;              		//假设顶点的数据类型为字符型 
    typedef int ArcType;                  		//假设边的权值类型为整型 
    
    //- - - - -图的邻接矩阵存储表示- - - - -
    typedef struct{
         
    	VerTexType vexs[MVNum];            		//顶点表 
    	ArcType arcs[MVNum][MVNum];      		//邻接矩阵 
    	int vexnum,arcnum;                		//图的当前点数和边数 
    }AMGraph;

## 3.采用邻接矩阵表示法创建无向网 ##

算法步骤：

1.  输入总顶点数和总边数
2.  依次输入点的信息存入顶点表中
3.  初始化邻接矩阵，使得每个权值初始化为极大值
4.  构造邻接矩阵

## 4.如何构造邻接矩阵 ##

依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后，是相应的边赋予相应的权值，同时使其对称边赋予相同的权值。

## 5.如何确定顶点位置 ##

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

## 6.完整代码 ##

#include <iostream>
    using namespace std;
    
    #define MaxInt 32767  //表示极大值
    #define MVNum 100 //最大顶点数
    #define OK 1
    typedef char VerTexType;//顶点数据类型为字符型
    typedef int  ArcType;//权值为整形
    typedef int  Status;//定义返回值类型
    //定义结构体
    typedef struct{
        
        //顶点表
        VerTexType vexs[MVNum];
        //邻接矩阵
        ArcType arcs[MVNum][MVNum];
        //当前顶点数和边数
        int vexnum,arcnum;
    }AMGraph;
    //确定顶点位置
    Status LocateVer(AMGraph G,VerTexType v){
        
        for (int i = 0; i < G.vexnum; ++i) {
        
            if (G.vexs[i]==v){
        
                return i;
            }
        }
        return -1;
    }
    //采用邻接矩阵创建无向图
    Status CreateUDN(AMGraph &G){
        
        int i,j,k;
        //1.输入总顶点数和总边数
       // cout<<"please input the vexnum and the arcnum:"<<endl;
       cout<<"1.输入总顶点数和总边数"<<endl;
        cin>>G.vexnum;
        cin>>G.arcnum;
        //2.依次输入点的信息存入顶点表中
        cout<<"2.依次输入点的信息存入顶点表中"<<endl;
        for ( i = 0; i < G.vexnum; ++i) {
        
            cin>>G.vexs[i] ;
        }
        //3.初始化邻接矩阵，使每个权值初始化为最大值
        cout<<"3.初始化邻接矩阵，使每个权值初始化为最大值"<<endl;
        for (i  = 0; i < G.vexnum; ++i) {
        
            for ( j = 0; j < G.vexnum; ++j) {
        
                G.arcs[i][j]=MaxInt;
            }
        }
        //4.构造邻接矩阵,依次输入每条边依附的顶点和权值
        cout<<"4.构造邻接矩阵,依次输入每条边依附的顶点和权值"<<endl;
        for ( k = 0; k < G.arcnum; ++k) {
        
            //1.定义两个顶点和边的权值
            VerTexType v1,v2;
            ArcType w;
            cout<<"Please enter the vertex and weight of each edge in turn:"<<endl;
            cin>>v1>>v2>>w;
            //2.确定两个顶点在图中的位置
            i=LocateVer(G,v1);
            j=LocateVer(G,v2);
            //3.两个顶点之间的权值
            G.arcs[i][j]=w;
            //4.无向图邻接矩阵权值对称
            G.arcs[j][i]=G.arcs[i][j];
    
    
        }
        return OK;
        cout<<endl;
    }
    
    int main() {
        
        cout<<"----------------Use the Adjacency Matrix CreateUDN------------"<<endl;
        AMGraph G;
        CreateUDN(G);
        cout<<"----------------Show the Adjacency Matrix---------------------"<<endl;
        for (int i = 0; i < G.vexnum; ++i) {
        
            for (int j = 0; j < G.vexnum; ++j) {
        
                if (j!=G.vexnum-1){
        
                    if (G.arcs[i][j]!=MaxInt){
        
                        cout<<G.arcs[i][j]<<"\t";
                    } else{
        
                        cout << "∞" << "\t";
                    }
                }else{
        
                    if(G.arcs[i][j]!=MaxInt){
        
                        cout<<G.arcs[i][j]<<endl;
                    } else{
        
                        cout << "∞" <<endl;
                    }
                }
    
            }
    
        }
        cout<<endl;
        return 0;
    }

## 7.运行结果 ##

验证无向图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70]  
注：原无向图来自百度百科

----------------Use the Adjacency Matrix CreateUDN------------
    1.输入总顶点数和总边数
    6 9
    2.依次输入点的信息存入顶点表中
    a b c d e f
    3.初始化邻接矩阵，使每个权值初始化为最大值
    4.构造邻接矩阵,依次输入每条边依附的顶点和权值
    Please enter the vertex and weight of each edge in turn:
    a b 1
    Please enter the vertex and weight of each edge in turn:
    a c 2
    Please enter the vertex and weight of each edge in turn:
    a d 3
    Please enter the vertex and weight of each edge in turn:
    b e 4
    Please enter the vertex and weight of each edge in turn:
    c d 5
    Please enter the vertex and weight of each edge in turn:
    c e 6
    Please enter the vertex and weight of each edge in turn:
    c f 7
    Please enter the vertex and weight of each edge in turn:
    d f 8
    Please enter the vertex and weight of each edge in turn:
    e f 9
    ----------------Show the Adjacency Matrix---------------------
    ∞      1       2       3       ∞      ∞
    1       ∞      ∞      ∞      4       ∞
    2       ∞      ∞      5       6       7
    3       ∞      5       ∞      ∞      8
    ∞      4       6       ∞      ∞      9
    ∞      ∞      7       8       9       ∞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70]: /images/20221120/0dc7eab4e8ce40ffb482798c8914022d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/c2d6f31bca9f49e7b02125ee9f4d4aa3.png