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

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

一 ：邻接矩阵存储结构

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] << '	';
    }
    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 << '	';
        }
        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