首页 > > 程序设计 > C/C++ >

图的两种存储结构及四种形态——邻接矩阵、邻接…

2019-08-16 07:58:15来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

图的两种存储结构及四种形态——邻接矩阵、邻接表；有向图、无向图、有向网、无向网。

Posted on 2019-08-04 17:12 水龙头 阅读(...) 评论(...) 编辑 收藏

声明： 代码中有大量的注释，所以此处就不再作出大量的解释了。

一 ：邻接矩阵存储结构

1.首先是各种类型与宏的定义：

 1 #include <iostream>
 2 using namespace std;
 3 //无穷大
 4 #define INFINITY INT_MAX
 5 //最大顶点个数
 6 #define MAX_VERTEX_NUM 20
 7 //顶点类型
 8 typedef char VertexType;
 9 typedef int VRType;
10 typedef char infoType;
11  //图的四种类型
12 typedef enum {DG = 1, DN, UDG, UDN} GraphKind;
13 
14 //弧的结构体定义
15 typedef struct ArcCell
16 {
17     // 对于网来说是权值；对于图来说就是0或1
18     VRType adj;
19     //该弧相关信息的指针（现在暂且可以理解为字符指针）
20     infoType* info;
21 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
22 
23 //图的结构体定义
24 typedef struct
25 {
26     VertexType vexs[MAX_VERTEX_NUM];
27      //arcs可以先简单地理解为一个数组名
28     AdjMatrix arcs;
29     //当前图中的顶点数和弧数
30     int vexnum, arcnum;
31     //图的种类标志
32     GraphKind kind;
33 }MGraph;
View Code


2.接下来是函数声明及main函数：

void CreateGraph(MGraph &G);
void CreateUDN(MGraph &G);
int LocateVex(MGraph G , int v1);
void CreateUDG(MGraph &G);
void CreateDG(MGraph &G);
void CreateDN(MGraph &G);
void Print(MGraph G);
int main(void)
{
    MGraph G;
    CreateGraph(G);
    return 0;
}
View Code


3.最后就是各种自定义函数的定义了：

void CreateGraph(MGraph &G)
{
    cout << "1、有向图" << endl;
    cout << "2、有向网" << endl;
    cout << "3、无向图" << endl;
    cout << "4、无向网" << endl;
    cout << "你需要创建哪一种类型的图?" << endl;
    //此处运用了强转（不能直接从键盘上给枚举变量赋值）
    cin >> (int&)G.kind;
    switch (G.kind)
    {
        case 1:
            return CreateDG(G);
            break;
        case 2:
            return CreateDN(G);
            break;
        case 3:
            return CreateUDG(G);
            break;
        case 4:
            return CreateUDN(G);
            break;
    }
}
//创建有向网
void CreateDN(MGraph &G)
{
    cout << "该图有多少顶点以及多少条弧?" << endl;
    cin >> G.vexnum  >> G.arcnum;
    cout << "请输入顶点:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        //cin相当于c里面的scanf函数
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.vexnum; i++)
    {
        for(int j = 0; j < G.vexnum; j++)
        {
            //先假设每两个点之间都没有边
            G.arcs[i][j].adj = INFINITY;
        }
    }
    cout << "请输入各弧的两个端点及其权值" << endl;
    VertexType v1, v2;
    //用于暂时存储每条弧的权值
    VRType temp;
    int i, j;
    //有向网不具备对称性
    for(int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2 >> temp;
        //利用存储顶点所用的一维数组中对应点的下标
        i = LocateVex(G, v1), j = LocateVex(G, v2),
        G.arcs[i][j].adj = temp;
    }
    Print(G);
}
//创建有向图
void CreateDG(MGraph &G)
{
    cout << "该图有多少顶点以及多少条边?" << endl;
    cin >> G.vexnum  >> G.arcnum;
    cout << "请输入顶点:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.vexnum; i++)
    {
        for(int j = 0; j < G.vexnum; j++)
        {
            //先假定图中没有弧
            G.arcs[i][j].adj = 0;
        }
    }
    cout << "请输入各弧的两个端点" << endl;
    VertexType v1, v2;
    //用于暂时存储每条弧的'权值'(存在即为1,否则为0)
    //因为temp的取值只能为1或0，所以不需要再输入
    VRType temp = 1;
    int i, j;
    //有向图不具备对称性
    for(int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2;
        i = LocateVex(G, v1), j = LocateVex(G, v2),
        G.arcs[i][j].adj = temp;
    }
    Print(G);
}
//创建无向图（对称）
void CreateUDG(MGraph &G)
{
    cout << "该图有多少顶点以及多少条边?" << endl;
    cin >> G.vexnum  >> G.arcnum;
    cout << "请输入顶点:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.vexnum; i++)
    {
        for(int j = 0; j < G.vexnum; j++)
        {
            //先假设每两个点之间都没有边
            G.arcs[i][j].adj = 0;
        }
    }
    cout << "请输入各弧的两个端点(下三角)" << endl;
    VertexType v1, v2;
    VRType temp = 1;
    int i, j;
    //考虑到无向图具有对称性（先只输入(邻接矩阵)下三角里存在的边）
    for(int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2;
        i = LocateVex(G, v1), j = LocateVex(G, v2),
        G.arcs[i][j].adj = temp;
        //将上三角里的每条弧同样添加上权值
        G.arcs[j][i].adj = G.arcs[i][j].adj;
    }
    Print(G);
}
//创建无向网（对称）
void CreateUDN(MGraph &G)
{
    cout << "该图有多少顶点以及多少条边?" << endl;
    cin >> G.vexnum  >> G.arcnum;
    cout << "请输入顶点:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.vexnum; i++)
    {
        for(int j = 0; j < G.vexnum; j++)
        {
            //先假设每两个点之间都没有边(无穷远)
            G.arcs[i][j].adj = INFINITY;
        }
    }
    cout << "请输入各弧的两个端点及其权值(下三角)" << endl;
    VertexType v1, v2;
    VRType temp;
    int i, j;
    //考虑到无向图具有对称性（先只输入(邻接矩阵)下三角里存在的边）
    for(int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2 >> temp;
        i = LocateVex(G, v1), j = LocateVex(G, v2),
        G.arcs[i][j].adj = temp;
        //将上三角里的每条弧同样添加上权值
        G.arcs[j][i].adj = G.arcs[i][j].adj;
    }
    Print(G);
}
 //返回该顶点在一维数组中的下标（当然每一个人创建的一维数组可以是不同的）
int LocateVex(MGraph G , int v1)
{
    for(int i = 0; i < G.vexnum; i++)
    {
        if(G.vexs[i] == v1)
            return i;
    }
}
void Print(MGraph G)
{
    cout << "存储的一维数组如下:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        cout << G.vexs[i] << '\t';
    }
    cout << endl;
    cout << "邻接矩阵如下:" << endl;
    for(int i = 0; i < G.vexnum; i++)
    {
        for(int j = 0; j < G.vexnum; j++)
        {
            cout << G.arcs[i][j].adj << '\t';
        }
        cout << endl;
    }
}
View Code


二 ：邻接表存储结构

  1 #include <iostream>
  2 #include <string>
  3 using namespace std;
  4 using std :: string;
  5 typedef string InforType;
  6 //顶点类型
  7 typedef char VertexType;
  8 typedef int Status;
  9 typedef enum {UDG = 1, DG, UDN, DN} GraphKind;
 10 //最大顶点个数
 11 #define MAX_VERTEX_NUM 20
 12 #define ERROR -1
 13 #define OK 1
 14 //表节点的定义
 15 typedef struct ArcNode
 16 {
 17     //该弧所指向的顶点的位置（相对地址）
 18     int adjvex;
 19     //指向下一条弧的指针
 20     struct ArcNode* nextarc;
 21     //该弧相关信息的指针（例如权值）
 22     InforType info;
 23 }ArcNode;
 24 //头节点的定义
 25 typedef struct VNode
 26 {
 27     //顶点信息
 28     VertexType data;
 29     //指向第一条依附该顶点的弧的指针
 30     ArcNode* firstarc;
 31 }VNode, AdjList[MAX_VERTEX_NUM];
 32 //图的定义
 33 typedef struct
 34 {
 35     //存放头节点的一维数组
 36     AdjList vertices;
 37     //图的当前顶点数和弧数
 38     int vexnum, arcnum;
 39     //图的种类标志
 40     GraphKind kind;
 41 }ALGraph;
 42 void CreateGraph(ALGraph& G);
 43 Status CreateUDN(ALGraph& G);
 44 Status CreateUDG(ALGraph& G);
 45 Status CreateDG(ALGraph& G);
 46 Status CreateDN(ALGraph& G);
 47 int LocateVex(VNode vertices[], int vexnum, VertexType e);
 48 void Print(const ALGraph& G);
 49 int main(void)
 50 {
 51     ALGraph G;
 52     CreateGraph(G);
 53     return 0;
 54 }
 55 void CreateGraph(ALGraph& G)
 56 {
 57     int reply;
 58     cout << "1. 无向图" << endl;
 59     cout << "2. 有向图" << endl;
 60     cout << "3. 无向网" << endl;
 61     cout << "4. 有向网" << endl;
 62     //其实逆与正是差不多的，根本上还是取决于用户的输入
 63     cout << "5. 逆有向网" << endl;
 64     cout << "6. 逆有向图" << endl;
 65     cout << "你想创建哪一种类型的图?" << endl;
 66     cin >> reply;
 67     switch(reply)
 68     {
 69     case 1:
 70         CreateUDG(G);
 71         break;
 72     case 2:
 73         CreateDG(G);
 74         break;
 75     case 3:
 76         CreateUDN(G);
 77         break;
 78     case 4:
 79         CreateDN(G);
 80         break;
 81     case 5:
 82         CreateDN(G);
 83         break;
 84     case 6:
 85         CreateDG(G);
 86         break;
 87     default:
 88         exit(-1);
 89     }
 90 }
 91 //构造无向网
 92 Status CreateUDN(ALGraph& G)
 93 {
 94     VertexType e;
 95     int num;
 96     cout << "该图共有多少个顶点、多少条弧?" << endl;
 97     cin >> G.vexnum >> G.arcnum;
 98     cout << "请输入各顶点:" << endl;
 99     for(int i = 0; i < G.vexnum; i++)
100     {
101         //注意存储结构
102         cin >> G.vertices[i].data;
103         //先将头节点的指针域设为空
104         G.vertices[i].firstarc = NULL;
105     }
106     for(int i = 0; i < G.vexnum; i++)
107     {
108         //(强调引用)
109         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针
110         //所以接连各节点不想以前那样简单了
111         ArcNode* &ptr = G.vertices[i].firstarc;
112         cout << "请问以顶点" << G.vertices[i].data << "为起点的弧一共有多少条?" << endl;
113         cin >> num;
114         if(num > 0)
115         {
116             int Index;
117             ArcNode* p = NULL;
118             cout << "请将这些顶点及弧所带信息依次输入:" << endl;
119             //先处理一个节点（为了方便后面的操作）
120             ptr = new ArcNode;
121             if(ptr)
122             {
123                 cin >> e;
124                 //输入弧上的信息
125                 cin >> ptr->info;
126                 Index = LocateVex(G.vertices, G.vexnum, e);
127                 p = ptr;
128                 p->adjvex = Index;
129                 p->nextarc = NULL;
130             }
131             else
132                 return ERROR;
133             for(int j = 1; j < num; j++)
134             {
135                 ArcNode* ptr2 = new ArcNode;
136                 if(ptr2)
137                 {
138                     //注意各变量的类型，不要搞混了
139                     cin >> e;
140                     //输入弧上的信息
141                     cin >> ptr2->info;
142                     Index = LocateVex(G.vertices, G.vexnum, e);
143                     ptr2->adjvex = Index;
144                     ptr2->nextarc = NULL;
145                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）
146                     p->nextarc = ptr2;
147                     p = p->nextarc;
148                 }
149                 else
150                     return ERROR;
151             }
152         }
153     }
154     Print(G);
155     return OK;
156 }
157 //构造无向图
158 Status CreateUDG(ALGraph& G)
159 {
160     VertexType e;
161     int num;
162     cout << "该图共有多少个顶点、多少条弧?" << endl;
163     cin >> G.vexnum >> G.arcnum;
164     cout << "请输入各顶点:" << endl;
165     for(int i = 0; i < G.vexnum; i++)
166     {
167         //注意存储结构
168         cin >> G.vertices[i].data;
169         //先将头节点的指针域设为空
170         G.vertices[i].firstarc = NULL;
171     }
172     for(int i = 0; i < G.vexnum; i++)
173     {
174         //(强调引用)
175         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针
176         //所以接连各节点不想以前那样简单了
177         ArcNode* &ptr = G.vertices[i].firstarc;
178         cout << "请问以顶点" << G.vertices[i].data << "为起点的弧一共有多少条?" << endl;
179         cin >> num;
180         if(num > 0)
181         {
182             int Index;
183             ArcNode* p = NULL;
184             cout << "请将这些顶点依次输入:" << endl;
185             //先处理一个节点（为了方便后面的操作）
186             ptr = new ArcNode;
187             if(ptr)
188             {
189                 cin >> e;
190                 Index = LocateVex(G.vertices, G.vexnum, e);
191                 p = ptr;
192                 p->adjvex = Index;
193                 p->nextarc = NULL;
194             }
195             else
196                 return ERROR;
197             for(int j = 1; j < num; j++)
198             {
199                 //注意各变量的类型，不要搞混了
200                 cin >> e;
201                 Index = LocateVex(G.vertices, G.vexnum, e);
202                 ArcNode* ptr2 = new ArcNode;
203                 if(ptr2)
204                 {
205                     ptr2->adjvex = Index;
206                     ptr2->nextarc = NULL;
207                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）
208                     p->nextarc = ptr2;
209                     p = p->nextarc;
210                 }
211                 else
212                     return ERROR;
213             }
214         }
215     }
216     Print(G);
217     return OK;
218 }
219 //构造有向图
220 Status CreateDG(ALGraph& G)
221 {
222     VertexType e;
223     int num;
224     cout << "该图共有多少个顶点、多少条弧?" << endl;
225     cin >> G.vexnum >> G.arcnum;
226     cout << "请输入各顶点:" << endl;
227     for(int i = 0; i < G.vexnum; i++)
228     {
229         //注意存储结构
230         cin >> G.vertices[i].data;
231         //先将头节点的指针域设为空
232         G.vertices[i].firstarc = NULL;
233     }
234     for(int i = 0; i < G.vexnum; i++)
235     {
236         //(强调引用)
237         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针
238         //所以接连各节点不想以前那样简单了
239         ArcNode* &ptr = G.vertices[i].firstarc;
240         cout << "请问以顶点" << G.vertices[i].data << "为起点的弧一共有多少条?" << endl;
241         cin >> num;
242         if(num > 0)
243         {
244             int Index;
245             ArcNode* p = NULL;
246             cout << "请将这些顶点依次输入:" << endl;
247             //先处理一个节点（为了方便后面的操作）
248             ptr = new ArcNode;
249             if(ptr)
250             {
251                 cin >> e;
252                 Index = LocateVex(G.vertices, G.vexnum, e);
253                 p = ptr;
254                 p->adjvex = Index;
255                 p->nextarc = NULL;
256             }
257             else
258                 return ERROR;
259             for(int j = 1; j < num; j++)
260             {
261                 //注意各变量的类型，不要搞混了
262                 cin >> e;
263                 Index = LocateVex(G.vertices, G.vexnum, e);
264                 ArcNode* ptr2 = new ArcNode;
265                 if(ptr2)
266                 {
267                     ptr2->adjvex = Index;
268                     ptr2->nextarc = NULL;
269                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）
270                     p->nextarc = ptr2;
271                     p = p->nextarc;
272                 }
273                 else
274                     return ERROR;
275             }
276         }
277     }
278     Print(G);
279     return OK;
280 }
281 //构造有向网
282 Status CreateDN(ALGraph& G)
283 {
284     VertexType e;
285     int num;
286     cout << "该图共有多少个顶点、多少条弧?" << endl;
287     cin >> G.vexnum >> G.arcnum;
288     cout << "请输入各顶点:" << endl;
289     for(int i = 0; i < G.vexnum; i++)
290     {
291         //注意存储结构
292         cin >> G.vertices[i].data;
293         //先将头节点的指针域设为空
294         G.vertices[i].firstarc = NULL;
295     }
296     for(int i = 0; i < G.vexnum; i++)
297     {
298         //(强调引用)
299         //注意ptr是节点的指针（是节点类型的一部分）而不是‘指向’节点的指针
300         //所以接连各节点不想以前那样简单了
301         ArcNode* &ptr = G.vertices[i].firstarc;
302         cout << "请问以顶点" << G.vertices[i].data << "为起点的弧一共有多少条?" << endl;
303         cin >> num;
304         if(num > 0)
305         {
306             int Index;
307             ArcNode* p = NULL;
308             cout << "请将这些顶点及弧所带信息依次输入:" << endl;
309             //先处理一个节点（为了方便后面的操作）
310             ptr = new ArcNode;
311             if(ptr)
312             {
313                 cin >> e;
314                 //输入弧上的信息
315                 cin >> ptr->info;
316                 Index = LocateVex(G.vertices, G.vexnum, e);
317                 p = ptr;
318                 p->adjvex = Index;
319                 p->nextarc = NULL;
320             }
321             else
322                 return ERROR;
323             for(int j = 1; j < num; j++)
324             {
325                 ArcNode* ptr2 = new ArcNode;
326                 if(ptr2)
327                 {
328                     //注意各变量的类型，不要搞混了
329                     cin >> e;
330                     //输入弧上的信息
331                     cin >> ptr2->info;
332                     Index = LocateVex(G.vertices, G.vexnum, e);
333                     ptr2->adjvex = Index;
334                     ptr2->nextarc = NULL;
335                     //注意此处的连接节点与以前写的有点不同（ptr‘一直’为空）
336                     p->nextarc = ptr2;
337                     p = p->nextarc;
338                 }
339                 else
340                     return ERROR;
341             }
342         }
343     }
344     Print(G);
345     return OK;
346 }
347 //定位顶点在一维数组中的位置
348 int LocateVex(VNode vertices[], int vexnum, VertexType e)
349 {
350     int i;
351     for(i = 0; i < vexnum; i++)
352     {
353         if(vertices[i].data == e)
354             break;
355     }
356     return i;
357 }
358 //打印图
359 void Print(const ALGraph& G)
360 {
361     cout << "您所创建的图用邻接表存储结构展示如下:" << endl;
362     for(int i = 0; i < G.vexnum; i++)
363     {
364         cout  << "[" << G.vertices[i].data << "]";
365         ArcNode* ptr = G.vertices[i].firstarc;
366         while(ptr)
367         {
368             //打印出下标（从零开始）
369             cout  << "—>" << ptr->adjvex;
370             ptr = ptr->nextarc;
371         }
372         cout << endl;
373     }
374 }
View Code

 


原文链接:https://www.cnblogs.com/ReturnOfTheKing/p/11298827.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：Ural 1250 Sea Burial 题解

下一篇：Ural 1201 Which Day Is It? 题解

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签