GroupBlog

一.邻接表:

1.简介

邻接表是图的链式存储结构，他克服了邻接矩阵的缺点，只存储定点之间有关联的信息，邻接表由边表
和定点表组成，所以它存储的是稀疏图，也就是边数e < nlnn(n为顶点数)，这样相比于邻接矩阵极大
的节省了空间，顶点表用于存放图中每个顶点的信息以及指向该定点边表的头指针，顶点表采用的
是顺序存储结构。边表就是对于针对顶点表中的每一个定点建立链表，来存储与该顶点有关联的所有顶点。

2.经验总结:

1：相当于一个大数组，数组中的每一个元素中都是各自链表的头结点，在初始化时将头结点指向为空。然后根据数组的下标分别在不同的顶点上链接与它有关的节点。
2：对于有n个顶点e条边的无向图，存储时需要n个表头节点和2e个表节点，相比于邻接矩阵几大节省空间。

二.DFS（深度优先搜索）:

1.介绍

深度优先搜索类似于树的先序遍历，尽可能先对纵深的方向进行搜索，基本思想为从图中某一定点V0出发，先访问此节点，然后从V0的某一个未被访问的邻接点出发深度优先搜索遍历全图，直到图中所有与V0有路径相同的顶点都被访问到，若图为连通图，则结束，否则另选一个未访问的节点继续出发。

例如：
这里写图片描述

由A->E->C->D->B
策略：从一个顶点出发，设置顶点是否被访问的标志(可以自定义一个数组来实现)，保证每一个定点只被
访问一次。对于连通图一次DFS就可以将整个图遍历完，而非连通图则需要多次，在下面的代码中DFS函
数根据大数组中顶点元素的下标来输出该节点的信息，然后再输出该顶点链表中与它有关的第一个链表节点
的信息，再由它的下标转到大数组中的顶点处，将它链表中与它有关的第一个链表节点信息输出，如果它的
下一个定点访问过就返回找与它有关的第二个链表节点的信息……直到所有的顶点都访问完。

如果没看懂，就看下面的代码(代码是有向网，而上面例子是有向图，是我不会在箭头上写数，所以请谅解)。

2.代码

/*用邻接表来存储有向网*/
# include<stdio.h>
# include <stdlib.h>


# define Max 10
typedef struct ArcNode{//存放的是链表的节点 
    int adjvex;// 所连接定点的下标 
    int info;//改边所对应的权值 
    struct ArcNode *next;
}ArcNode;

typedef struct VNode{
    char data;//存放的是头定点的信息 
    ArcNode *firstarc;//
}VNode;

typedef struct {
    VNode vertices[Max];
    int vexnum;//存放的是定点的个数 
    int arcnum;//存放的是边的个数 
}ALGraph;
int visited[Max];

int LocateVex(ALGraph G,char u)
{
    int i;
    for (i=0;i<G.vexnum;i++)
    { 
       if(u==G.vertices[i].data) return i;//在存放定点信息的数组中找出该定点的下标 
    }
    if (i==G.vexnum) 
    {
       printf("Error u!\n");exit(1); 
    }
    return 0;
}

void Create(ALGraph &G)
{
    int i, j, k, w;
    char v1,v2,enter;
    ArcNode *p;//创建一个定点 
    printf("请输入顶点数和边数:\n");
    scanf("%d",&G.vexnum);
    scanf("%d",&G.arcnum);
    printf("请输入定点的信息(用大写字母表示):\n"); 
    for (i=0;i<G.vexnum;i++)
    {     scanf("%c%c",&enter,&G.vertices[i].data);//
          G.vertices[i].firstarc=NULL;
    }
    printf("请输入边的信息例如(a,b,w)w为权值\n");//w代表权值
    for (k=0;k<G.arcnum;k++)
     {
        scanf("%c%c",&enter,&v1);
        scanf("%c%c",&enter,&v2);
        scanf("%d",&w);
        i=LocateVex(G,v1);//存放在该单链表的第几个定点 
        j=LocateVex(G,v2);//找到要存放定点的下标 
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;//  要链接定点的下标 
        p->info = w;
        p->next=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p;
    }

}
void DFS(ALGraph &G, int v)
{
   ArcNode *p;  
   printf("%c",G.vertices[v].data);
   visited[v]=1;
   p=G.vertices[v].firstarc;//头结点 
    while (p)
    {  
      if (!visited[p->adjvex])//要确保没有找到的下标 
       DFS(G,p->adjvex);
        p=p->next;
    }
}
void DFSTraverse(ALGraph &G)
{
   for (int v=0;v<G.vexnum;++v)
     visited[v]=0;
   for(int v=0;v<G.vexnum;++v)
    if (!visited[v])
     DFS(G,v);
}

int main(void)
{
   ALGraph G;
   Create(G);//用邻接表表示一个图 
   DFSTraverse(G);//遍历这个邻接表     
   return 0;
 }

3.对上面例子的运行结果

这里写图片描述