大学院受験の復習(8)-図の基本的な操作

一.図の格納構造
1.臨接行列表示
2つの頂点にエッジがあるかどうかを確認しやすく、どれだけの頂点があるかを決定するには、全体図を巡回します.
稠密図に適合

#include <stdio.h> #include <stdlib.h> #define MAXVEX 100 #define inf 2000000000 typedef char vertexType; struct vertex {      int num;      vertexType data; }; typedef struct graph {      struct vertex vexs[MAXVEX];//vertex      int edges[MAXVEX][MAXVEX];//adjacency matrix }adjmax;

2.臨接表
無方向図にはn個の頂点があり、e個の辺があれば、臨接表にはn個の結点兄2 e個の表ノードが必要で、疎図に適している.
無方向図中のviの度はi番目のチェーンテーブルの結点数である.
図中のviへの出度はi番目のチェーンテーブルの結点数であり、入度を求めるには全図を遍歴する必要があり、逆臨接表を確立することができる.
いずれかの頂点の1番目の兄の隣接点と次の隣接点が見つかりやすいが、viとvjの間にエッジまたはアークがあるかどうかを検索するには、i番目またはj番目のチェーンテーブルを検索する必要がある.

#include <stdio.h> #include <stdlib.h> #define MAXVEX 100 #define inf 2000000000 typedef char vertexType; struct edgeNode{      int from;      int weight;      struct edgeNode *next;      vertexType data; }; typedef struct vexnode {      vertexType data;      int No;      struct edgeNode *link; }adjlist[MAXVEX];

二.二種類の遍歴
検索:
ツリーのようなルート遍歴

//deep first search void dfs(adjlist adj,int v,int visited[]) //adj is a adjlist, v is the No. of first point,visited is a assistant array  {      int i;      struct edgeNode *p;      visited[v]=1;      printf("[%d,%c]",v,adj[v].data);      p=adj[v].link;      while(p!=NULL)      {           if(visited[p->from]==0) dfs(adj,p->from,visited);           p=p->next;      } }

広く捜す
類似ツリーの階層遍歴
vにアクセスした後、アクセスされていない各臨接点に順次アクセスし、これらの臨接点から順次彼らの臨接点にアクセスする

//broad first search void bfs(adjlist adj,int v,int visited[]) {      struct edgeNode *p;      visited[v]=1;     int front=-1,rear=-1;      int i;     rear++;     printf("[%d,%c]",v,adj[v].data);     queue[rear]=v;     while(front!=rear)     {          front=(front+1)%MAXVEX;          i=queue[front];          p=adj[i].link;          while(p!=NULL)          {               if(visited[p->from]==0)               {                    printf("..%d,%d:
",p->from,visited[p->from]);                   visited[p->from]=1;                   printf("[%d,%c]",p->from,adj[p->from].data);                   rear=(rear+1)%MAXVEX;                   queue[rear]=p->from;               }               p=p->next;          }     }   }