1 #include "000库函数.h"  2 //无向图  3   4 #define MAXSIZE 9 /* 存储空间初始分配量 */  5 #define MAXEDGE 15  6 #define MAXVEX 9  7 #define INFINITY 65535  8   9 typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ 10 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ 11  12 typedef char VertexType; /* 顶点类型应由用户定义 */ 13 typedef int EdgeType; /* 边上的权值类型应由用户定义 */ 14  15 struct MGraph {
   //临接矩阵参数 16     VertexType vexs[MAXVEX]; 17     EdgeType arc[MAXVEX][MAXVEX]; 18     int numVertexes, numEdges; 19 }; 20  21 struct EdgeNode {
   //邻接表 22     int adjvex;//节点 23     EdgeType wt;//权重 24     struct EdgeNode *next;//指针 25 }; 26  27 struct VertexNode {
   //顶点表节点 28     int in;//节点的入度 29     VertexType data; 30     EdgeNode *firstedge; 31 }; 32  33 struct GraphAdjList { 34     VertexNode adjList[MAXVEX]; 35     int numNodes, numEdges; 36 }; 37  38 void CreateMGraph(MGraph **G) { 39     (*G) = new MGraph; 40     (*G)->numEdges = 15; 41     (*G)->numVertexes = 9; 42     /* 读入顶点信息，建立顶点表 */ 43     (*G)->vexs[0] = 'A'; 44     (*G)->vexs[1] = 'B'; 45     (*G)->vexs[2] = 'C'; 46     (*G)->vexs[3] = 'D'; 47     (*G)->vexs[4] = 'E'; 48     (*G)->vexs[5] = 'F'; 49     (*G)->vexs[6] = 'G'; 50     (*G)->vexs[7] = 'H'; 51     (*G)->vexs[8] = 'I'; 52  53  54     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */ 55     { 56         for (int j = 0; j < (*G)->numVertexes; ++j) 57         { 58             (*G)->arc[i][j] = 0; 59         } 60     } 61  62     (*G)->arc[0][1] = 1; 63     (*G)->arc[0][5] = 1; 64  65     (*G)->arc[1][2] = 1; 66     (*G)->arc[1][8] = 1; 67     (*G)->arc[1][6] = 1; 68  69     (*G)->arc[2][3] = 1; 70     (*G)->arc[2][8] = 1; 71  72     (*G)->arc[3][4] = 1; 73     (*G)->arc[3][7] = 1; 74     (*G)->arc[3][6] = 1; 75     (*G)->arc[3][8] = 1; 76  77     (*G)->arc[4][5] = 1; 78     (*G)->arc[4][7] = 1; 79  80     (*G)->arc[5][6] = 1; 81  82     (*G)->arc[6][7] = 1; 83  84  85     for (int i = 0; i < (*G)->numVertexes; ++i)/* 初始化图 */ 86     { 87         for (int j = 0; j < (*G)->numVertexes; ++j) 88         { 89             (*G)->arc[j][i] = (*G)->arc[i][j]; 90         } 91     } 92  93 } 94  95  96 //构建临接表 97 void CreateALGraph(MGraph *G, GraphAdjList **GL) { 98     (*GL) = new GraphAdjList; 99     (*GL)->numEdges = G->numEdges;100     (*GL)->numNodes = G->numVertexes;101     for (int i = 0; i < G->numVertexes; ++i) {102         (*GL)->adjList[i].data = G->vexs[i];103         (*GL)->adjList[i].firstedge = NULL;104         (*GL)->adjList[i].in = 0;105     }106     for (int i = 0; i < G->numVertexes; ++i) {107         for (int j = 0; j < G->numVertexes; ++j) {108             if (G->arc[i][j] != 0) {109                 EdgeNode *p = new EdgeNode;110                 p->adjvex = j;111                 p->wt = 1;112                 p->next = (*GL)->adjList[i].firstedge;113                 (*GL)->adjList[i].firstedge = p;114                 (*GL)->adjList[i].in += 1;115             }116         }117     }118 119 }120 //深度遍历121 vector
     
      DFSRes;122 void DFS(GraphAdjList *GL, vector 
      
       &flag, EdgeNode *p) {123     if (DFSRes.size() == GL->numNodes)return;124     while (p) {125         if (flag[p->adjvex]) {126             DFSRes.push_back(GL->adjList[p->adjvex].data);//第一遍入栈，用来判断的127             flag[p->adjvex] = false;128             p = GL->adjList[p->adjvex].firstedge;//下一个点129             DFS(GL, flag, p);130             DFSRes.pop_back();//弹出栈，让后面回溯回来的元素入栈！131         }132         else133             p = p->next;134     }135 }136 137 void DFSTraverse(GraphAdjList *GL) {138     vector
       
        flag(GL->numNodes, true);//标志139     for (int i = 0; i < GL->numNodes; ++i) {140         DFSRes.push_back(GL->adjList[i].data);141         flag[i] = false;142         EdgeNode *p = GL->adjList[i].firstedge;143         DFS(GL, flag, p);144     }145     cout << "/*****DFS*****/" << endl;146     for (auto a : DFSRes)147         cout << a << "->";148     cout << endl;149 }150 151 152 //广度遍历153 vector
        
         BFSRes;154 deque
         
          dq;//压入节符号155 156 void BFS(GraphAdjList *GL, EdgeNode *p, vector
          
           &flag) {157 BFSRes.push_back(GL->adjList[dq.front()].data);158 dq.pop_front(); 159 while (p) {160 if (flag[p->adjvex]) { //未遍历过161 flag[p->adjvex] = false; 162 dq.push_back(p->adjvex); 163 }164 p = p->next;165 }166 if (dq.empty())return ;167 BFS(GL, GL->adjList[dq.front()].firstedge, flag);//下一个表168 }169 170 171 void BFSTraverse(GraphAdjList *GL) {172 vector
           
            flag(GL->numNodes, true);//访问标志173 dq.push_back(0);174 flag[0] = false;175 BFS(GL, GL->adjList[dq.front()].firstedge, flag);176 cout << "/*****BFS*****/" << endl;177 for (auto b : BFSRes)178 cout << b << "->";179 cout << endl;180 }181 182 183 184 int T023(void)185 {186 MGraph *G;187 GraphAdjList *GL;188 CreateMGraph(&G);189 CreateALGraph(G, &GL);190 191 //printf("\n深度遍历:");192 //DFSTraverse(GL);193 printf("\n广度遍历:");194 BFSTraverse(GL);195 return 0;196 }