论坛 › 数据结构与算法 › 图的遍历完整代码（邻接表）

小甲鱼的二师兄 发表于 2016-3-9 02:10:01

图的遍历完整代码（邻接表）

本帖最后由 小甲鱼的二师兄 于 2016-3-9 14:57 编辑

邻接表（无向图）

/**
* C: 邻接表表示的"无向图(List Undirected Graph)"
*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define MAX 100
#define isLetter(a)((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
#define LENGTH(a)(sizeof(a)/sizeof(a))

// 邻接表中表对应的链表的顶点
typedef struct _ENode
{
    int ivex;                   // 该边所指向的顶点的位置
    struct _ENode *next_edge;   // 指向下一条弧的指针
}ENode, *PENode;

// 邻接表中表的顶点
typedef struct _VNode
{
    char data;            // 顶点信息
    ENode *first_edge;      // 指向第一条依附该顶点的弧
}VNode;

// 邻接表
typedef struct _LGraph
{
    int vexnum;             // 图的顶点的数目
    int edgnum;             // 图的边的数目
    VNode vexs;
}LGraph;

/*
* 返回ch在matrix矩阵中的位置
*/
static int get_position(LGraph g, char ch)
{
    int i;
    for(i=0; i<g.vexnum; i++)
      if(g.vexs.data==ch)
            return i;
    return -1;
}

/*
* 读取一个输入字符
*/
static char read_char()
{
    char ch;

    do {
      ch = getchar();
    } while(!isLetter(ch));

    return ch;
}

/*
* 将node链接到list的末尾
*/
static void link_last(ENode *list, ENode *node)
{
    ENode *p = list;

    while(p->next_edge)
      p = p->next_edge;
    p->next_edge = node;
}

/*
* 创建邻接表对应的图(自己输入)
*/
LGraph* create_lgraph()
{
    char c1, c2;
    int v, e;
    int i, p1, p2;
    ENode *node1, *node2;
    LGraph* pG;

    // 输入"顶点数"和"边数"
    printf("input vertex number: ");
    scanf("%d", &v);
    printf("input edge number: ");
    scanf("%d", &e);
    if ( v < 1 || e < 1 || (e > (v * (v-1))))
    {
      printf("input error: invalid parameters!\n");
      return NULL;
    }

    if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(LGraph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = v;
    pG->edgnum = e;
    // 初始化"邻接表"的顶点
    for(i=0; i<pG->vexnum; i++)
    {
      printf("vertex(%d): ", i);
      pG->vexs.data = read_char();
      pG->vexs.first_edge = NULL;
    }

    // 初始化"邻接表"的边
    for(i=0; i<pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      printf("edge(%d): ", i);
      c1 = read_char();
      c2 = read_char();

      p1 = get_position(*pG, c1);
      p2 = get_position(*pG, c2);

      // 初始化node1
      node1 = (ENode*)malloc(sizeof(ENode));
      node1->ivex = p2;
      node1->next_edge = NULL;
      // 将node1链接到"p1所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node1;
      else
            link_last(pG->vexs.first_edge, node1);
      // 初始化node2
      node2 = (ENode*)malloc(sizeof(ENode));
      node2->ivex = p1;
      node1->next_edge = NULL;
      // 将node2链接到"p2所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node2;
      else
            link_last(pG->vexs.first_edge, node2);
    }

    return pG;
}

/*
* 创建邻接表对应的图(用已提供的数据)
*/
LGraph* create_example_lgraph()
{
    char c1, c2;
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[] = {
      {'A', 'C'},
      {'A', 'D'},
      {'A', 'F'},
      {'B', 'C'},
      {'C', 'D'},
      {'E', 'G'},
      {'F', 'G'}};
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);
    int i, p1, p2;
    ENode *node1, *node2;
    LGraph* pG;


    if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(LGraph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = vlen;
    pG->edgnum = elen;
    // 初始化"邻接表"的顶点
    for(i=0; i<pG->vexnum; i++)
    {
      pG->vexs.data = vexs;
      pG->vexs.first_edge = NULL;
    }

    // 初始化"邻接表"的边
    for(i=0; i<pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      c1 = edges;
      c2 = edges;

      p1 = get_position(*pG, c1);
      p2 = get_position(*pG, c2);

      // 初始化node1
      node1 = (ENode*)malloc(sizeof(ENode));
      node1->ivex = p2;
      node1->next_edge = NULL;
      // 将node1链接到"p1所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node1;
      else
            link_last(pG->vexs.first_edge, node1);
      // 初始化node2
      node2 = (ENode*)malloc(sizeof(ENode));
      node2->ivex = p1;
      node2->next_edge = NULL;
      // 将node2链接到"p2所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node2;
      else
            link_last(pG->vexs.first_edge, node2);
    }

    return pG;
}

/*
* 深度优先搜索遍历图的递归实现
*/
static void DFS(LGraph G, int i, int *visited)
{
    int w;
    ENode *node;

    visited = 1;
    printf("%c ", G.vexs.data);
    node = G.vexs.first_edge;
    while (node != NULL)
    {
      if (!visited)
            DFS(G, node->ivex, visited);
      node = node->next_edge;
    }
}

/*
* 深度优先搜索遍历图
*/
void DFSTraverse(LGraph G)
{
    int i;
    int visited;       // 顶点访问标记

    // 初始化所有顶点都没有被访问
    for (i = 0; i < G.vexnum; i++)
      visited = 0;

    printf("DFS: ");
    for (i = 0; i < G.vexnum; i++)
    {
      if (!visited)
            DFS(G, i, visited);
    }
    printf("\n");
}

/*
* 广度优先搜索（类似于树的层次遍历）
*/
void BFS(LGraph G)
{
    int head = 0;
    int rear = 0;
    int queue;   // 辅组队列
    int visited;   // 顶点访问标记
    int i, j, k;
    ENode *node;

    for (i = 0; i < G.vexnum; i++)
      visited = 0;

    printf("BFS: ");
    for (i = 0; i < G.vexnum; i++)
    {
      if (!visited)
      {
            visited = 1;
            printf("%c ", G.vexs.data);
            queue = i;// 入队列
      }
      while (head != rear)
      {
            j = queue;// 出队列
            node = G.vexs.first_edge;
            while (node != NULL)
            {
                k = node->ivex;
                if (!visited)
                {
                  visited = 1;
                  printf("%c ", G.vexs.data);
                  queue = k;
                }
                node = node->next_edge;
            }
      }
    }
    printf("\n");
}

/*
* 打印邻接表图
*/
void print_lgraph(LGraph G)
{
    int i,j;
    ENode *node;

    printf("List Graph:\n");
    for (i = 0; i < G.vexnum; i++)
    {
      printf("%d(%c): ", i, G.vexs.data);
      node = G.vexs.first_edge;
      while (node != NULL)
      {
            printf("%d(%c) ", node->ivex, G.vexs.data);
            node = node->next_edge;
      }
      printf("\n");
    }
}

void main()
{
    LGraph* pG;

    // 自定义"图"(自己输入数据)
    //pG = create_lgraph();
    // 采用已有的"图"
    pG = create_example_lgraph();

    // 打印图
    print_lgraph(*pG);
    DFSTraverse(*pG);
    BFS(*pG);
}

邻接表（有向图）

/**
* C: 邻接表表示的"有向图(List Directed Graph)"
*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define MAX 100
#define isLetter(a)((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
#define LENGTH(a)(sizeof(a)/sizeof(a))

// 邻接表中表对应的链表的顶点
typedef struct _ENode
{
    int ivex;                   // 该边所指向的顶点的位置
    struct _ENode *next_edge;   // 指向下一条弧的指针
}ENode, *PENode;

// 邻接表中表的顶点
typedef struct _VNode
{
    char data;            // 顶点信息
    ENode *first_edge;      // 指向第一条依附该顶点的弧
}VNode;

// 邻接表
typedef struct _LGraph
{
    int vexnum;             // 图的顶点的数目
    int edgnum;             // 图的边的数目
    VNode vexs;
}LGraph;

/*
* 返回ch在matrix矩阵中的位置
*/
static int get_position(LGraph g, char ch)
{
    int i;
    for(i=0; i<g.vexnum; i++)
      if(g.vexs.data==ch)
            return i;
    return -1;
}

/*
* 读取一个输入字符
*/
static char read_char()
{
    char ch;

    do {
      ch = getchar();
    } while(!isLetter(ch));

    return ch;
}

/*
* 将node链接到list的末尾
*/
static void link_last(ENode *list, ENode *node)
{
    ENode *p = list;

    while(p->next_edge)
      p = p->next_edge;
    p->next_edge = node;
}

/*
* 创建邻接表对应的图(自己输入)
*/
LGraph* create_lgraph()
{
    char c1, c2;
    int v, e;
    int i, p1, p2;
    ENode *node1, *node2;
    LGraph* pG;

    // 输入"顶点数"和"边数"
    printf("input vertex number: ");
    scanf("%d", &v);
    printf("input edge number: ");
    scanf("%d", &e);
    if ( v < 1 || e < 1 || (e > (v * (v-1))))
    {
      printf("input error: invalid parameters!\n");
      return NULL;
    }

    if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(LGraph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = v;
    pG->edgnum = e;
    // 初始化"邻接表"的顶点
    for(i=0; i<pG->vexnum; i++)
    {
      printf("vertex(%d): ", i);
      pG->vexs.data = read_char();
      pG->vexs.first_edge = NULL;
    }

    // 初始化"邻接表"的边
    for(i=0; i<pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      printf("edge(%d): ", i);
      c1 = read_char();
      c2 = read_char();

      p1 = get_position(*pG, c1);
      p2 = get_position(*pG, c2);
      // 初始化node1
      node1 = (ENode*)malloc(sizeof(ENode));
      node1->ivex = p2;
      node1->next_edge = NULL;
      // 将node1链接到"p1所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node1;
      else
            link_last(pG->vexs.first_edge, node1);
    }

    return pG;
}

/*
* 创建邻接表对应的图(用已提供的数据)
*/
LGraph* create_example_lgraph()
{
    char c1, c2;
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[] = {
      {'A', 'B'},
      {'B', 'C'},
      {'B', 'E'},
      {'B', 'F'},
      {'C', 'E'},
      {'D', 'C'},
      {'E', 'B'},
      {'E', 'D'},
      {'F', 'G'}};
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);
    int i, p1, p2;
    ENode *node1, *node2;
    LGraph* pG;


    if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(LGraph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = vlen;
    pG->edgnum = elen;
    // 初始化"邻接表"的顶点
    for(i=0; i<pG->vexnum; i++)
    {
      pG->vexs.data = vexs;
      pG->vexs.first_edge = NULL;
    }

    // 初始化"邻接表"的边
    for(i=0; i<pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      c1 = edges;
      c2 = edges;

      p1 = get_position(*pG, c1);
      p2 = get_position(*pG, c2);
      // 初始化node1
      node1 = (ENode*)malloc(sizeof(ENode));
      node1->ivex = p2;
      node1->next_edge = NULL;
      // 将node1链接到"p1所在链表的末尾"
      if(pG->vexs.first_edge == NULL)
          pG->vexs.first_edge = node1;
      else
            link_last(pG->vexs.first_edge, node1);
    }

    return pG;
}

/*
* 深度优先搜索遍历图的递归实现
*/
static void DFS(LGraph G, int i, int *visited)
{
    int w;
    ENode *node;

    visited = 1;
    printf("%c ", G.vexs.data);
    node = G.vexs.first_edge;
    while (node != NULL)
    {
      if (!visited)
            DFS(G, node->ivex, visited);
      node = node->next_edge;
    }
}

/*
* 深度优先搜索遍历图
*/
void DFSTraverse(LGraph G)
{
    int i;
    int visited;       // 顶点访问标记

    // 初始化所有顶点都没有被访问
    for (i = 0; i < G.vexnum; i++)
      visited = 0;

    printf("DFS: ");
    for (i = 0; i < G.vexnum; i++)
    {
      if (!visited)
            DFS(G, i, visited);
    }
    printf("\n");
}

/*
* 广度优先搜索（类似于树的层次遍历）
*/
void BFS(LGraph G)
{
    int head = 0;
    int rear = 0;
    int queue;   // 辅组队列
    int visited;   // 顶点访问标记
    int i, j, k;
    ENode *node;

    for (i = 0; i < G.vexnum; i++)
      visited = 0;

    printf("BFS: ");
    for (i = 0; i < G.vexnum; i++)
    {
      if (!visited)
      {
            visited = 1;
            printf("%c ", G.vexs.data);
            queue = i;// 入队列
      }
      while (head != rear)
      {
            j = queue;// 出队列
            node = G.vexs.first_edge;
            while (node != NULL)
            {
                k = node->ivex;
                if (!visited)
                {
                  visited = 1;
                  printf("%c ", G.vexs.data);
                  queue = k;
                }
                node = node->next_edge;
            }
      }
    }
    printf("\n");
}

/*
* 打印邻接表图
*/
void print_lgraph(LGraph G)
{
    int i,j;
    ENode *node;

    printf("List Graph:\n");
    for (i = 0; i < G.vexnum; i++)
    {
      printf("%d(%c): ", i, G.vexs.data);
      node = G.vexs.first_edge;
      while (node != NULL)
      {
            printf("%d(%c) ", node->ivex, G.vexs.data);
            node = node->next_edge;
      }
      printf("\n");
    }
}

void main()
{
    LGraph* pG;

    // 自定义"图"(自己输入数据)
    //pG = create_lgraph();
    // 采用已有的"图"
    pG = create_example_lgraph();

    // 打印图
    print_lgraph(*pG);
    DFSTraverse(*pG);
    BFS(*pG);
}

～风介～ 发表于 2016-3-11 19:22:13

顶一个，现在也开始复习《数据结构与算法》了~{:10_256:}

mianht 发表于 2016-4-4 16:48:33

赞一个！

rowang 发表于 2016-5-2 19:28:54

温馨提示，加入边的时候不一定非要插入到链表尾部，那样还会查找遍历整个链表，效率较低，可以直接插入到链表首部，写起来方便而且效率高^_^。

sxd 发表于 2016-5-26 20:16:52

队列用STL感觉好方便{:5_97:}

丨平平淡淡丶 发表于 2018-12-24 18:20:55

给楼主点个赞～

pmyasdf 发表于 2019-9-7 15:19:08

感谢！{:5_105:}

mspstd21 发表于 2020-2-11 17:03:52

厉害

zxh. 发表于 2020-4-10 19:06:08

malloc后面如果不用memset可不可以

查看完整版本: 图的遍历完整代码（邻接表）