数据结构 图论（一）

1.很多定义

             -- 表示多对多关系

             -- 一个图由顶点和边组成

             -- 边又叫做弧

             -- （v,w）表示 v-w 无方向

                         <v,w> 表示从v指向w的单行边

             -- 不考虑重边和回路

             -- 图可以分为有向图和无向图，又可以根据存储方式分为领接矩阵和领接表

             --连通分量：无向图的极大连通子图

             需要满足以下的条件：

                    ---极大顶点数：再加一个顶点就不连通了

                    ---极大边：包含子图中所有顶点相连的所有边

             --强连通：两点之间双向路径

2.在程序中表示图

    方法一：

            -- 最简单的方法就是使用领接矩阵（问题：浪费空间）

            -- 可以通过一维数组来简化存储，从上到下依次存储，省掉了一半的空间，但是会造成查找不好查找

            -- 将数组的值定义为权重

   方法二：

            -- 领接表

3.图的遍历

         --DFS 深度优先搜索

                void DFS(Vertex V)

                {

                        visited[v]=ture;

                        for(V的每个邻结点 w){

                             if（！visted[w]）{

                                       DFS(w);

                             }

                        }

               }

                      解释：从一个顶点开始，向下走，如果有多个顶点，每次选择一个顶点，不断走，如果遇到无路可走，则原路返

                       回，知道返回到有可走路的结点，然后继续从还没有经过的路走，反复如此，直到返回到起始点

                     使用该方法，若有N个顶点，E条边，时间复杂度为：

                                                     邻接表：O(N+E)

                                                     领接矩阵：O(N2)

 

          --BFS广度优先搜索

                  伪代码：

                        void BFS（Vertex V）{ //从V这个顶点开始遍历

                                       visited[V]=true; //先对V进行确认

                                       Enqueue(V,Q); //将V压入队列中

                                       while（！IsEmpty）{

                                                  V=Dequeue(Q); //将队列中的弹出

                                                 for(V的每一个邻接点W）{

                                                             if(!visted[w]){

                                                                    visted[w]=true;

                                                                    Enqueue(V,Q); //将V压入队列中

                                                              }

                                              }

                                        }

                             }

                   队列：头进尾出

                   解释：广度搜索就是从一个顶点开始，先将它的所有邻顶点都遍历了，再依次将其他的顶点遍历。

                   使用该方法，若有N个顶点，E条边，时间复杂度为：

                                                  邻接表：O(N+E)

                                                  领接矩阵：O(N2)

 4.邻接矩阵，领接表的建立

-- 领接矩阵标准创建思路：通常我们需要创建两个结构体，一个结构体用来存储图（它有这个图的属性，顶点数，边数，所表示的矩阵），另一个用来存储表示边（有顶点的坐标表示，权重），因为我们主要是通过矩阵的方式存储这个图，所以存储边的结构体只是一个辅助的，就相当一个中间变量一样，先输入顶点数，通过顶点数来初始化数组，再读入边数，通过边数读入两个不同坐标的信息到表示边的结点中，然后将信息插入进存储图的结构体中的数组中，完成领接矩阵

            领接矩阵也有简单的创建方法，直接不用结构体

           /*领接矩阵的简单创建*/

           #include<stdio.h>

           #define MAXN 100

 

            int G[MAXN][MAXN],Nv,Ne;

            int main(){

                   int i,j,v1,v2,w;

                   scanf("%d",&Nv);

                    //创建

                  for(i=0;i<Nv;i++)

                            for(j=0;j<Nv;j++)

                                       G[i][j]=0;

                  scanf("%d",&Ne);

                    for(i=0;i<Ne;i++){

                             scanf("%d%d%d",&v1,&v2,&w);

                             G[v1][v2]=w;

                               G[v2][v1]=w;

                    }

 

                   for(i=0;i<Nv;i++){

                            for(j=0;j<Nv;j++)

                                     printf("%d",G[i][j]);

                            printf("\n");

                   }

           }

--领接表的标准创建思路：

---准备：

邻接表有四个结构体，首先有一个用来表示图的结构体（顶点数，边数，领接表），领接表所对应的是一个结构体数组，这个结构体数组中存着多条链表，这个数组中有一个用来记录表示节点的头指针，第三个结构体就是用来存需要记录结点的信息的（下一个结点的坐标，边的权重，指向下一个的指针），随后一个结构体就是用来读取边的中间变量，就和领接矩阵中所说的中间变量一样

 

---初始化

首先初始化，给表示图的结点输入要创建的结点，然后让边数都为0，再将该结构体中的领接表所表示的数组的头指针全部为NULL

---插入数据

当创建成功后，就要插入数据，我们每次使用的是头插，假设这里已经将新的中间结构体E变量传进来，我们先开辟新的结点（NE），然后将E中的数据给NE结点，让NE结点的next指向现在该邻接表所对应数组的头指针，最后让该邻接表所对应数组的头指针指向新的结点NE，插入完成（注：如果是无向图，就要用同样的方法再反着插一遍）