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

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

邻接矩阵（无向图）

/**
* C: 邻接矩阵图表示的"无向图(Matrix Undirected Graph)"
*
* @author skywang
* @date 2014/04/18
*/

#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 _graph
{
    char vexs;       // 顶点集合
    int vexnum;         // 顶点数
    int edgnum;         // 边数
    int matrix; // 邻接矩阵
}Graph, *PGraph;

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

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

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

    return ch;
}

/*
* 创建图(自己输入)
*/
Graph* create_graph()
{
    char c1, c2;
    int v, e;
    int i, p1, p2;
    Graph* 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=(Graph*)malloc(sizeof(Graph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(Graph));

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

    // 初始化"边"
    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);
      if (p1==-1 || p2==-1)
      {
            printf("input error: invalid edge!\n");
            free(pG);
            return NULL;
      }

      pG->matrix = 1;
      pG->matrix = 1;
    }

    return pG;
}

/*
* 创建图(用已提供的矩阵)
*/
Graph* create_example_graph()
{
    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;
    Graph* pG;
   
    // 输入"顶点数"和"边数"
    if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(Graph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = vlen;
    pG->edgnum = elen;
    // 初始化"顶点"
    for (i = 0; i < pG->vexnum; i++)
    {
      pG->vexs = vexs;
    }

    // 初始化"边"
    for (i = 0; i < pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      p1 = get_position(*pG, edges);
      p2 = get_position(*pG, edges);

      pG->matrix = 1;
      pG->matrix = 1;
    }

    return pG;
}

/*
* 返回顶点v的第一个邻接顶点的索引，失败则返回-1
*/
static int first_vertex(Graph G, int v)
{
    int i;

    if (v<0 || v>(G.vexnum-1))
      return -1;

    for (i = 0; i < G.vexnum; i++)
      if (G.matrix == 1)
            return i;

    return -1;
}

/*
* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
*/
static int next_vertix(Graph G, int v, int w)
{
    int i;

    if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
      return -1;

    for (i = w + 1; i < G.vexnum; i++)
      if (G.matrix == 1)
            return i;

    return -1;
}

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

    visited = 1;
    printf("%c ", G.vexs);
    // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
    for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
    {
      if (!visited)
            DFS(G, w, visited);
    }
      
}

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

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

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

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

    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);
            queue = i;// 入队列
      }
      while (head != rear)
      {
            j = queue;// 出队列
            for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
            {
                if (!visited)
                {
                  visited = 1;
                  printf("%c ", G.vexs);
                  queue = k;
                }
            }
      }
    }
    printf("\n");
}

/*
* 打印矩阵队列图
*/
void print_graph(Graph G)
{
    int i,j;

    printf("Martix Graph:\n");
    for (i = 0; i < G.vexnum; i++)
    {
      for (j = 0; j < G.vexnum; j++)
            printf("%d ", G.matrix);
      printf("\n");
    }
}

void main()
{
    Graph* pG;

    // 自定义"图"(输入矩阵队列)
    //pG = create_graph();
    // 采用已有的"图"
    pG = create_example_graph();

    print_graph(*pG);       // 打印图
    DFSTraverse(*pG);       // 深度优先遍历
    BFS(*pG);               // 广度优先遍历
}

邻接矩阵（有向图）

/**
* C: 邻接矩阵表示的"有向图(Matrix Directed Graph)"
*
* @author skywang
* @date 2014/04/18
*/

#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 _graph
{
    char vexs;       // 顶点集合
    int vexnum;         // 顶点数
    int edgnum;         // 边数
    int matrix; // 邻接矩阵
}Graph, *PGraph;

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

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

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

    return ch;
}

/*
* 创建图(自己输入)
*/
Graph* create_graph()
{
    char c1, c2;
    int v, e;
    int i, p1, p2;
    Graph* 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=(Graph*)malloc(sizeof(Graph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(Graph));

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

    // 初始化"边"
    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);
      if (p1==-1 || p2==-1)
      {
            printf("input error: invalid edge!\n");
            free(pG);
            return NULL;
      }

      pG->matrix = 1;
    }

    return pG;
}

/*
* 创建图(用已提供的矩阵)
*/
Graph* create_example_graph()
{
    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;
    Graph* pG;
   
    // 输入"顶点数"和"边数"
    if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
      return NULL;
    memset(pG, 0, sizeof(Graph));

    // 初始化"顶点数"和"边数"
    pG->vexnum = vlen;
    pG->edgnum = elen;
    // 初始化"顶点"
    for (i = 0; i < pG->vexnum; i++)
    {
      pG->vexs = vexs;
    }

    // 初始化"边"
    for (i = 0; i < pG->edgnum; i++)
    {
      // 读取边的起始顶点和结束顶点
      p1 = get_position(*pG, edges);
      p2 = get_position(*pG, edges);

      pG->matrix = 1;
    }

    return pG;
}

/*
* 返回顶点v的第一个邻接顶点的索引，失败则返回-1
*/
static int first_vertex(Graph G, int v)
{
    int i;

    if (v<0 || v>(G.vexnum-1))
      return -1;

    for (i = 0; i < G.vexnum; i++)
      if (G.matrix == 1)
            return i;

    return -1;
}

/*
* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
*/
static int next_vertix(Graph G, int v, int w)
{
    int i;

    if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
      return -1;

    for (i = w + 1; i < G.vexnum; i++)
      if (G.matrix == 1)
            return i;

    return -1;
}

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

    visited = 1;
    printf("%c ", G.vexs);
    // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
    for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
    {
      if (!visited)
            DFS(G, w, visited);
    }
      
}

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

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

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

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

    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);
            queue = i;// 入队列
      }
      while (head != rear)
      {
            j = queue;// 出队列
            for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
            {
                if (!visited)
                {
                  visited = 1;
                  printf("%c ", G.vexs);
                  queue = k;
                }
            }
      }
    }
    printf("\n");
}

/*
* 打印矩阵队列图
*/
void print_graph(Graph G)
{
    int i,j;

    printf("Martix Graph:\n");
    for (i = 0; i < G.vexnum; i++)
    {
      for (j = 0; j < G.vexnum; j++)
            printf("%d ", G.matrix);
      printf("\n");
    }
}

void main()
{
    Graph* pG;

    // 自定义"图"(输入矩阵队列)
    //pG = create_graph();
    // 采用已有的"图"
    pG = create_example_graph();

    print_graph(*pG);       // 打印图
    DFSTraverse(*pG);       // 深度优先遍历
    BFS(*pG);               // 广度优先遍历
}

mianht 发表于 2016-4-4 16:49:26

题主辛苦啦{:9_233:}
页: [1]
查看完整版本: 图的遍历完整代码（邻接矩阵）