数据结构:

 1 typedef struct ArcNode{
 2 int adjvex;    //该弧所指向的顶点位置
 3 struct ArcNode* next;    //指向下一条弧的指针
 4 } ArcNode;
 5
 6 typedef struct VNode {
 7 int data;    //顶点信息,标号,int类型
 8 ArcNode* first;    //指向第一条关联弧
 9 } VNode, AdjList[MAX_VERTEX_NUM];
10
11 typedef struct {
12 AdjList vertices;    //邻接表
13 int vexnum, arcnum;    //顶点和弧的个数
14 }AdjListGraph;

 上图顶点集:

举例:

将邻接表示的图转为邻接矩阵(无向无权图)

 1 #include <iostream>
 2 using namespace std;
 3
 4 #define MAX_VERTEX_NUM  10    //最大顶点数
 5 #define MAX_ARCNODE_NUM 10    //最大边数
 6
 7 typedef struct ArcNode{
 8     int adjvex;                //该弧所指向的顶点位置
 9     struct ArcNode* next;    //指向下一条弧的指针
10 } ArcNode;
11 typedef struct VNode {
12     int data;                //顶点信息,标号,int类型
13     ArcNode* first;            //指向第一条关联弧
14 } VNode, AdjList[MAX_VERTEX_NUM];
15 typedef struct {
16     AdjList vertices;        //邻接表
17     int vexnum, arcnum;        //顶点和弧的个数
18 }AdjListGraph;                //邻接表
19
20 void showInMat(AdjListGraph alg) {
21     int adjList[MAX_ARCNODE_NUM][MAX_ARCNODE_NUM];
22     for (int i = 0; i < alg.vexnum; i++) {
23         for (int j = 0; j < alg.vexnum; j++)
24             adjList[i][j] = 0;
25     }
26     ArcNode *temp;
27     for (int i = 0; i < alg.vexnum; i++)
28     {
29         temp = alg.vertices[i].first;
30         while (temp != NULL) {
31             adjList[i][temp->adjvex] = 1;
32             temp = temp->next;
33         }
34     }
35     for (int i = 0; i < alg.vexnum; i++) {
36         for (int j = 0; j < alg.vexnum; j++)
37             cout << adjList[i][j] << '\t';
38         cout << endl << endl;
39     }
40 }
41 int main()
42 {
43     AdjListGraph alg;
44     alg.vexnum = 5;                //顶点0,1,2,3,4
45     alg.arcnum = 4;                //弧数:4
46     alg.vertices[0].data = 0;
47     alg.vertices[1].data = 1;
48     alg.vertices[2].data = 2;
49     alg.vertices[3].data = 3;
50     alg.vertices[4].data = 4;
51
52     ArcNode an[8];
53     an[0].adjvex = 1;
54     an[0].next = NULL;
55     alg.vertices[0].first = an;
56     an[1].adjvex = 0;
57     an[2].adjvex = 2;
58     an[3].adjvex = 3;
59     an[1].next = &an[2];
60     an[2].next = &an[3];
61     an[3].next = NULL;
62     alg.vertices[1].first = &an[1];
63     an[4].adjvex = 1;
64     an[5].adjvex = 4;
65     an[4].next = &an[5];
66     an[5].next = NULL;
67     alg.vertices[2].first = &an[4];
68     an[6].adjvex = 1;
69     an[6].next = NULL;
70     alg.vertices[3].first = &an[6];
71     an[7].adjvex = 2;
72     an[7].next = NULL;
73     alg.vertices[4].first = &an[7];
74
75     showInMat(alg);
76     return 0;
77 }
View Code
12-23 01:31