《数据结构与算法》——图

luciferzf

图：
1）图是由点的集合和边的集合组成的一个多对多的关系，通常可以表示为G（V，E），其中V是点的集合，E是边的集合，点的集合要求有穷非空
2）简单图：图中不存在顶点到自身的边，并且两个点之间只有一条边
3）无向完全图：任意2个顶点间都存在无向边
4）有向完全图：任意2个顶点间都存在两条方向相反的有向边
5）连通图：图中任意两个点都连通；强连通图则要求任意两个点都存在路径

图的存储结构：
1）我们定义一个一维数组存放顶点，一个二维数组存放边，对于二维数组元素T[a]表示点a和b的关系，若T[a]值为1，表示a和b之间有边，若为0，则无边
2）对于无向图，边的储存数组相当于一个对称矩阵，一个顶点的度等于该顶点在矩阵中对应行的1的个数
3）对于网，储存边的数组中的值不再只是0和1，而是每条边的权，若两个点间不存在边，则定义数组对应元素的值为无穷大（即一个比其他元素值都大的静态值）

邻接表：
首先定义一个顺序表用来存储各个节点，然后利用链表的形式，将各个相邻点在顺序表中的下标依次连接在顺序表里各个点上。对于有向表来说，这样就易于得到点的出度。
十字链表：相比于邻接表，十字链表将出度和入度分开，十字链表的顺序表中的各个点不仅储存了出度的点的下标，还有入度的点的下标，对于有向图，更易于得到入度和出度。
邻接多重表：在边表结构中，我们储存了一条边的两个点的下标，以及分别指向与两个点相邻的另外两条边的指针

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<iostream>
   
4. using namespace std;
   
5. #define N 100
   
6. 
   
7. class edgenode
   
8. {
   
9. public:
   
10.         int index;
    
11.         edgenode *np=NULL;
    
12. 
    
13. };
    
14. 
    
15. class node
    
16. {
    
17. public:
    
18.         char data;
    
19.         int flag = 0;
    
20.         edgenode *np=NULL;
    
21. }vertex[N];
    
22. 
    
23. 
    
24. void Input()
    
25. {
    
26.         int T;
    
27.         cout << "Input vertex:";
    
28.         cin >> T;
    
29.         vertex[0].data = T;
    
30.         for (int i = 1; i < T+1; i++)
    
31.         {
    
32.                 cin >> vertex[i].data;
    
33.         }
    
34.         cout << "Input edges:";
    
35.         cin >> T;
    
36.         for (int i = 1; i < T+1; i++)
    
37.         {
    
38.                 int a, b;
    
39.                 edgenode *cp = NULL;
    
40.                 cin >> a >> b;
    
41.                 if (vertex[a].np == NULL)
    
42.                 {
    
43.                         cp = new edgenode;
    
44.                         vertex[a].np = cp;
    
45.                 }
    
46.                 else
    
47.                 {
    
48.                         cp = vertex[a].np;
    
49.                         while (cp->np != NULL)
    
50.                         {
    
51.                                 cp = cp->np;
    
52.                         }
    
53.                         edgenode *p = cp;
    
54.                         cp = new edgenode;
    
55.                         p->np = cp;
    
56.                 }
    
57.                 cp->index = b;
    
58.         }
    
59. }
    
60. 
    
61. void research()
    
62. {
    
63.         int n = vertex[0].data;
    
64.         for (int i = 1; i <= n; i++)
    
65.         {
    
66.                 edgenode *p=vertex[i].np;
    
67.                 cout << vertex[i].data << "——>" << vertex[p->index].data;
    
68.                 while (p->np != NULL)
    
69.                 {
    
70.                         p = p->np;
    
71.                         cout << "——>" << vertex[p->index].data;
    
72.                 }
    
73.                 cout << endl;
    
74.         }
    
75. }
    
76. 
    
77. int main()
    
78. {
    
79.         Input();
    
80.         research();
    
81.         system("PAUSE");
    
82. }

复制代码