转载

数据结构与算法之“图”

其实所有的数据结构都是“图”。图其实就是一系列的顶点和边的集合。如果边有指向性就叫做有向图，否则就是无向图，边也可以有权值。任意两点间都有路径连接的图叫做连通图，顶点连接的边数叫做这个顶点的度。

没有圈的连通图就是所谓的树，没有圈的非连通图就是森林。

1、图的表示

(1)邻接矩阵

使用|V|*|V|的二维数组来表示：graph[V][V]。graph[i][j]表示顶点i和顶点j的关系，在无权图中，graph[i][j]=1表示i,j之间有边，=0表示无边。无向图中，这是一个堆成矩阵；若是带权图，则graph[i][j]表示顶点i到顶点j的边的权值，无边时graph[i][j]=INF。

用邻接矩阵可以在o(1)时间内判断两点间是否有边存在，可是代价是花费o(|V| ² )的空间。在无向图中由于是对称矩阵，至少浪费了一般的空间；当一个图的边很少时，空间利用率更低。

(2)邻接表

每个顶点都有一个邻接表（包含邻接于该顶点的所有顶点）。邻接表只需要占用o(|V|+|E|)的空间，极大地提高了空间的利用率。邻接表也有两种表示方式，用链表来表示，则为邻接链表；用数组表示，则为邻接数组。无论是邻接链表还是邻接数组，它们的空间复杂度都渐近相等，但在图的很多算法中，邻接数组的用时比邻接矩阵要少。

这里采用的是邻接表的表示方法：

vector<int> G[MAX_V];//MAX_V为顶点数

其中，G[i]表示顶点i的邻接表。

判断边(i,j)是否存在于图G中：

bool existsEdge(int i,int j){     vector<int>::iterator it;     for(it=G[i].begin(); it!=G[i].end(); it++)         if(j == *it)             return true;     return false; }

向G中插入边(i,j)：

void insertEdge(int i,int j){     if(existsEdge(i,j))         return ;     G[i].push_back(j);     G[j].push_back(i); }

从G中删除边(i,j)：

void eraseEdge(int i,int j){  for(it=G[i].begin(); it!=G[i].end(); it++)   if(j == *it)    G[i].erase(it);  for(it=G[j].begin(); it!=G[j].end(); it++)   if(i == *it)    G[j].erase(it); }

顶点i的度：

int degree(int i){     return G[i].size(); }

2、图的遍历

其中，flag数组用来记录已经搜索过的顶点。这里的G[MAX_V]为无向图，通过遍历打印出所有的边。

(1)深度优先遍历（DFS）

从一个顶点v开始，选择一个邻接于v并且未到达的顶点u，如果u存在,则从u开始新的DFS，否则，u存在，结束搜索返回。

void dfs(int v){  static int flag[MAX_V] = {0};  flag[v] = 1;  for(int i=0; i<G[v].size(); i++){   if(0 == flag[G[v][i]]){    dfs(G[v][i]);    printf("%d <--> %d/n",v,G[v][i]);   }  } }

(2)广度优先遍历（BFS）

其实BFS就跟树的层序遍历一样，从一个顶点开始，访问它的所有邻接顶点，并把访问过的邻接顶点放入队列里，每次访问完所有的邻接顶点后，就从队列里取出一个顶点，然后，继续前面操作，直到队列里的元素个数为0。

void bfs(int v){  queue<int> que;  bool flag[MAX_V];  fill(flag,flag+MAX_V,false);  que.push(v);  flag[v] = true;  while(!que.empty()){   int vi = que.front();   que.pop();   vector<int> it;   for(it=G[vi].begin(); it!=G[vi].end(); it++){    if(!flag[*it]){     printf("%d <--> %d/n",vi,*it);     que.push(*it);     flag[*it] = true;    }   }  } }