数据结构--图(Graph)

定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的一种非线性表结构，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

• 顶点（vertex）：图中的元素。
• 边（edge）：图中的顶点与其他任意顶点建立连接的关系。
• 度（degree）：跟顶点相连接的边的条数。
• 入度（In-dedree）：以该顶点为终点的边的条数。
• 出度（Out-degree）：以该顶点为起点的边的条数。

完全图

无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

含有n个顶点的无向完全图有n×(n-1)/2条边

有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

含有n个顶点的有向完全图有n×(n-1)条边

连通图

如果从顶点v到顶点w之间有路径，则称顶点v和w连通。

连通图一般都是指无向图。

顶点数为n的连通图，至少有n-1条边。

强连通图

在有向图中，若从顶点v到w有路径，则称这两个顶点强连通。若任意一对顶点都是强连通的，称此图为强连通图。

顶点数为n的强连通图，最少有n条边。

图的表示

邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边信息。

无向图

有向图

使用邻接矩阵的存储方式比较简单、直接，且可以高效的获取两个顶点的关系；但是由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。这时，可以考虑使用邻接表表示法来存储图中的数据。

邻接表

图的顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。

邻接表存储起来比较节省空间，但是使用起来就比较耗时间。

当链表过长，为了提高查找效率，我们可以将链表换成其他更加高效的数据结构，如平衡二叉树（红黑树）、跳表、散列表等。

图的深度优先遍历

图的深度优先遍历，类似于树的先序遍历，主要思想是首先选择一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。

以无向图为例，深度优先搜索的算法步骤。

1. 选择起始节点 u，并将其标记为已访问。
2. 遍历当前节点 u 的所有未访问邻接节点。
3. 对每个未访问的邻接节点 v，从节点 v 出发继续进行深度优先搜索（递归）。
4. 如果节点 u 没有未访问的相邻节点，回溯到上一个节点，继续搜索其他路径。
5. 重复 2∼4 步骤，直到遍历完整个图或找到目标节点为止。

//递归实现
void DfsRecursive(int v)
{
	cout<<v<<" ";
    //将v标记为已读
	visited[v] = true;
 
	for (int i = 0; i < vertexNum; i++)
	{
        //选择一个没有被标记过的节点
		if ((arc[v][i] != 0 && arc[v][i] != inf) && visited[i] == 0)
		{
			DfsRecursive(i);
		}
	}
 
}
//非递归
void DFS(int v) {
    stack<int> st;
    st.push(v); // 将起始顶点压入栈中
 
    visited[v]=true // 标记起始顶点为已访问
 
    while (!st.empty()) {
        v = stack.top();
        stack.pop();
 
        cout << v << " "; // 访问顶点v
 
        // 遍历顶点v的所有邻接点
        for (int i = 0; i < vertexNum; i++)
	    {
            //选择一个没有被标记过的节点
		    if ((arc[v][i] != 0 && arc[v][i] != inf) && visited[i] == false)
		    {
			    st.push(i);
		    }    
	    }
        
    }
}

 深度优先搜索的时间复杂度为 O(E)，E 表示边的个数；空间复杂度为 O(V)，V 表示顶点的个数。

图的广度优先遍历

广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问，然后顺序访问v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。

步骤：

1. 将起始节点u 放入队列中，并标记为已访问。
2. 从队列中取出一个节点，访问它并将其所有的未访问邻接节点 v 放入队列中。
3. 标记已访问的节点 v，以避免重复访问。
4. 重复步骤 2∼3，直到队列为空或找到目标节点。

   void BFS(int v)
   {
   	queue<int> q;
   	q.push(v);
   	visited[v] = true;
   	while (!q.empty())
   	{
   		v = q.front();
           q.pop();
   		cout<<v<<" ";
   		for (int i = 0; i < vertexNum; i++)
   		{
   			if ((arc[v][i] !=0&&arc[v][i]!=inf) && visited[i] == false)
   			{
   				q.push(i);
   				visited[i] = true;
   			}
   		}
    
   	}
   	
   }