图论之广度优先遍历

生命当有坚持之算法拾遗

前言

若说读高中期间最大的遗憾,应该不是没有去给校花表白,应该是最后还是别无选择的参加了高考。年级主任说,我应该会把肠子给悔青吧。于是,自那时候起,做事情开始变得审慎。老实说,高中时候的指导老师很多次说过我浮躁,然后我却并不以为意,只是最后显得很无能为力。

24岁的365天也度过了350多天,恰逢上周六去听了一个培训,唤起了我曾蓄意很久的一件事 —— 让自己曾花费过很多个自由活动课和周末写就的沉睡代码再次换发生机。

所以,就让我从图论开始吧。

问题描述

有如上图所示的有向图,需要求从最小数字为起点的能够遍历所有节点路径。(其中,边上的数字为有向边的距离(权重),本文中不予考虑。)

输入数据

输入数据格式如下(为节省篇幅,截断中间部分),其中第一行数据为节点数m及边数n,随后的n行为有向边的起点、终点及距离(权重)数据。

5 16
1 2 5
1 3 8
...
5 5 11

算法代码

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

#define max -1

// struct node for node with it's index, data (weight) and next node pointer
typedef struct node {
  int dot;
  int data;
  struct node *next;
}node;

// struct flag for a chain of nodes originated from certain node
typedef struct flag {
  struct node *link;
  struct node *end;
}flag;

FILE *in, *out; // in and out pointers reference to input and output data file

int n, e; // n for node number, e for eage number
int visit[21] = {0}; // visit[i] denotes whether node i has been searched or not

flag g[21]; // flag[i] records a chian of nodes originated from a node with index i

// load input data and build the graph in memory as chains
void init() {
  int k, i, j, w;
  node *p;

  fscanf(in, "%d%d", &n, &e);

  for(i=1; i<=n; i++)
    g[i].link = NULL;

  for(k=1; k<=e; k++) {
    fscanf(in, "%d%d%d", &i, &j, &w);

    p = (node *)malloc(sizeof(node));
    p->dot = j;
    p->data = w;
    p->next = NULL;

    if(g[i].link == NULL) {
      g[i].link = p;
      g[i].end = p;
    } else {
      g[i].end->next = p;
      g[i].end = p;
    }
  }
}

// print out chians of nodes originated from a certain node
void outprint() {
  int i;
  node *p;

  for (i=1; i<=n; i++) {
    fprintf(out,"%d -> ", i);

    p = g[i].link;

    while (p!=NULL) {
      fprintf(out,"%d (%d),", p->dot, p->data);
      p = p->next;
    }

    fprintf(out, "\n");
  }
}

// deap first search start from node i
void dfs(int i) {
  int j;
  node *p;

  fprintf(out, "%d  ", i);

  visit[i] = 1;
  p = g[i].link;

  while (p!=NULL) {
    j = p->dot;

    if (!visit[j])
      dfs(j);

    p=p->next;
  }
}

int main() {
  int i;

  in = fopen("shuru.in", "r");
  out = fopen("shuchu.out","w");

  init();
  outprint();

  // start from the node with minimum index
  for (i=1; i<=n; i++)
    if (!visit[i])
      dfs(i);

  fclose(in);
  fclose(out);
}

输出数据

1 -> 2 (5),3 (8),5 (3),
2 -> 1 (5),3 (2),5 (6),
3 -> 1 (8),2 (2),4 (10),5 (4),
4 -> 3 (10),5 (11),
5 -> 1 (3),2 (6),3 (4),5 (11),
1  2  3  4  5  

以上输出文件,前5行表示与箭头前节点有关联的节点序列(如下图),第6行为深度优先遍历所有节点的节点序列。


* first generated at 2018-04-30 15:08:11 UTC © http://articles.johannhuang.com

Subscribe by RSS