数据结构学习笔记----【图】邻接矩阵和邻接表转换代码_邻接矩阵转换为邻接表代码

转载参考：https://blog.csdn.net/qwm8777411/article/details/8990718

邻接矩阵–>邻接表

要求

带权 有向图 邻接矩阵表示 转换为 邻接表

INPUT

1.图的节点数、图的边数 m n
2. n*n 矩阵（数字间以空格空开，非零表示权）

OUTPUT

m个结点 则输出m行
对应结点连接情况

SAMPLE

6 10
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 0
0 0 5 0 0 6
0 0 5 0 0 0
3 0 0 0 1 0

0:1 3
1:2
2:0
3:2 5
4:2
5:0 4

代码实现

`# include<stdio.h>
# include <malloc.h>

#include <iostream>
using namespace std;
typedef  int InfoType;
#define MAXV 100    //最大顶点个数
#define INF 32767   //INF 正无穷

//定义邻接矩阵类型
    //顶点
    typedef struct{
         int no;//定点编号
         InfoType info;//顶点其他信息
    }VertexType;//顶点类型
    //图
    typedef struct{
       int edges[MAXV][MAXV];//邻接矩阵
       int vertexNum,arcNum;//顶点数 边数
      VertexType vexs[MAXV];//存放顶点信息
    }MGraph;//图的邻接矩阵类型

//邻接表类型

//表节点类型
    typedef struct ANode{
      int adjvex; //这条弧的终点 <i,j>
      struct ANode *nextarc; //指向下一条边的指针
     InfoType infoType;//相关信息，用于存放权值
    }ArcNode;

//头节点类型
    typedef struct VNode{
        typedef int Vertex;
        Vertex data;//顶点信息
        ArcNode *firstarc;//指向第一条边
        //有趣啊，顺序&结构体
    }VNode;
    typedef VNode AdjList[MAXV];	//AdjList是邻接表类型

    typedef struct{
      AdjList adjList;
      int vertexNum,e;//顶点数和边数
    }ALGraph;

//==============================================
    //邻接矩阵转换成邻接表
    void MatToList(MGraph &M, ALGraph *&A){
        int i,j;
        ArcNode *p;

        //给邻接表分配内存
        A = (ALGraph*)malloc(sizeof(ALGraph));
        //遍历头节点 赋初值
        for(i=0;i<M.vertexNum;i++)
            A->adjList[i].firstarc=NULL;

        //遍历邻接矩阵中的所有元素
        for(i=0;i<M.vertexNum;i++)
            for(j=0;j<i;j++)
                if(M.edges[i][j]!=0) {//存在<i,j>边
                    p=(ArcNode*)malloc(sizeof(ArcNode)); //创建一个新的表结点
                    p->adjvex=j;    //弧的终点为j
                    p->nextarc=A->adjList[i].firstarc; //邻接表： 头节点 表结点；
                    // 新的表结点的链域nextarc存放 之前表结点的地址（在头节点的链域里）
                    A->adjList[i].firstarc=p;//将p接在头节点后面
                }



    }


    //输出邻接矩阵M
    void DispMat(MGraph M)
    {
        int i,j;
        for(i=0;i<M.vertexNum;i++)
            for(j=0;j<M.vertexNum;j++)
                printf("%3d",M.edges[i][j]);
            printf("\n");
    }

    //输出邻接表
    void DispAdj(ALGraph *A)
    {
        int i;
        ArcNode *p;
        for(i=0;i<A->vertexNum;i++)
        {
            p=A->adjList[i].firstarc;
            cout<<i<<":";
            while (p!=NULL)
            {
                cout<<p->adjvex<<"";
                p=p->nextarc;
            }
            printf("\n");
        }
    }


    // main
    int main(){
        int i,j;
        MGraph M;
        ALGraph *A;

        int m,n;
        cin>>n>>m;//n节点数 m边数
        int k[n][n];
        for(int i=0;i<M.vertexNum;i++){
            for(int j=0;j<M.vertexNum;j++){
                cin>>k[i][j];
            }
        }
        M.vertexNum=n;
        M.arcNum=m;

        for(i=0;i<M.vertexNum;i++)
            for(j=0;j<M.vertexNum;j++)
                M.edges[i][j]=k[i][j];

        A=(ALGraph*)malloc(sizeof(ALGraph));
        MatToList(M,A)  ;
        DispAdj(A);
    }
// 输入ok 无显示`
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

重点

   //邻接矩阵转换成邻接表
    void MatToList(MGraph &M, ALGraph *&A){
        int i,j;
        ArcNode *p;

        //给邻接表分配内存
        A = (ALGraph*)malloc(sizeof(ALGraph));
        //遍历头节点 赋初值
        for(i=0;i<M.vertexNum;i++)
            A->adjList[i].firstarc=NULL;

        //遍历邻接矩阵中的所有元素
        for(i=0;i<M.vertexNum;i++)
            for(j=0;j<i;j++)
                if(M.edges[i][j]!=0) {//存在<i,j>边
                    p=(ArcNode*)malloc(sizeof(ArcNode)); //创建一个新的表结点
                    p->adjvex=j;    //弧的终点为j
                    p->nextarc=A->adjList[i].firstarc; //邻接表： 头节点 表结点；
                    // 新的表结点的链域nextarc存放 之前表结点的地址（在头节点的链域里）
                    A->adjList[i].firstarc=p;//将p接在头节点后面
                }



    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

邻接表—>邻接矩阵

void ListToMat(ALGraph *A,MGraph &M)

{	int i;
	ArcNode *p;
	for (i=0;i<A->vertexNum;i++)
	{	p=A->adjlist[i].firstarc;
		while (p!=NULL)
		{	M.edges[i][p->adjvex]=1;
			p=p->nextarc;
		}
	}
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15