图的邻接表存储实现:http://www.jb51.cc/article/p-nvwvgedf-bcb.html
图的邻接表DFS和BFS算法:http://www.jb51.cc/article/p-syijtjxb-bcb.html
这里则介绍图的另外一种存储方式:邻接矩阵。参考资料《大话数据结构》《C算法:卷二》
一、图的数据结构
图的邻接矩阵存储方式是用两个数据来表示。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边的信息。
见下图:(图片来源于《大话数据结构》)
/*图的邻接矩阵存储*/ typedef int VertexType; typedef int EdgeType; #define MAXVEX 100 #define INFI 65535 typedef struct { VertexType vexs[MAXVEX]; /*顶点表*/ EdgeType matrix[MAXVEX][MAXVEX]; /*邻接矩阵*/ unsigned int numVertexes; /*顶点数*/ unsigned int numEdges; /*边数*/ }Graph;二、创建一个图
/*创建一个邻接矩阵无向图*/ Graph* CreateGraph() { Graph *pGragh = new Graph; if (NULL == pGragh) return NULL; cout << "输入顶点数和边数:" << endl; cin >> pGragh->numVertexes >> pGragh->numEdges; for (int i = 0; i < pGragh->numVertexes; ++i)/*建立顶点表*/ (pGragh->vexs)[i] = i; for (int i = 0; i < pGragh->numVertexes; ++i)/*邻接矩阵初始化*/ { for (int j = 0; j < pGragh->numVertexes; ++j) { (pGragh->matrix)[i][j] = INFI; if (i == j) (pGragh->matrix)[i][j] = 0; } } for (int k = 0; k < pGragh->numEdges; ++k) { int i,j,w; cout << "输入边(vi,vj)上的下标i,下标j和权重w:" << endl; cin >> i >> j >> w; (pGragh->matrix)[i][j] = w; (pGragh->matrix)[j][i] = (pGragh->matrix)[i][j];//无向图是对称矩阵 } return pGragh; }
/*创建一个邻接矩阵有向图*/ Graph* CreateDiGraph() { Graph *pGragh = new Graph; if (NULL == pGragh) return NULL; cout << "输入顶点数和边数:" << endl; cin >> pGragh->numVertexes >> pGragh->numEdges; for (int i = 0; i < pGragh->numVertexes; ++i)/*建立顶点表*/ (pGragh->vexs)[i] = i; for (int i = 0; i < pGragh->numVertexes; ++i)/*邻接矩阵初始化*/ { for (int j = 0; j < pGragh->numVertexes; ++j) { (pGragh->matrix)[i][j] = INFI; if (i == j) (pGragh->matrix)[i][j] = 0; } } for (int k = 0; k < pGragh->numEdges; ++k) { int i,w; cout << "输入边<vi,vj>上的下标i,下标j和权重w:" << endl; cin >> i >> j >> w; (pGragh->matrix)[i][j] = w;//清楚上面输入的顺序,有向边的开始点和终点 } return pGragh; }三、检查图中两个顶点间是否有边
/*检查两个顶点之间是否有边 对于邻接矩阵存储图,这比较简单。其中有向图对输入顶点顺序有要求*/ bool GraphHasEdge(Graph *pGraph,unsigned int begin,unsigned int end) { if (NULL == pGraph || begin >= pGraph->numVertexes || end >= pGraph->numVertexes) return false; if (begin == end) return false; return ((pGraph->matrix)[begin][end] != INFI) ? true : false; }
四、DFS
关于DFS与BFS的介绍见开篇链接
/*DFS*/ /*邻接矩阵的深度优先递归算法*/ void DFSUtil(Graph *pGraph,int start,bool visited[]) { visited[start] = true; cout << start << endl; for (int j = 0; j < pGraph->numVertexes; ++j) { if ((pGraph->matrix)[start][j] != 0 && (pGraph->matrix)[start][j] != INFI && !visited[j]) DFSUtil(pGraph,visited); } } /*邻接矩阵的深度优先搜索*/ void DFS(Graph *pGraph) { if (NULL == pGraph) return; bool *visited = new bool[pGraph->numVertexes]; memset(visited,false,pGraph->numVertexes); for (int i = 0; i < pGraph->numVertexes; ++i) { if (!visited[i]) DFSUtil(pGraph,i,visited); } delete[] visited; }五、BFS
/*BFS*/ void BFS(Graph *pGraph) { if (NULL == pGraph) return; bool *visited = new bool[pGraph->numVertexes]; memset(visited,pGraph->numVertexes); list<int> queue;//利用链表构造一个队列 for (int i = 0; i < pGraph->numVertexes; ++i) { if (!visited[i]) { visited[i] = true; cout << pGraph->vexs[i] << endl; queue.push_back(i); while (!queue.empty()) { i = *queue.begin(); queue.pop_front(); for (int j = 0; j < pGraph->numVertexes; ++j) { if ((pGraph->matrix)[i][j] != 0 && (pGraph->matrix)[i][j] != INFI && !visited[j]) { visited[j] = true; cout << pGraph->vexs[j] << endl; queue.push_back(j); } } } } } }这里只提供相关代码实现,代码已测试,理论部分请参考相关资料。