图算是一种较复杂的数据结构了。图由 边的集合与顶点的集合 组成。关于图有许多种存储方式。在这一篇中，在深度优先搜索（DFS）和广度优先搜索（BFS）算法中，树用邻接表的方式存储。在最小生成树的Prim算法中，树用的时邻接矩阵的方式表示。
下面对Prim算法做一个简单的介绍。
Prim算法以点集合逐步扩展的方式选择连接它们的最小的边。
先指定一个点加入空集中，然后把连接它的最小边的另一个顶点加入集合中，在重复前一个步骤，逐步扩大直到所有的点都加入到了集合中。
#include < iostream > #include < queue > #include < string > using namespace std; /**/ ////error class // class BadOccur // { // public: // BadOccur(const string szErrorDescription) // { // m_szErrorDescription = szErrorDescription; // } // void BadOccurPrint() // { // cout << m_szErrorDescription << endl; // } // private: // string m_szErrorDescription; // }; // structure of the adjacent vertex nodes typedef struct TAdjVertexNode ... { int nAdjVertexNum; //sequence number of the adjacent vertex node struct TAdjVertexNode* pNextAdjVertex; //pointer of the next adjacent vertex node} TAdjVertexNode; // structure of the vertex nodes typedef struct TVertexNode ... { int nVertexNum; //sequence number of the vertex node struct TAdjVertexNode* pFirstAdjVertex; //pointer of the vertex's first adjacent node } TVertexNode;TVertexNode * CreatGraph( int NodesNum) ... { TVertexNode* pVertexArray = new TVertexNode [NodesNum + 1]; for (int i = 1; i <= NodesNum; i++) ...{ pVertexArray[i].nVertexNum = i; int nAmount = 0; cout << "Please give the number of adjacent nodes of the " << i << " th node" << endl; cin >> nAmount; if (0 == nAmount) ...{ pVertexArray[i].pFirstAdjVertex = NULL; } else ...{ TAdjVertexNode* pPreNode = NULL; for (int j = 1; j <= nAmount; j++) ...{ TAdjVertexNode* pNewNode = new TAdjVertexNode; cout << "Please enter the sequence number of the node." << endl; int nSequenceNum = 0; cin >> nSequenceNum; pNewNode->nAdjVertexNum = nSequenceNum; if (1 == j) ...{ pVertexArray[i].pFirstAdjVertex = pNewNode; } else ...{ pPreNode->pNextAdjVertex = pNewNode; } pPreNode = pNewNode; pNewNode->pNextAdjVertex = NULL; } } } return pVertexArray;} typedef void ( * TraverseMethod) (TVertexNode * , int , int * ); /**/ /** Function Name ：BFS* function ：broad traverse the graph from one vertex* detail ：none* author ：weixiong* time ：2007-2-1* return type ：void* return description : * function parameters ：TVertexNode* pVertexesArray the storage array of the graph * int nVertexSequenceNum sequence number of current vertex* int* pVertexesFlagArray the flag array of all the vertexes*/ void BFS(TVertexNode * pVertexesArray, int nVertexSequenceNum, int * pVertexesFlagArray) ... { queue<int> qAdjacentNodes; TAdjVertexNode* pCurrentNode = NULL; int nCurrentNodeNum = nVertexSequenceNum; cout << nCurrentNodeNum << " "; pVertexesFlagArray[nCurrentNodeNum] = 1; for (pCurrentNode = pVertexesArray[nCurrentNodeNum].pFirstAdjVertex; NULL != pCurrentNode; pCurrentNode = pCurrentNode->pNextAdjVertex) ...{ nCurrentNodeNum = pCurrentNode->nAdjVertexNum; cout << nCurrentNodeNum << " "; pVertexesFlagArray[nCurrentNodeNum] = 1; qAdjacentNodes.push(nCurrentNodeNum); } while (!qAdjacentNodes.empty()) ...{ pCurrentNode = pVertexesArray[nCurrentNodeNum].pFirstAdjVertex; if (pCurrentNode) ...{ nCurrentNodeNum = pCurrentNode->nAdjVertexNum; } for (; NULL != pCurrentNode; pCurrentNode = pCurrentNode->pNextAdjVertex) ...{ nCurrentNodeNum = pCurrentNode->nAdjVertexNum; if (0 == pVertexesFlagArray[nCurrentNodeNum]) ...{ cout << nCurrentNodeNum << " "; pVertexesFlagArray[nCurrentNodeNum] = 1; qAdjacentNodes.push(nCurrentNodeNum); } } nCurrentNodeNum = qAdjacentNodes.front(); qAdjacentNodes.pop(); }} /**/ /** Function Name ：DFS* function ：depth traverse the graph from one vertex* detail ：none* author ：weixiong* time ：2007-2-1* return type ：void* return description : * function parameters ：TVertexNode* pVertexesArray the storage array of the graph * int nVertexSequenceNum sequence number of current vertex* int* pVertexesFlagArray the flag array of all the vertexes*/ void DFS(TVertexNode * pVertexesArray, int nVertexSequenceNum, int * pVertexesFlagArray) ... { cout << pVertexesArray[nVertexSequenceNum].nVertexNum << " "; pVertexesFlagArray[nVertexSequenceNum] = 1; TAdjVertexNode* pCurrentVertex = pVertexesArray[nVertexSequenceNum].pFirstAdjVertex; int nCurrentVertexNum = 0; if (NULL != pCurrentVertex) ...{ nCurrentVertexNum = pCurrentVertex->nAdjVertexNum; } for (; NULL != pCurrentVertex; pCurrentVertex = pCurrentVertex->pNextAdjVertex) ...{ if (0 == pVertexesFlagArray[nCurrentVertexNum]) ...{ DFS(pVertexesArray, nCurrentVertexNum, pVertexesFlagArray); } }} /**/ /** Function Name ：DepthFirstTraveralGraph* function ：traverse graph using the depth first order* detail ：none* author ：weixiong* time ：2007-2-1* return type ：bool* return description : true two matrices has multiplied* false two matrices can't be multiplied* function parameters ：int nNodesNum number of all the vertexes* int* pVertexesFlagArray the flag array of all the vertexes* TVertexNode* pVertexesArray the storage array of the vertex*/ void DepthFirstTraveralGraph( int nNodesNum, int * pVertexesFlagArray, TVertexNode * pVertexesArray) ... { int nVertex = 1; TraverseMethod p = NULL; cout << "Please choose your traversal method: 1. BFS 2. DFS" << endl; int nChoice = 0; cin >> nChoice; while(nVertex != nNodesNum) ...{ int nCurrentVertex = pVertexesArray[nVertex].nVertexNum; if (0 == pVertexesFlagArray[nVertex]) ...{ switch (nChoice) ...{ case 1: BFS(pVertexesArray, nVertex, pVertexesFlagArray); break; case 2: DFS(pVertexesArray, nVertex, pVertexesFlagArray); break; default: cout << "Bad choice!" << endl; } } nVertex++; }} const int MAX = 100 ; // If it hasn't directly path from Vi to Vj, we denote value(Vi, Vj) = 100 const int VERNUM = 6 ; /* Function Name ：MiniSpanTree_Prim* function ：creat the minimal span tree* detail ：none* author ：weixiong* time ：2007-2-1* return type ：void* return description : * function parameters ：int ppGraphMatrix[][VERNUM] the storage of the orginal tree * int nVertexNum the vertexes number it has */ void MiniSpanTree_Prim( int ppGraphMatrix[][VERNUM], int nVertexNum) ... { ppGraphMatrix[0][0] = 1; int nRow = 0;//record row of the minimal edge int nCol = 0; for (int k = 0; k < nVertexNum - 1; k++) ...{ int nMinEdge = MAX;//record the minimal value for (int i = 0; i < nVertexNum; i++) ...{ if (1 == ppGraphMatrix[i][i]) ...{ for (int j = 0; j < nVertexNum; j++) ...{ if ((0 == ppGraphMatrix[j][j]) && (ppGraphMatrix[i][j] < nMinEdge)) ...{ nMinEdge = ppGraphMatrix[i][j]; nRow = i; nCol = j; } } } } ppGraphMatrix[nCol][nCol] = 1; if (nRow > nCol) ppGraphMatrix[nRow][nCol] = -ppGraphMatrix[nRow][nCol]; else ppGraphMatrix[nCol][nRow] = -ppGraphMatrix[nCol][nRow]; }} void PrintGraph( int ppGraphMatrix[][VERNUM]) ... { for (int i = 0; i < VERNUM; i++) ...{ for (int j = 0; j < VERNUM; j++) ...{ cout << ppGraphMatrix[i][j] << ' '; } cout << endl; }} typedef struct TEdge{ int nVertexBegin; int nVertexEnd; int nVertexValue; int nFlag;}TEdge; /* Function Name ：MiniSpanTree_Prim* function ：creat the minimal span tree* detail ：none* author ：weixiong* time ：2007-2-1* return type ：void* return description : * function parameters ：TEdge GraphEdgeArray[], the storage of the edges of the tree * TAdjVertexNode GraphVertexArray[] the storage of the vertexes array */ void MiniSpanTree_Kruskal(TEdge GraphEdgeArray[], TAdjVertexNode GraphVertexArray[]){ int nChosenEdges = 1; while (nChosenEdges < VERNUM) { int nMin = MAX; int nEdge = 0; int nEdgeBegin = 0; int nEdgeEnd = 0; for (int i = 1; i <= EDGENUM; i++) //search the minimal edge from the edges which were not chosen { if ((0 == GraphEdgeArray[i].nFlag) && (GraphEdgeArray[i].nVertexValue < nMin)) { nMin = GraphEdgeArray[i].nVertexValue; nEdge = i; nEdgeBegin = GraphEdgeArray[i].nVertexBegin; nEdgeEnd = GraphEdgeArray[i].nVertexEnd; } } //add the chosen edge's initial vertex to its terminal vertex's list TAdjVertexNode* pCurrentVertex = &GraphVertexArray[nEdgeBegin]; for (; (pCurrentVertex->pNextAdjVertex != NULL) && (pCurrentVertex->nAdjVertexNum != nEdgeEnd); pCurrentVertex = pCurrentVertex->pNextAdjVertex) {} if (NULL == pCurrentVertex->pNextAdjVertex) { TAdjVertexNode* pNewVertex = new TAdjVertexNode; pNewVertex->nAdjVertexNum = nEdgeEnd; pNewVertex->pNextAdjVertex = NULL; pCurrentVertex->pNextAdjVertex = pNewVertex; } //add the chosen edge's terminal vertex to its initial vertex's list pCurrentVertex = &GraphVertexArray[nEdgeEnd]; for (; (pCurrentVertex->pNextAdjVertex != NULL) && (pCurrentVertex->nAdjVertexNum != nEdgeBegin); pCurrentVertex = pCurrentVertex->pNextAdjVertex) {} if (NULL == pCurrentVertex->pNextAdjVertex) { TAdjVertexNode* pNewVertex = new TAdjVertexNode; pNewVertex->nAdjVertexNum = nEdgeBegin; pNewVertex->pNextAdjVertex = NULL; pCurrentVertex->pNextAdjVertex = pNewVertex; GraphEdgeArray[nEdge].nFlag = 1; nChosenEdges++; } }} int main() ... { //MiniSpanTree static int ppGraphMatrix[][VERNUM] = ...{ ...{0 ,6 ,1,5 ,MAX,MAX}, ...{6 ,0 ,5,MAX,3 ,MAX}, ...{1 ,5 ,0,5 ,6 ,4}, ...{5 ,MAX,5,0 ,MAX,2}, ...{MAX,3 ,6,MAX,0 ,6}, ...{MAX,MAX,4,2 ,6 ,0} }; MiniSpanTree_Prim(ppGraphMatrix, VERNUM); PrintGraph(ppGraphMatrix); //DestroyGraphMatrix(ppGraphMatrix, nVertexNum);//destory the storage matrix //ppGraphMatrix = NULL; //graph's edgesstatic TEdge GraphEdgeArray[EDGENUM + 1] ={{0, 0, 0, 0},//no use, convenient for count{1, 2, 6, 0},{1, 3, 1, 0},{1, 4, 5, 0},{2, 3, 5, 0},{3, 4, 5, 0},{2, 5, 3, 0},{3, 5, 6, 0},{3, 6, 4, 0},{4, 6, 2, 0},{5, 6, 6, 0}}; //graph's vertexesstatic TAdjVertexNode GraphVertexArray[VERNUM + 1] ={{0, NULL},//no use{1, NULL},{2, NULL},{3, NULL},{4, NULL},{5, NULL},{6, NULL}};MiniSpanTree_Kruskal(GraphEdgeArray, GraphVertexArray);for (int i = 0; i < EDGENUM + 1; i++){if (1 == GraphEdgeArray[i].nFlag){cout << GraphEdgeArray[i].nVertexValue << endl;}}getchar(); getchar(); //BFS and DFS cout << "Please enter the sequence number for all the vertexes in the graph." << endl; int nNodesNum = 0; cin >> nNodesNum; int *pVertexesFlagArray = new int [nNodesNum + 1]; for (int i = 1; i <= nNodesNum; i++) ...{ pVertexesFlagArray[i] = 0; } TVertexNode* pGraphStorageArray = CreatGraph(nNodesNum); DepthFirstTraveralGraph(nNodesNum, pVertexesFlagArray, pGraphStorageArray); getchar();} /**/ /*int** CreatGraphMatrix(int nVertexNum){int** ppGraphMatrix = new int* [nVertexNum];for (int i = 0; i < nVertexNum; i++){ppGraphMatrix[i] = new int [nVertexNum];for (int j = 0; j < nVertexNum; j++){cin >> ppGraphMatrix[i][j];}}return ppGraphMatrix;}void DestroyGraphMatrix(int** ppGraphMatrix, int nVertexNum){for (int i = 0; i < nVertexNum; i++){delete [] ppGraphMatrix[i];}ppGraphMatrix = NULL;}*/