数据结构之——图

Created in December 05, 2015

2015   ·   datastructure

终于写到数据结构的图部分了，后面接着的还有排序，可能也会写散列（串）。写完Data Structure专题的之后寒假打算是泛读算法导论，所以寒假时候的博客内容还是算法部分，也会预习下学期的运筹学，MySql,可能之后会涉及面试题的汇总和查漏补缺部分。还有一个就是特别希望赶快过一遍LINUX的部分，然后第二次学的时候也总结在博客上面。总之还有很多事情要做，很多知识要学。

 

正文：

  • 图的概念（来自维基百科）

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts frommathematics.

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges or arcs orlines for an undirected graph and as arrows or directed edges or directed arcs or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

译：图是一种抽象数据结构，用来解决数学中的无向图和有向图的概念。

图包括顶点，与之联系的无向或者有向的边。边无箭头的为无向边，有箭头指向的则是有向边，顶点可能是图结构的一员，也可能是由整数索引或者引用的外部结点。

1.简单的图

screenshot

<三个顶点，三条边的图>

2.基本操作

The basic operations provided by a graph data structure G usually include:

  • adjacent(G, x, y): tests whether there is an edge from the vertices x to y;

  • 检测x与y之间是否有边

  • neighbors(G, x): lists all vertices y such that there is an edge from the vertices x to y;

  • 顶点x的所有邻边

  • add_vertex(G, x): adds the vertex x, if it is not there;

  • 若无点，增加顶点

  • remove_vertex(G, x): removes the vertex x, if it is there;

  • 若有点，移除点

  • add_edge(G, x, y): adds the edge from the vertices x to y, if it is not there;

  • 若无边，增加边

  • remove_edge(G, x, y): removes the edge from the vertices x to y, if it is there;

  • 若有边，移除

  • get_vertex_value(G, x): returns the value associated with the vertex x;

  • 获得顶点值

  • set_vertex_value(G, x, v): sets the value associated with the vertex x to v.
  • 设置顶点值

Structures that associate values to the edges usually also provide:

  • get_edge_value(G, x, y): returns the value associated with the edge (x, y);

  • 返回x与y权值

  • set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
  • 设置权值

 

  • 基本抽象数据定义

class Graph{ public: //class member int vexnum; //VERTEX NUM int edgenum; //EDGES NUM vector V; //STORAGE THE GRAPH //member function Graph(){ //CONSTRUCTOR vexnum = 0; edgenum = 0; } Graph(vector & v); int getVexNum(); int getEdgeNum();

void InsertVertex(VNode &x);     //Vertex 
bool DeleteVertex(int x);

bool IsEdge(int v1, int v2);     //Edge
bool AddEdge(int v1, int v2);
bool RemoveEdge(int v1, int v2);

void PrintNeighbors(int x);      //Neighbor
VNode & Neighbor(VNode &x, int n);//the Nth neighbors n would be the first in default

//BFS
void BreadthFirstSearch();
void BFS(VNode & x);             //implementation it with QUEUE

//DFS
void DepthFirstSearch();
void DFS(VNode &x);              //implementation it with DFS //	~Graph();                        //DESTRUCTION  };

关于边和顶点的操作无非就是添加删除，还有就是顶点自身的一些性质，顶点的值[data]，顶点是否被访问[bool visited] .所以还有关于顶点的定义。

class VNode{//VERTEX CLASS public: //data member bool visited; //VISITED NOTE DataType data; //VERTEX DATA vector e; //ADJUST EDGE

//function member
VNode(DataType val = INIT_DATA, bool flag = false) :data(val), visited(flag){}    //CONSTRUCTOR
void Visit(){
	cout << data << " ";
}
bool operator == (VNode & y){           //OVERWRITE THE ==
	if (data == y.data && e == y.e)
		return true;
	else
		return false;
} };
  • 完整操作 ```c++ #ifndef _GRAPH__H__ #define _GRAPH__H__ #include #include #include using namespace std; typedef int DataType; const DataType INIT_DATA = -1; const int NO_NODE = -1; const int NO_EDGE = -2;

class VNode{//VERTEX CLASS public: //data member bool visited; //VISITED NOTE DataType data; //VERTEX DATA vector e; //ADJUST EDGE

//function member
VNode(DataType val = INIT_DATA, bool flag = false) :data(val), visited(flag){}    //CONSTRUCTOR
void Visit(){
	cout << data << " ";
}
bool operator == (VNode & y){           //OVERWRITE THE ==
	if (data == y.data && e == y.e)
		return true;
	else
		return false;
} };

class Graph{ public: //class member int vexnum; //VERTEX NUM int edgenum; //EDGES NUM vector V; //STORAGE THE GRAPH //member function Graph(){ //CONSTRUCTOR vexnum = 0; edgenum = 0; } Graph(vector & v); int getVexNum(); int getEdgeNum();

void InsertVertex(VNode &x);     //Vertex 
bool DeleteVertex(int x);

bool IsEdge(int v1, int v2);     //Edge
bool AddEdge(int v1, int v2);
bool RemoveEdge(int v1, int v2);

void PrintNeighbors(int x);      //Neighbor
VNode & Neighbor(VNode &x, int n);//the Nth neighbors n would be the first in default

//BFS
void BreadthFirstSearch();
void BFS(VNode & x);             //implementation it with QUEUE

//DFS
void DepthFirstSearch();
void DFS(VNode &x);              //implementation it with DFS //	~Graph();                        //DESTRUCTION  };

Graph::Graph(vector &v){ V.assign(v.begin(), v.end());//将区间[first,last)的元素赋值到当前的vector容器中 vexnum = V.size(); edgenum = getEdgeNum(); }

int Graph::getVexNum(){ vexnum = V.size(); return vexnum; }

int Graph::getEdgeNum(){ edgenum = 0; for (vector::iterator iter = V.begin(); iter != V.end(); ++iter){ edgenum += iter->e.size(); } return edgenum; }

void Graph::InsertVertex(VNode &x){ V.push_back(x); vexnum++; }

bool Graph::DeleteVertex(int x){ if (x >= V.size() || x < 0){ cout « “Not Found This Node” « endl; return false; } vector::iterator iter = V.begin() + x; V.erase(iter); vexnum--; return true; }

bool Graph::AddEdge(int v1, int v2){ if ((v1 >= V.size() || v1 < 0) || (v2 >= V.size() || v2 < 0)){//容错处理 cout « “Not Found This Edge” « endl; return false; } int size = V[v1].e.size(); for (vector::iterator iter = V[v1].e.begin(); iter != V[v1].e.end(); iter++){ if (V[*iter] == V[v1]){ cout << "It has already had (v1,v2)" << endl; return false; } } }

bool Graph::RemoveEdge(int v1, int v2){ if ((v1 >= V.size() || v1 < 0) || (v2 >= V.size() || v2 < 0)){//容错处理 cout « “Not Found This Edge” « endl; return false; } for (vector::iterator iter = V[v1].e.begin(); iter != V[v1].e.end(); iter++){ if (V[*iter] == V[v2]){ V[v1].e.erase(iter);//删除操作 edgenum--; return true; } } }

这里的操作基本都是采用泛型编程，用vecor容器中迭代器来完成一些基本的操作。比如里面出现的边的对象e,节点的对象V，因为在节点定义里面定义了储存边的容器，所以可以用V.e.的类似操作来操作边的增加和移除。还有vector中一些常用操作assign（将区间first和last的元素赋值进入）,erase(清除)，size（返回其容器内元素的个数）。

------------有点累 晚点更新-----------------

- **图出现的算法介绍**

图出现的算法挺多的，这里介绍6个算法

1. **深度优先搜索**

简称DFS(Depth First Search)，是搜索算法中的一种，是一种在开发[爬虫](http://baike.baidu.com/link?url=Wxx4HrhPJs3v78RffNJQRYtJ3UrnkUM94kaEmlpu1gM_LtEGrTISPjZ2x-4Lv_0N)中比较常用的算法，目的是要达到被搜索结构的叶结点。

<p align="center">
  <img src="https://zhengliangliang.files.wordpress.com/2015/12/2015-12-06_095930.png" alt="screenshot" width="80%" height="auto">
</p>

**例如这一个图示例，访问先后就是 A B E F D C G 先要往最低最底寻找节点。那么这样的机制要怎么实现呢？**

1. **在树里面，我们可以利用stack来完成，根节点首先在栈，然后弹出，先让右子树入栈，然后让左子树入栈，然后依次出栈达成DFS的要求**

void DepthFirstSearch(Tree root){
    stack<Node *> nodeStack;//用STL的栈容器装载
    nodeStack.push(root);
    Node * node;
    while(!nodeStack.empty()){ //循环体【必记内容】
       node = nodeStack.top();
       cout<<node->data<<" ";  //第一次输出根
       nodeStack.pop();        //第一次让根出栈
       if(node->rChild)
       	nodeStack.push(node->rChild);
       if(node->lChild)
       	nodeStack.push(node->lChild);
    }
}

**2.也可以用递归的方法来实现**
```c++
#include <iostream>
#include <list>

using namespace std;

class Graph{
  int V;             //顶点数
  list<int> * adj;   //存储邻边
public:
  Graph(int V);
  void addEdge(int v, int w);         //增加边
  void DFS(int s);                    //DFS操作
  void DFSUtil(int v, bool visited[]);//输出并且判断是否已经访问
};

Graph::Graph(int V){                  //构造函数
  this->V = V;
  adj = new list<int>[V];
}

void Graph::addEdge(int v, int w){     //增加边
  adj[v].push_back(w);                 //利用邻接矩阵的思想
}

void Graph::DFS(int v){                //DFS v是源点
  //Mark all the vertices as not visited
  bool * visited = new bool[V];
  for (int i = 0; i < V; i++)
    visited[i] = false;

  //Call the recursive helper function to print the DFS traversal
  DFSUtil(v, visited);
}

void Graph::DFSUtil(int v, bool visited[]){
  //mark the current node as visited
  visited[v] = true;
  cout << v << " ";

  list<int>::iterator i;              //利用迭代器
  for (i = adj[v].begin(); i != adj[v].end();i++)
      if (!visited[*i])               //如果没有访问
        DFSUtil(*i, visited);         //递归
}

void main(){
  // Create a graph given in the above diagram
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  cout << "Following is Depth First Traversal (starting from vertex 2) n";
  g.DFS(2);

  system("pause");
}

利用了邻接矩阵的思想。将一个点作为类似adj[i][j]中的i，另一点作为j.只不过这里是用链表来解决。

  • 广度优先搜索

广度优先遍历（BFS）。又称为宽度优先遍历，是最简便的图的搜索算法之一。单源最短路径算法和prim最小生成树都采用了类似BFS的思想。

来自百度百科：

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

1、把根节点放到队列的末尾。

2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序

screenshot

还是刚刚那个图，如果遍历的话，顺序是A B C D E F G.显然和DFS有很大的区别，这个是访问完一个结点所有的邻接结点。

  1. 树里面的实现搬出来看看 
    void BreadthFirstSearch(Tree root){
  queue<Node *> nodeQueue;
  nodeQueue.push(root);
  Node*node;
  while(!nodeQueue.empty()){
 node = nodeQueue.front();
   nodeQueue.pop();
   cout<<node->data<<" ";
   if(node->lChild)
     nodeQueue.push(node->lChild);
   if(node->rChild)
     nodeQueue.push(node->rChild);
  }
}

    简直和DFS的做法一样，就是用queue来搞定，一个while循环，里面访问首元素，弹出，然后递归，递归先访问左子树，后访问右子树。

2.用STL可以更简单一点

// Program to print BFS traversal from a given source vertex. BFS(int s) 
// traverses vertices reachable from s.
#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
  int V;    // No. of vertices
  list<int> *adj;    // Pointer to an array containing adjacency lists
public:
  Graph(int V);  // Constructor
  void addEdge(int v, int w); // function to add an edge to graph
  void BFS(int s);  // prints BFS traversal from a given source s
};

Graph::Graph(int V)
{
  this->V = V;
  adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
  adj[v].push_back(w); // Add w to v¡¯s list.
}

void Graph::BFS(int s)
{
  // Mark all the vertices as not visited
  bool *visited = new bool[V];
  for (int i = 0; i < V; i++)
    visited[i] = false;

  // Create a queue for BFS
  list<int> queue;

  // Mark the current node as visited and enqueue it
  visited[s] = true;
  queue.push_back(s);

  // 'i' will be used to get all adjacent vertices of a vertex
  list<int>::iterator i;

  while (!queue.empty())
  {
    // Dequeue a vertex from queue and print it
    s = queue.front();
    cout << s << " ";
    queue.pop_front();

    // Get all adjacent vertices of the dequeued vertex s
    // If a adjacent has not been visited, then mark it visited
    // and enqueue it
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
    {
      if (!visited[*i])
      {
        visited[*i] = true;//注意要把它标记为true
        queue.push_back(*i);//这里我有个疑问 这一个点其实可以不需要的
      }
    }
  }
}

// Driver program to test methods of graph class
int main()
{
  // Create a graph given in the above diagram
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  cout << "Following is Breadth First Traversal (starting from vertex 2) n";
  g.BFS(2);

  system("pause");
  return 0;
}

和DFS基本一样，就是把DSFUtil那个函数的递归模式改为用一个while来实现而已。

  • PRIM

普里姆算法，是生成最小生成树的算法。

具体步骤：来源于百度

普里姆(Prim)算法

（1）算法思想

通过每次添加一个新节点加入集合，直到所有点加入停止的最小生成树的算法

原理：每次连出该集合到其他所有点的最短边保证生成树的边权总和最小

1. 首先随便选一个点加入集合

2. 用该点的所有边去刷新到其他点的最短路

3. 找出最短路中最短的一条连接（且该点未被加入集合）

4. 用该点去刷新到其他点的最短路

5 重复以上操作n-1次

6 最小生成树的代价就是连接的所有边的权值之和

7最适合用于稠密图的算法

screenshot

具体就是先构造一个邻接矩阵graph，然后传入，从source point出发，寻找距离自己最短的点，加入最小生成树的点集中，初始点初始化为0的权值。需要两个接口，一个是寻找最小的值，并且用bool标记访问，另一个是输出的函数print,主算法prim的函数，先初始化所有点未访问，然后循环n-1次（因为减去第一个点）直到所有点都已经进入点集（都被访问）为止。

具体代码：

#include <iostream>
#include <limits.h>

#define V 5

//MINKEY
int minKey(int key[], bool mstSet[]){
  //initialize min value
  int min = INT_MAX, min_index;

  for (int v = 0; v < V; v++){
    if (mstSet[v] == false && key[v] < min)
      min = key[v], min_index = v;
  }

  return min_index;
}

//PRINT
void printMST(int parent[], int n, int graph[V][V]){
  std::cout << "Edge  Weight n" << std::endl;
  for (int i = 1; i < V; i++)
    std::cout << parent[i] << " - " << i <<"    "<< graph[i][parent[i]]<<std::endl;
}

//PRIM_STM
void primMST(int graph[V][V]){
  int parent[V]; 
  int key[V];
  bool mstSet[V];

  for (int i = 0; i < V; i++)
    key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;//first node is alwasy root of MST

    for (int count = 0; count < V - 1; count++){
      //pick the minimum key vertex from the set of vertices
      //not yet included in MST
      int u = minKey(key, mstSet);

      mstSet[u] = true;

      for (int v = 0; v < V; v++)
      if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
        parent[v] = u, key[v] = graph[u][v];
    }
  printMST(parent, V, graph);
}

// driver program to test above function
void main()
{
  /* Let us create the following graph
 2    3
 (0)--(1)--(2)
 |   /    |
 6| 8/   5 |7
 | /      |
 (3)-------(4)
 9          */
  int graph[V][V] = { { 0, 2, 0, 6, 0 },
  { 2, 0, 3, 8, 5 },
  { 0, 3, 0, 0, 7 },
  { 6, 8, 0, 0, 9 },
  { 0, 5, 7, 9, 0 },
  };

  // Print the solution
  primMST(graph);

  system("pause");
}
  • KRUSKAL

因为Kruskal要用到并集内容，就给出介绍，算法我本身还没有自己实现过 ：（

克鲁斯卡尔算法是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

具体步骤可以去这个网站看看动态过程

下面是一个动态图：

screenshot

  • DIJKSTRA

思想和PRIM基本一样，不过这人蛮屌的，大家可以去查查。

screenshot

1.cpp

//Dijkstra's shortest path algorithm
#include <iostream>
#include <limits.h>

#define V 9

int minDistance(int dist[], bool sptSet[]){
  int min = INT_MAX, min_index = 0;

  for (int v = 0; v < V; v++)
  if (sptSet[v] == false && dist[v] <= min)
    min = dist[v], min_index = v;

  return min_index;
}

void printSolution(int dist[]){
  std::cout << "Vertex    Distance from Source" << std::endl;
  for (int i = 0; i < V; i++)
    std::cout << i << 't' << dist[i] << std::endl;
}

void Dijkstra(int graph[V][V], int src){
  int dist[V];   

  bool sptSet[V]; 

  for (int i = 0; i < V; i++)
    dist[i] = INT_MAX, sptSet[i] = false;

  dist[src] = 0;

  for (int count = 0; count < V - 1; count++)
  {

    int u = minDistance(dist, sptSet);

    sptSet[u] = true;

    for (int v = 0; v < V; v++)

      // Update dist[v] only if is not in sptSet, there is an edge from 
      // u to v, and total weight of path from src to  v through u is 
      // smaller than current value of dist[v]
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
      && dist[u] + graph[u][v] < dist[v])
      dist[v] = dist[u] + graph[u][v];
  }

  // print the constructed distance array
  printSolution(dist);
}

void main()
{
  /* Let us create the example graph discussed above */
  int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
  { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
  { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
  { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
  { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
  { 0, 0, 4, 0, 10, 0, 2, 0, 0 },
  { 0, 0, 0, 14, 0, 2, 0, 1, 6 },
  { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
  { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
  };

  Dijkstra(graph, 0);

  system("pause");
}

算法基本和prim的一致，就是最后是计算和的，不需要输出点的距离 另外youtube上面有很多dijkstra的教程，觉得教的还不错。链接。讲解得很棒。

还有一个MITOCW的也很好，老师是印度人，不过英语讲的很清晰。

  • FLOYD（Floyd–Warshall algorithm）

最后一个是FLOYD的，个人认为比较高明，比dijksta的好，但是就输在复杂度上面。复杂度是n^3.算法特别简单

具体步骤：来自百度（百度其实也不是一无是处的）

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

 

维基：

screenshot

主要思想是有一个k点，是i和j点的中间点，利用三个循环进行，当k从0开始，每个点都没有中间点，随着k越来越大，每个点之间都会有联系。

所以算法的核心其实只有五条：

    //Floyd-Warshall算法核心语句 
    for(k=1;k<=n;k++)   
       for(i=1;i<=n;i++)   
        for(j=1;j<=n;j++)   
           if(e[i][j]>e[i][k]+e[k][j] )   
               e[i][j]=e[i][k]+e[k][j];

三个循环，k是i和j的终点，如果ij原本距离大于加上k之后的距离，就更新ij之间的距离得到最小距离

完整代码：

#include <iostream>
#include <limits.h>

#define V 4
#define INF 9999
void printSolution(int dist[][V]);

void floydWarshell(int graph[][V]){
  int dist[V][V], i, j, k;

  for (i = 0; i < V;i++)
  for (j = 0; j < V; j++)
    dist[i][j] = graph[i][j];

  for (k = 0; k < V;k++)
  for (i = 0; i < V;i++)
  for (j = 0; j < V; j++)
  if (dist[i][k] + dist[k][j] < dist[i][j])
    dist[i][j] = dist[i][k] + dist[k][j];

  printSolution(dist);
}

void printSolution(int dist[V][V]){
  for (int i = 0; i < V; i++){
    for (int j = 0; j < V; j++){
       if (dist[i][j] == INF)
        std::cout << "INF"<<'t';
      else std::cout << dist[i][j]<<'t';
    }
    std::cout << std::endl;
  }
}

void main()
{
  /* Let us create the following weighted graph
 10
 (0)------->(3)
 |         /|
 5 |          |
 |          | 1
 |/         |
 (1)------->(2)
 3           */
  int graph[V][V] =
  { { 0, 5, INF, 10 },
  { INF, 0, 3, INF },
  { INF, INF, 0, 1 },
  { INF, INF, INF, 0 }
  };

  // Print the solution
  floydWarshell(graph);
  system("pause");
}

天啦噜，终于手工搞定！



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • What is Mathematics: Solution Chapter 3
  • What is Mathematics: Solution Chapter 2
  • What is Mathematics: Solution Chapter 1
  • A small guide to supplements: What you need to know
  • 混乱与秩序