有向图的邻接链表

程序员文章站 2022-05-22 14:35:32

...

这儿是我的笔记，希望大家可以友好交流！！谢谢#__#
参考站上的大神的资料学习，还是很有效的，感觉很好。

图的表示一般有两种方式，邻接矩阵和邻接链表，图本身也有两种有向和无向，先从简单的开始，有向理解了之后，无向图也能很快的写出来了，并且要是输入量较大，邻接矩阵往往会很浪费考空间（稀图），因此邻接矩阵一般适合顶点数较少的情况下。

**图的表示**

struct ListGraph;
typedef struct ListGraph LISTGRAPH;
typedef struct ListGraph* LISTGRAPH_T;

struct VexNode;
typedef struct VexNode VEXNODE;
typedef struct VexNode* VEXNODE_T;

struct Edge_Node;
typedef struct Edge_Node EDGENODE;
typedef struct Edge_Node* EDGENODE_T;

//以下的结构体放在实现文件中
struct ListGraph
{
    int vex_num;
    int edge_num;
    VEXNODE_T vex_hash[MAXNUM_VEX];
};

struct VexNode
{
    char* vex_name;//节点的信息
    EDGENODE_T head;//头插法

};

struct Edge_Node
{
    int vex_index;
    EDGENODE_T next;
};

ListGraph是图结构，包含有当前顶点数，边数，还有一唯的顶点数组，存放顶点结构体变量（这个数组其实可以看成一个特殊的哈希表，只不过这里是顺序存储顶点）；
VexNode 是顶点的结构体，包含顶点的信息（名称等），还有表示边的及结构体（也就是第一个节点，边链表的第一个节点）；
Edge_Node是边的结构体，包含有另一顶点在顶点数组的序号（位置）。

为了条理清晰些，先看简单头文件（只用于生成图，打印图）

/**最大的顶点个数*/
#define MAXNUM_VEX 20

//访问函数指针变量
typedef void (*VisitFun)(char*);
typedef enum
{
    false = 0,
    true,
}bool;
struct ListGraph;
typedef struct ListGraph LISTGRAPH;
typedef struct ListGraph* LISTGRAPH_T;

struct VexNode;
typedef struct VexNode VEXNODE;
typedef struct VexNode* VEXNODE_T;

struct Edge_Node;
typedef struct Edge_Node EDGENODE;
typedef struct Edge_Node* EDGENODE_T;

/***********对于图的基本构成接口************/
LISTGRAPH_T ListGraph_Init(LISTGRAPH_T LG);
bool ListGraph_InsertOneVex(LISTGRAPH_T LG,char* vexname);
bool ListGraph_InsertOneEdge(LISTGRAPH_T LG,char* start_vex,char* end_vex);
int  ListGraph_GetIndexByVexName(LISTGRAPH_T LG,char* vexname);
char*  ListGraph_GetNameByVexIndex(LISTGRAPH_T LG,int vexindex);
EDGENODE_T ListGraph_GetEdgeHeadNode(LISTGRAPH_T LG,char* vexname);

bool ListGraph_DeleteOneVex(LISTGRAPH_T LG,char* vexname);
bool ListGraph_DeleteOneArc(LISTGRAPH_T LG,char* start_vex,char* end_vex);
void ListGraph_DeleteGraph(LISTGRAPH_T LG);

void ListGraph_Printf(LISTGRAPH_T LG);
void LIStGraph_PrintfVex(LISTGRAPH_T LG);
void ListGraph_PrintfEdge(LISTGRAPH_T LG);

基本操作有：（全部的代码后面再粘贴上来）
1：找到顶点的位置，没找到返回-1，否则返回序号
ListGraph_GetIndexByVexName
2：返回顶点的名称信息
ListGraph_GetNameByVexIndex
3：读入一个顶点：
ListGraph_InsertOneVex
只要新加顶点A时不超过最大顶点数以及现有顶点中不含有A（避免重复），就正确加入到后面。
4：读入一条边
ListGraph_InsertOneEdge
先找到起点的顶点的序号，找到对应链表，将包含终点位置信息的边结构体进行插入到链表中（本文中采用头插）
5：删除一个顶点
ListGraph_DeleteOneVex
找到对应顶点的序号index，删除顶点对应的链表（他的为起点的边都要删除），然后将index后面的顶点往移动；最后去删除以该顶点为终点的边，在寻找时要注意所有终点的位置（边结构体中的顶点序号）大于index都要减1。
6：删除一条弧线
ListGraph_DeleteOneArc
这里简单化了，少考虑了一点，就是若起点只有一条出边的话，要删除顶点；所以这里只是删除了终点的边结构体。（从这一点让顶点包含出入度的信息是很重要的，这里也简化了，只是在后续的深度遍历时从头到尾算了一遍入度）

LISTGRAPH_T ListGraph_Init(LISTGRAPH_T LG)
{
    LG = (LISTGRAPH_T)malloc(sizeof(LISTGRAPH));
    if(LG == NULL)
        return NULL;
    memset(LG,0,sizeof(LISTGRAPH));

    return LG;
}
bool ListGraph_InsertOneVex(LISTGRAPH_T LG,char* vexname)
{
    VEXNODE_T newvnode = NULL;
    int m = LG->vex_num + 1;
    if(m == MAXNUM_VEX)
    {
        printf("不能再添加顶点了\n");
        return false;
    }
     m = ListGraph_GetIndexByVexName(LG,vexname);
    if(m != -1)
    {
        printf("出现了相同的顶点,插入顶点失败\n");
        return false;
    }
    //等于-1说明可以加入顶点
    newvnode = (VEXNODE_T)malloc(sizeof(VEXNODE));
    if(newvnode == NULL)
    {
        printf("插入顶点失败\n");
        return false;
    }
    memset(newvnode,0,sizeof(VEXNODE));
    newvnode->vex_name = vexname;
    newvnode->head = NULL;

    LG->vex_hash[LG->vex_num] = newvnode;
    LG->vex_num++;

}
bool ListGraph_InsertOneEdge(LISTGRAPH_T LG,char* start_vex,char* end_vex)
{
    if(LG == NULL)
    {
        printf("ListGraph_InsertOneEdge图是无效的\n",NULL);
        return false;
    }
    int start_index = ListGraph_GetIndexByVexName(LG,start_vex);
    int end_index = ListGraph_GetIndexByVexName(LG,end_vex);

    if(start_index == -1 || end_index == -1)
    {
        printf("插入弧失败\n");
        return false;
    }
    //获取弧线的链表头结点

    LG->vex_hash[start_index]->head = EdgeList_InsertToHead(LG->vex_hash[start_index]->head,end_index);
    LG->edge_num++;
    return true;

}
int  ListGraph_GetIndexByVexName(LISTGRAPH_T LG,char* vexname)
{
    if(LG == NULL)
        return -1;

    int i = 0;
    for( i = 0;i < LG->vex_num;i++)
    {
        if(!strcmp(LG->vex_hash[i]->vex_name,vexname))
        {
            return i;
        }
    }
    return -1;
}
char*  ListGraph_GetNameByVexIndex(LISTGRAPH_T LG,int vexindex)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return NULL;
    }
    return LG->vex_hash[vexindex]->vex_name;
}
EDGENODE_T ListGraph_GetEdgeHeadNode(LISTGRAPH_T LG,char* vexname)
{
    if(LG == NULL)
    {
        printf("ListGraph_InsertOneEdge图是无效的\n",NULL);
        return false;
    }
    int index = ListGraph_GetIndexByVexName(LG,vexname);
    return LG->vex_hash[index]->head;

}

bool ListGraph_DeleteOneVex(LISTGRAPH_T LG,char* vexname)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return false;
    }

    int i = ListGraph_GetIndexByVexName(LG,vexname);
    if(i == -1)
    {
        printf("没有对应的顶点\n");
        return false;
    }
    //删除顶点带的链表
    Edge_DeleteAll(LG,LG->vex_hash[i]->head);
    /**接着要将顶点往前移动*/
    int j = i;
    for(;j < LG->vex_num - 1; j++ )
    {
        LG->vex_hash[j] = LG->vex_hash[j+1];
    }
    LG->vex_hash[j+1] = NULL;

    LG->vex_num--;

    /**************************删除弧线*******************************************/
    for(int k = 0; k < LG->vex_num; k++)
    {
        EDGENODE_T head = LG->vex_hash[k]->head;
        EDGENODE_T prenode = head;/**为了好删除，每次要保留上次的节点*/

        while(head != NULL)//有弧
        {
            if(head->vex_index == i)//是以待删除的顶点为入度
            {
                if(head == LG->vex_hash[k]->head)//节点是第一个节点
                {
                    LG->vex_hash[k]->head = head->next;
                    free(head);
                    head = NULL;
                    LG->edge_num--;
                    break;
                }
                else
                {
                    prenode->next = head->next;
                    free(head);
                    head = NULL;
                    LG->edge_num--;
                    break;
                }
            }
            else//注意要将顶点的位置改变下
            {
                if(head->vex_index > i)
                    head->vex_index--;
                prenode = head;/**保留本次*/
                head = head->next;
            }
        }
    }

    return true;
}
bool ListGraph_DeleteOneArc(LISTGRAPH_T LG,char* start_vex,char* end_vex)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return false;
    }
    int start_index = ListGraph_GetIndexByVexName(LG,start_vex);
    int end_index = ListGraph_GetIndexByVexName(LG,end_vex);

    if(start_index == -1 || end_index == -1)
        return false;

    EDGENODE_T head = LG->vex_hash[start_index]->head;
    EDGENODE_T prenode = head;
    while(head != NULL)
    {
        if(head->vex_index == end_index)
        {
            if(head == LG->vex_hash[start_index]->head)
            {
                LG->vex_hash[start_index]->head = head->next;
                free(head);
                head = NULL;
                LG->edge_num--;
                break;
            }
            else
            {
                prenode->next = head->next;
                free(head);
                head = NULL;
                LG->edge_num--;
                break;
            }
        }
        else
        {
            prenode = head;
            head = head->next;
        }
    }
}
void LIStGraph_PrintfVex(LISTGRAPH_T LG)
{
    printf("图现在有多少个%d顶点\n",LG->vex_num);
    for(int i = 0; i <LG->vex_num ; i++)
    {
        printf("顶点%d:%s\t",i,LG->vex_hash[i]->vex_name);
    }
    printf("\n");
}
void ListGraph_PrintfEdge(LISTGRAPH_T LG)
{
    printf("图现在有%d条边\n",LG->edge_num);

    for(int i = 0; i <LG->vex_num ; i++)
    {
        EDGENODE_T head = ListGraph_GetEdgeHeadNode(LG,LG->vex_hash[i]->vex_name);
        EDGENODE_T  p = head;
        while(p!=NULL)
        {
           printf("(%s %s)\t",LG->vex_hash[i]->vex_name,ListGraph_GetNameByVexIndex(LG,p->vex_index));
           p = p->next;
        }
    }
    printf("\n");
}
void ListGraph_Printf(LISTGRAPH_T LG)
{
    LIStGraph_PrintfVex(LG);
    ListGraph_PrintfEdge(LG);
}
void ListGraph_DeleteGraph(LISTGRAPH_T LG)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return ;
    }
    int n = LG->vex_num;
    for(int i = 0; i < n; i++)
    {
        Edge_DeleteAll(LG,LG->vex_hash[i]->head);
        LG->vex_hash[i]->head = NULL;
    }
    free(LG->vex_hash);
    free(LG);
}

加入深度优先和广度优先搜索
图的深度优先搜索有点像树的先序遍历,广度优先遍历又有点像树的按层次遍历需要借助辅助队列，因此深度优先搜索可以用递归也可以不用，则需要另外需要辅助栈。

另外有个结构经常用到以队列为例：

//或许外面还会有个循环
EnQueue（queue,data）;
while(!Queue_Isempty(queue))
{
    DeQueue(queue);
    //得到出来的元素判断处理

    //其他判断
    EnQueue(queue);
}

【深度优先搜索】：
（表现为从一个顶点A触发，若有边则到第一个领接顶点B，又到B处得到B的第一个领接顶点；相反，广度优先搜索时，基本会按链表方向的）
首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。

1：驱动函数（需要借助辅助数组）
void ListGraph_DFSTranverse(LISTGRAPH_T LG,VisitFun visit);
2：搜索的递归函数（也先不要辅助数组，所以定义为全局变量）
void ListGraph_DFS(LISTGRAPH_T LG ,VisitFun visit,int index);

void ListGraph_DFSTranverse(LISTGRAPH_T LG,VisitFun visit)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return ;
    }
    for(int i = 0;i < MAXNUM_VEX; i++)
    {
        visited[i] = 0;
    }
    for(int i = 0; i < LG->vex_num; i++)
    {
        if(!visited[i])//未访问过的话
        {
            ListGraph_DFS(LG,visit,i);
        }
    }
}
void ListGraph_DFS(LISTGRAPH_T LG ,VisitFun visit,int index)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return ;
    }
    char* data = LG->vex_hash[index]->vex_name;
    visit(data);
    visited[index] = 1;//置访问标志

    EDGENODE_T head = LG->vex_hash[index]->head;
    //找一个没有访问过的顶点进行递归
    if(head != NULL && !visited[head->vex_index])
        ListGraph_DFS(LG,visit,head->vex_index);
}

【广度优先搜索】
1、从图中某个顶点V0出发，并访问此顶点；
2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
类似与层次遍历，会将V0的所有第一个领接顶点访问完，才会去访问第二个层次，要借助辅助队列

辅助队列部分，当然可以也可以用数组，不用这个链式队列

struct QueueNode
{
    int vex_index;
    struct QueueNode* next;
};
struct ListQueue
{
    struct QueueNode* front;
    struct QueueNode* rear;
};
LISTQUEUE_T ListQueue_Init(LISTQUEUE_T LQ)
{
    LQ = (LISTQUEUE_T)malloc(sizeof(LISTQUEUE));
    if(LQ == NULL)
        return NULL;
    LQ->front = LQ->rear = (QUEUENODE_T)malloc(sizeof(QUEUENODE));
    if(LQ->front == NULL)
    {
        free(LQ);
        return NULL;
    }
    LQ->front->next = LQ->rear->next = NULL;
    return LQ;
}
bool ListQueue_IsEmpty(LISTQUEUE_T LQ)
{
    if(LQ != NULL)
        return LQ->front->next == NULL ? true : false;
    else
        return false;
}
bool ListQueue_EnQueue(LISTQUEUE_T LQ,int data)
{
    if(LQ == NULL)
        return false;
    QUEUENODE_T newnode = (QUEUENODE_T)malloc(sizeof(QUEUENODE));
    if(newnode == NULL)
        return false;
    newnode -> next = NULL;
    newnode->vex_index = data;

    LQ->rear->next = newnode;
    LQ->rear = newnode;
    return true;
}
bool ListQueue_DeQueue(LISTQUEUE_T LQ,int* data)
{
    if(LQ == NULL || ListQueue_IsEmpty(LQ))
        return false;

        *data = LQ->front->next->vex_index;
        QUEUENODE_T tmp = LQ->front->next;
        LQ->front->next = tmp->next;

        free(tmp);
        tmp = NULL;
        if(ListQueue_IsEmpty(LQ))
        {
            LQ->rear = LQ->front;
        }
        return true;
}

搜索实现部分：

void ListGraph_BFSTranverse(LISTGRAPH_T LG,VisitFun visit)
{
    if(LG == NULL)
    {
        printf("图是无效的NULL\n");
        return ;
    }

    for(int i = 0; i < MAXNUM_VEX;i++)
        visited[i] = 0;

    LISTQUEUE_T queue = ListQueue_Init(queue);
    char* data = NULL;
    //也保证从顺序进行，若是连通图，则可以i=0就可以遍历完
    for(int i = 0; i < LG->vex_num;i++)
    {
        if(!visited[i])
        {
            ListQueue_EnQueue(queue,i);
            data= LG->vex_hash[i]->vex_name;
            visit(data);//访问
            visited[i] = 1;//置访问标志

            while(!ListQueue_IsEmpty(queue))
            {
                int index = ListQueue_DeQueue(queue,&index);
              /**要找index所在那条链表相对index的下一个领接顶点*/
                EDGENODE_T head = LG->vex_hash[index]->head;

                while(head != NULL)
                {
                    //用辅助数组表示没找到
                    if(visited[head->vex_index])
                    {
                        head = head->next;
                    }
                    //找到了领接点
                    else
                    {
                        ListQueue_EnQueue(queue,head- >vex_index);
                         data = LG->vex_hash[head->vex_index]->vex_name;
                        visit(data);
                        visited[head->vex_index] = 1;
                    }

                }

            }
        }
    }

}

【拓展排序】
拓展排序适用于有向无环图，访问的顺序一定是起点在前，终点在后，若有ABCD顶点，A->B，C->B,C->D，则访问是ACBD。

思想：将途中没有入度为0的顶点入队1，再出队得到队首顶点V将V放入结果队列2中，将v的所有领接边的入度减去1，此时减的过程中判断入度为0的话就入队。

/**用于有向图的拓补排序*/
void ListGraph_TuoBuSort(LISTGRAPH_T LG,char** vexnode)
{   /**辅助队列，压入入度为0的顶点*/
    LISTQUEUE_T queue = ListQueue_Init(queue);

    int Rudu[MAXNUM_VEX] = {0};
    /**统计各个顶点的入度正确*/
    for(int i = 0; i < LG->vex_num; i++)
    {
        EDGENODE_T head = LG->vex_hash[i]->head;

        while (head != NULL)
        {
            Rudu[head->vex_index]++;
            head = head->next;
        }
    }
    printf("\n");
    int index = 0;
    int res_index = 0;
    char* result[MAXNUM_VEX] = {0};

    for(int i = 0; i < LG->vex_num; i++)
    {
        if(Rudu[i] == 0)
        {
            ListQueue_EnQueue(queue,i);
            while(!ListQueue_IsEmpty(queue))
            {

                ListQueue_DeQueue(queue,&res_index);
                vexnode[index++] = LG->vex_hash[res_index]->vex_name;
                EDGENODE_T head = LG->vex_hash[res_index]->head;

                while(head != NULL)
                {
                    Rudu[head->vex_index]--;/**所有这个顶点相关的点入度都-1*/

                    if(Rudu[head->vex_index] != 0)
                    {
                        head = head->next;
                    }
                    else
                    {
                        ListQueue_EnQueue(queue,head->vex_index);
                    }
                }
            }
        }
    }


}

还有行文中关于链表的部分

bool EdgeList_IsEmpty(EDGENODE_T head)
{
    if(head == NULL)
        return true;
    return false;
}
EDGENODE_T EdgeList_InsertToHead(EDGENODE_T head,int index)
{
    EDGENODE_T newedgenode= (EDGENODE_T )malloc(sizeof(EDGENODE));
    if(newedgenode == NULL)
        return NULL;
    memset(newedgenode,0,sizeof(EDGENODE));
    newedgenode->vex_index = index;
    newedgenode->next = NULL;

    if(EdgeList_IsEmpty(head))
    {
        head = newedgenode;
        return head;
    }
    //EDGENODE_T tmp = head;
    newedgenode->next = head;
    head = newedgenode;
    //head->next = newedgenode;
    return head;
}
void Edge_DeleteAll(LISTGRAPH_T LG,EDGENODE_T head)
{
    EDGENODE_T p = head;
    while( p != NULL)
    {
        EDGENODE_T tmp = p->next;
        free(p);
        LG->edge_num--;
        p = tmp;
    }
}

到此，图的领接表示就完了。

有向图的邻接链表

xmind思维导图怎么绘制一个有曲线的流程图?

教你用CorelDraw9打造一幅有翠鸟的清新荷花图

乌鲁木齐网站建设公司，有客寻向您说明做网站的作用

AI制作非常漂亮有质感的水晶效果图

企业网站制作题目和稿子配图有什么地方需要注意的吗？

Python根据已知邻接矩阵绘制无向图操作示例

中府穴位位置图及作用中府穴的功效有哪些

99元的盒子能将有线打印机满血复活：有图有真相

Photoshop制作有创意的现实微型小人国场景图

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

有向图的邻接链表

xmind思维导图怎么绘制一个有曲线的流程图?

教你用CorelDraw9打造一幅有翠鸟的清新荷花图

乌鲁木齐网站建设公司，有客寻向您说明做网站的作用

AI制作非常漂亮有质感的水晶效果图

企业网站制作 题目和稿子配图有什么地方需要注意的吗？

Python根据已知邻接矩阵绘制无向图操作示例

中府穴位位置图及作用 中府穴的功效有哪些

99元的盒子能将有线打印机满血复活：有图有真相

Photoshop制作有创意的现实微型小人国场景图

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

企业网站制作题目和稿子配图有什么地方需要注意的吗？

中府穴位位置图及作用中府穴的功效有哪些