递归法dfs以邻接表表示的无向无权图

2024-04-12 21:20:38
完善数据结构：结点名字ElemType
　　上图：
　　上码：
  1 // vs 2015
  2 // 邻接表 无向不带权
  3 
  4 
  5 #include <iostream>
  6 #include <stack>
  7 
  8 using namespace std;
  9 #define MAX 10
 10 
 11 typedef int ElemType;            //结点被标记的类型
 12 //弧结点
 13 typedef struct ArcNode {
 14     ElemType name;                //与顶点相连的弧name
 15     struct ArcNode *next;        //下一个兄弟弧
 16 } ArcNode;
 17 //顶点信息
 18 typedef struct VNode {
 19     ElemType name;                //顶点被标记名字
 20     ArcNode * firstarc;            //顶点连接的第一条弧（左右不敏感）
 21 } VNode, AdjList[MAX];
 22 //邻接表
 23 typedef struct {
 24     AdjList vertinfo;            //hash表
 25     int vexnum;                    //顶点数
 26     int arcnum;                    //弧数
 27 } AdjGraph;
 28 
 29 
 30 int visited[MAX];
 31 void dfs_byecursion(AdjGraph G, ElemType stapos)
 32 {
 33     //-------增强健壮性，主要检测第一个stapos是否在图中------
 34 
 35     bool isIn = false;        //判断stapos结点是否在图中
 36     int pos = 0;            //记录结点在vertinfo中的索引
 37     for (int i = 0; i < G.vexnum; i++)
 38         if (stapos == G.vertinfo[i].name) {
 39             isIn = true;
 40             pos = i;
 41             break;
 42         }
 43     if (!isIn)
 44         return;                //不在图中，跳出
 45 
 46     visited[pos] = 1;        //若在图中，则操作此结点后进行标记
 47                             //此后pos无用，用来记录邻接点在vertinfo中的位置
 48     cout << G.vertinfo[pos].name << '\t';
 49         /*
 50             function();        //这里仅仅输出
 51         */
 52     //------------------------------------------------------
 53     
 54     ArcNode *temp;            //临时弧指针，指向stapos结点的邻接点
 55     temp = G.vertinfo[pos].firstarc;
 56     while (temp != NULL)
 57     {
 58         for (int i = 0; i < G.vexnum; i++) {
 59             if (temp->name == G.vertinfo[i].name)
 60             {
 61                 pos = i;
 62                 break;
 63             }
 64         }
 65         // temp->name 代表的是结点的邻接点名字，要判断visited则要找到在vertinfo中的下标
 66 
 67         //--------------------------------------------
 68         if (!visited[pos])
 69             dfs_byecursion(G, temp->name);
 70         temp = temp->next;
 71     }
 72 }
 73 void travelallnodes_dfs_byecrusion(AdjGraph G) {
 74     cout << "dfs all nodes :" << endl;
 75     int partnum = 1;
 76     for (int i = 0; i < G.vexnum; i++) {
 77         if (!visited[i]) {
 78             cout << "part " << partnum++ << " :" << endl;
 79             dfs_byecursion(G, G.vertinfo[i].name);
 80             cout << endl;
 81         }
 82     }
 83     cout << "-----dfs all nodes over!" << endl;
 84 }
 85 int main()
 86 {
 87     AdjGraph ag;
 88 
 89     ag.vexnum = 6, ag.arcnum = 5;
 90     ArcNode acn[10];
 91     ag.vertinfo[0].name = 1;
 92     acn[0].name = 2, acn[1].name = 3, acn[2].name = 5;
 93     ag.vertinfo[0].firstarc = &acn[0];
 94     acn[0].next = &acn[1], acn[1].next = &acn[2], acn[2].next = NULL;
 95     
 96     ag.vertinfo[1].name = 2;
 97     acn[3].name = 1, acn[4].name = 4;
 98     ag.vertinfo[1].firstarc = &acn[3];
 99     acn[3].next = &acn[4], acn[4].next = NULL;
100     
101     ag.vertinfo[2].name = 3;
102     acn[5].name = 1, acn[6].name = 5;
103     acn[5].next = &acn[6], acn[6].next = NULL;
104     ag.vertinfo[2].firstarc = &acn[5];
105     
106     ag.vertinfo[3].name = 4;
107     acn[7].name = 2, acn[7].next = NULL;
108     ag.vertinfo[3].firstarc = &acn[7];
109     
110     ag.vertinfo[4].name = 5;
111     acn[8].name = 3, acn[9].name = 1;
112     acn[8].next = &acn[9], acn[9].next = NULL;
113     ag.vertinfo[4].firstarc = &acn[8];
114     
115     ag.vertinfo[5].name = 5;
116     ag.vertinfo[5].firstarc = NULL;
117 
118     for (int i = 0; i < ag.vexnum; i++)
119         visited[i] = 0;        //初始化递归方法需要使用的visited全局数组
120     
121     //第二个参数：结点名字
122     dfs_byecursion(ag, 2);
123     travelallnodes_dfs_byecrusion(ag);
124 
125     return 0;
126 }
码农公寓
