图的概念及深度优先搜索和广度优先搜索

图是一种复杂的非线性结构。 图 G 是由两个集合 V(G) 和 E(G) 组成 的,记为 G=(V,E )  其中： V(G) 是顶点的非空有限集，   E(G) 是边的有限集合，边是顶点的无序对或有序对 一、有向图和无向图 无向图——无向图G是由两个集合V(G)和E(G)组成，   V(G) 是顶点的非空有限集， E(G) 是边的有限集合，边是顶 点的无序对，记为（ vi,vj ） 或（ vj,vi ) ， 并且（ vi,vj )=( vj,vi ) 有向图 —— 有向图 G 是由两个集合 V(G) 和 E(G) 组成，   V(G) 是顶点的非空有限集， E(G) 是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 < vi,vj > ， vi,vj 是顶点， vi 为弧尾， vj 为弧头。 例如：有向图 二、完全图 概念：图中任意两点之间恰有一条遍相连。 因此： 1、 有向完全图  : n 个顶点的有向图最大边数是 n(n-1)   （边是有方向的）            2、无向完全图 :n 个顶点的无向图最大边数是 n(n-1)/2 三、邻接点、度 邻接点 :  若(vi,vj)是一条无向边，则称vi和vj互为邻接点               （没有找到有向图的邻接点，我认为弧尾是弧头的连接点） 关联    :   vi和vj互为邻接点，称边(vi,vj)关联于顶点vi和vj 顶点的度 1、对于无向图，某顶点的度为与该顶点相连的边的数量 ,  记为 D(vi) 2、对于有向图，顶点的度分成 入度与出度，其中入度是以该顶点为头的弧的数目，记为ID(v)。出度是以该顶点为尾的弧的数目,记为OD(v)。顶点的度为入度和出度的和，即 D(v)=ID(v)+OD(v)。 不论是有向图还是无向图，边和度的关系： e = （d(v1) + d(v2) + ...d(vn)） / 2 子图： 四、路径和回路 路径        ： 存在顶点的序列 V={Vp,Vi 1 , …… Vi n ,Vq } ， 满足( Vp ,Vi 1 ),  ( Vi 1 ,Vi 2 ),  …  ,  ( Vi n , Vq ) 均属于边集 E (G), 则称 vp 到 vq 存在路径。 路径长度：沿路径边的数目 或沿路径各边权值之和。 回路       ： 第一个顶点和最后一个顶点相同的路径叫回路 简单路径 ： 序列中顶点不重复出现的路径叫简单路径 简单回路 ： 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路 五、连通图 连通       ： 从顶点 Vi 到顶点 vj 有一条路径，则说 Vi 和 vj 是连通的 连通图    ： 图中任意两个顶点都是连通的图叫 连通图 连通分量 ： 无向图中的 最大 ( 含的边和顶点最多 ) 连通 子 图 强连通图 ： 有向图中，如果对每一对属于顶点集合的Vi,Vj（ij不等）, ,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是强连通图 六：权和网、生成树 权    ： 与图的边或弧相关的数叫 权 网   ： 带权的图叫 网 七、生成树（ http://blog.csdn.net/heavenboya/article/details/6654778 ） 一个连通图的 生成树 是一个 极小连通子图 ，它含有图中全部顶点，但只有足以构成一棵树的 n-1 条边。 生成树算法： １、普里姆(Prim)算法：选择一个最小的边进行扩充（扩充时，选择两个顶点与其他权重最小的），直到生成一个最小连通子图 ２、 Kruskal算法　：　依次选择权重最小的边，直到生成最小连通子图 http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/flashhtml/kelusikaer.htm 一棵有 n 个顶点的生成树有且仅有 n-1 条边 有向树： 只有一个顶点的入度为 0 ，其余顶点的入度为 1 的有向图。 八：存储结构 ８.１　邻接矩阵（二维数组）      无向图：如果i和j有连接 Eij = Eji = 1 或者权重， 否则为0，（斜对称矩阵）。 行（列）非零元素个数，表示度            有向图：Eij  = 权重，如果有i到j直接连接的边。   行非零元素个数，表示出度；   列非零元素个数，表示入度      int A[n][n]; // n 为顶点的个数      特别是对于有向图，邻接矩阵极大浪费空间 8.2   邻接表（大部分用）空间复杂度 O(n+e) 邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。对于图G中每个顶点V i ，把所有邻接于V i 的顶点V j 链成一个单链表，这个单链表称为顶点V i 的邻接表。 对图中每个顶点建立一个邻接关系的 单 链表 ，并将其表头指针用向量 ( 一维数组 ) 存储 , 该结构称为邻接表 邻接表能很容易算出出度，如果用到入度，需要建立 逆邻接表 数据结构见下面代码 九、遍历 遍历有广度优先遍历（ breadth-first search， BFS ）和深度优先遍历（DFS），都用到数组来标记是否访问到。 （存储结构不确定，则遍历结果不唯一） 9.1 广度优先遍历 9.2 深度优先遍历 #include <iostream> #include <queue> #include <vector> #include <stack> using namespace std; // 每一个顶点的边链表 struct Edge { int verAdj; // 邻接点的序号 int cost; // 边的权值(顶点到这个点的) Edge *next; // 指向下一个边节点 Edge(int verVal, int costVal = 1) { verAdj = verVal; cost = costVal; next = NULL; } }; // 用数组存顶点节点 struct Vertex { int verName; // 顶点名称 Edge *adjacent; // 边链表的头指针 Vertex(){verName = 0; adjacent = NULL;} Vertex(int val) {verName = val; adjacent = NULL;} Vertex(int val, Edge *edge) { verName = val; adjacent = edge; } }; /** * 为了处理方便，verName与顶点数组的下表一样 * 否则还需要加一个数组，用来指示verName指向数组索引 */ class GraspList { private: Vertex *head; int graspSize; // 图点的个数 public: GraspList(int graspSize) { this->graspSize = graspSize + 1; // 目前 0到n是 n+1 个 this->head = new Vertex[this->graspSize]; for (int i = 0; i < this->graspSize; ++i) { this->head[i].verName = i; this->head[i].adjacent = NULL; } } void createGraspList() { int rows; cin >> rows; // 输入行数（边个数） for (int i = 0; i < rows; ++i) { int vBegin, vEnd; cin >> vBegin >> vEnd; Edge *edge = new Edge(vEnd); if (this->head[vBegin].adjacent == NULL) { this->head[vBegin].adjacent = edge; } else { Edge *tmpHead = this->head[vBegin].adjacent; while(tmpHead->next != NULL) { tmpHead = tmpHead->next; } tmpHead->next = edge; } } } /** * 宽度优先遍历, 利用队列,把每个没有访问的顶点入队列 * @param */ void bfs() { queue<Vertex> bfsQueue; queue<int> result; vector<int> visited(this->graspSize, 0); for (int i = 0; i < this->graspSize; ++i) { if (visited[i] == 1) { continue; } bfsQueue.push(this->head[i]); while (!bfsQueue.empty()) { Vertex tmp = bfsQueue.front(); bfsQueue.pop(); result.push(tmp.verName); visited[tmp.verName] = 1; Edge *tmpEdge = tmp.adjacent; while (tmpEdge != NULL) { int verName = tmpEdge->verAdj; if (visited[verName] == 0) { // 未被访问 bfsQueue.push(this->head[verName]); } tmpEdge = tmpEdge->next; } } }// end for while (!result.empty()) { cout << result.front() << "->"; result.pop(); } cout << endl; } /** * 深度优先遍历，利用栈，先把一个如栈，然后在对栈顶的节点进行 */ void dfs() { stack<Vertex> dfsStack; queue<int> result; vector<int> visited(this->graspSize, 0); for (int i = 0; i < this->graspSize; ++i) { if (visited[i] == 1) { continue; } dfsStack.push(this->head[i]); while (!dfsStack.empty()) { Vertex tmp = dfsStack.top(); dfsStack.pop(); result.push(tmp.verName); visited[tmp.verName] = 1; Edge *tmpEdge = tmp.adjacent; while (tmpEdge != NULL) { int verName = tmpEdge->verAdj; if (visited[verName] == 0) { dfsStack.push(this->head[verName]); } tmpEdge = tmpEdge->next; } } }// end for while (!result.empty()) { cout << result.front() << "->"; result.pop(); } cout << endl; } }; int main() { int verCount; // 顶点个数，从0开始 cin >> verCount; GraspList *gl = new GraspList(verCount); gl->createGraspList(); gl->bfs(); gl->dfs(); cout << "Hello World!" << endl; return 0; }