https://www.cnblogs.com/dzkang2011/p/graph_1.html
https://blog.csdn.net/lu_LLLR/article/details/82453722?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param
//A "Gang" is a cluster of more than 2 persons //who are related to each other with total relation weight being greater than a given threshold K // The weight of a relation // is defined to be the total time length of all the phone calls // made between the two persons // For each case, // the first line contains two positive numbers N and K (both less than or equal to 1000), // the number of phone calls and the weight threthold, respectively. // 8 59 //Then N lines follow, each in the following format: //Name1 Name2 Time // AAA BBB 10 // BBB AAA 20 // AAA CCC 40 // DDD EEE 5 // EEE DDD 70 // FFF GGG 30 // GGG HHH 20 // HHH FFF 10 //first print in a line the total number of gangs. //print in a line the name of the head and the total number of the members. //It is guaranteed that the head is unique for each gang. //In each gang, the one with maximum total weight is the head. // 2 // AAA 3 // GGG 3 #include <iostream> #include <map> using namespace std; const int maxn=10100; int n,k,numPerson=0;//边数 下限k 总人数numPerson int G[maxn][maxn]={0},weight[maxn]={0}; bool vis[maxn]={false};//标记是否被访问,初始化赋值为false,未访问 map<int,string>intToString;//编号->姓名 map<string,int>stringToInt;//姓名->编号 map<string,int>Gang;//head->人数 ///图的遍历，dfs你一定要传入id编号参数吧，深度啥的不一定 //返回姓名str对应的编号 //搞了半天，这是在对map进行操作啊！！！！！！！！！！map<string,int>map<int,string> int change(string str){ if(stringToInt.find(str)!=stringToInt.end()){//如果str已经出现过///map<string,int>stringToInt;//姓名->编号--AAA return stringToInt[str];//-----1 }else{ stringToInt[str]=numPerson;//str的编号是numPerson/map<string,int>stringToInt;//姓名->编号---AAA-1 intToString[numPerson]=str;//map<int,string>intToString;//编号->姓名----1-AAA return numPerson++;//1->2 } } //dfs访问单个连通块，nowVisit是当前访问的编号 //head为头目，numMember是成员编号，totalVaule为连通块的总边权 void dfs(int nowVisit,int& head,int& numMember,int& totalVaule){ numMember++;// vis[nowVisit]=true;//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 if(weight[nowVisit]>weight[head]){ head=nowVisit;//当前节点的点权大于头目的点权，则更新头目 } for(int i=0;i<numPerson;i++){//枚举所有人//。。。。。。。。。。。。。。。。。。。。。。。。。 if(G[nowVisit][i]>0){//如果nowVisit能到达i totalVaule+=G[nowVisit][i];//连通块的总边权增加该边权 G[nowVisit][i]=G[i][nowVisit]=0;//删除这条边，防止回头 if(vis[i]==false){//如果nowVisit能到达i,如果i没被访问，则递归访问i//。。。。。。。。。。。。。。。。。。。 dfs(i,head,numMember,totalVaule);//。。。。。。。。。。。。。。。。。。。。。。。。 } } } } //遍历整个图，获得每个连通块的信息 void dfsTravel(){ for(int i=0;i<numPerson;i++){//枚举所有人。。。。。。。。。。。。。。。。。。。。。。。。。。。。 if(vis[i]==false){//如果i没有被昂访问。。。。。。。。。。。。。。。。。。。。。。。。。。。 int head=i,numMember=0,totalVaule=0;//头目，成员数，总边权 dfs(i,head,numMember,totalVaule);//遍历i所在的连通块//。。。。。。。。。。。。。。。。。 if(numMember>2&&totalVaule>k){ //成员数>2并且总边权 //head人数为numMember Gang[intToString[head]]=numMember;//搞了半天，这是在对map进行操作啊！！！！！！！！！//map<string,int>Gang;//head->人数 } } } } int main() { int w; string str1,str2; cin>>n>>k;//8 59 for(int i=0;i<n;i++){ cin>>str1>>str2>>w;//2个端点和点权//AAA BBB 10 //----->点 int id1=change(str1);//将str1转换为编号id1//AAA-1//-------1 int id2=change(str2);//将str2转换为编号id2//BBB-2//-------2 //点---->点权 //邻接矩阵 weight[id1]+=w;//id1的点权增加w weight[id2]+=w;//id2的点权增加w G[id1][id2]+=w;//边id1->id2的边权增加w G[id2][id1]+=w;//边id2->id1的边权增加w } dfsTravel();//是遍历整个图的所有连通块，获取Gang的信息 cout<<Gang.size()<<endl; map<string,int>::iterator it; for(it=Gang.begin();it!=Gang.end();it++){ cout<<it->first<<" "<<it->second<<endl;//map<string,int>Gang;//head->人数 } return 0; }邻接矩阵C++实现：
#include <iostream> #include <cstdio> using namespace std; #define maxn 100 #define INF 1xffffff //预定于的最大值 int n, m; //顶点数、边数 int g[maxn][maxn]; //邻接矩阵表示 void Init() { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) g[i][j] = 0; //讲所有顶点度数置零，若为带权图，则置为INF } void Show() //打印邻接矩阵 { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) cout << g[i][j] << " "; cout << endl; } } int main() { int a, b; cout << "Enter n and m:"; cin >> n >> m; while(m--) { cin >> a >> b; //输入为边的始点、终点，若有权，还需输入权w g[a][b] = 1; //a、b间存在边，将g[a][b]置1，若有权，则将其置为权值 g[b][a] = 1; //对于无向图，还要插入边(b，a） } Show(); return 0; }邻接矩阵也可以用来表示加权图。例如，如果G=<V，E>是一个加权图，其权值函数为w，对于边（u，v）∈E，其权值w（u，v）就可以简单地存储在邻接矩阵的第u行第v列的元素中。如果边不存在，则可以在矩阵的相应元素中存一个NIL值，在很多问题中，对这样的元素赋0或∞会更为方便些。
int w; string str1,str2; cin>>n>>k;//8 59 for(int i=0;i<n;i++){ cin>>str1>>str2>>w;//2个端点和点权//AAA BBB 10 //----->点 int id1=change(str1);//将str1转换为编号id1//AAA-1//-------1 int id2=change(str2);//将str2转换为编号id2//BBB-2//-------2 //点---->点权 //邻接矩阵 weight[id1]+=w;//id1的点权增加w weight[id2]+=w;//id2的点权增加w G[id1][id2]+=w;//边id1->id2的边权增加w G[id2][id1]+=w;//边id2->id1的边权增加w }邻接矩阵法
用一维数组图中顶点的信息，用一个二维数组存储图中边的信息（各顶点之间的邻接关系）。存储顶点之间邻接关系的二维数组称为邻接矩阵。 对于带权图而言，若顶点vi,vj之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点vi和vj不相连，则用∞来表示这两个顶点之间不存在边 网的邻接矩阵表示（网就是带权的图）
无向图
#include <stdio.h> #include <string.h> #define MaxVertexNum 100 //顶点数目最大值 typedef char VertexType; //顶点的数据类型 typedef int EdgeType; //带权图中边上权值的数据类型 typedef struct { VertexType Vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表 int vexnum, edgenum; //图的顶点数和弧数 }MGraph; /**********创建无向图**********/ void create_Graph(MGraph *G) { int i, j; int start, end; //边的起点序号、终点序号 int numV, numE; int w; //边上的权值 printf("请输入所创建无向图的顶点数和边数(用空格隔开):"); scanf_s("%d%d", &numV, &numE); G->vexnum=numV; G->edgenum=numE; printf("\n"); //图的初始化 for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { if (i == j) G->Edge[i][j] = 0; else G->Edge[i][j] = 32767; } } //顶点信息存入顶点表 for (i = 0; i < G->vexnum; i++) { printf("请输入第%d个顶点的信息:",i+1); scanf_s("%d", &G->Vex[i]); } printf("\n"); //输入无向图边的信息 for (i = 0; i < G->edgenum; i++) { printf("请输入边的起点序号，终点序号，权值(用空格隔开)："); scanf_s("%d%d%d", &start, &end, &w); G->Edge[start -1][end -1] = w; G->Edge[end - 1][start - 1] = w; //无向图具有对称性 } } /***********打印出邻接矩阵*********/ void print_Matrix(MGraph G) { int i, j; printf("\n图的顶点为:"); for (i = 0; i < G.vexnum; i++) printf("%d ", G.Vex[i]); printf("\n输出邻接矩阵:\n"); printf("\t"); for (i = 0; i < G.vexnum; i++) printf("\t%8d", G.Vex[i]); for (i = 0; i < G.vexnum; i++) { printf("\n\n%8d", G.Vex[i]); for (j = 0; j < G.vexnum; j++) { if (G.Edge[i][j] == 32767) printf("\t%8s", "∞"); else printf("\t%8d", G.Edge[i][j]); } printf("\n"); } } void main() { MGraph G; create_Graph(&G); print_Matrix(G); system("pause"); }有向图 代码基本是一样的，只是对称的位置上权值不一样
/***********创建有向图************/ void create_Graph2(MGraph *G) { int i, j; int start, end; //边的起点序号、终点序号 int numV, numE; int w; //边上的权值 printf("请输入所创建有向图的顶点数和边数(用空格隔开):"); scanf_s("%d%d", &numV, &numE); G->vexnum = numV; G->edgenum = numE; printf("\n"); //图的初始化 for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { if (i == j) G->Edge[i][j] = 0; else G->Edge[i][j] = 32767; } } //顶点信息存入顶点表 for (i = 0; i < G->vexnum; i++) { printf("请输入第%d个顶点的信息:", i + 1); scanf_s("%d", &G->Vex[i]); } printf("\n"); //输入无向图边的信息 for (i = 0; i < G->edgenum; i++) { printf("请输入边的起点序号，终点序号，权值(用空格隔开)："); scanf_s("%d%d%d", &start, &end, &w); G->Edge[start - 1][end - 1] = w; //有向图只在这里不一样 //G->Edge[start -1][end -1] = w; //G->Edge[end - 1][start - 1] = w; //无向图具有对称性 } }深度优先遍历
/**********深度优先遍历*********/ int visitDFS[maxSize]; void DFS(MGraph G,int i)//某个顶点 { int j; visitDFS[i] = 1;//标记某个顶点访问过 printf("%d ", G.Vex[i]);//顶点编号0-->1 for (j = 0; j < G.vexnum; j++)//从某个顶点开始遍历图（每个顶点） //遍历每个的顶点范围大，需要条件有关系，没访问，不像v[i].size() //从u出发可以到达的所有顶点v //从v出发到达的所有顶点.. //.... { if (G.Edge[i][j] != 32767 && !visitDFS[j]) DFS(G, j);//递归访问j } } void DFSTraverse(MGraph G) { int i; //for (i = 0; i < G.vexnum; i++) //visitDFS[i] = 0; for (i = 0; i < G.vexnum; i++)//顶点数//遍历每个顶点 { if (!visitDFS[i]) DFS(G, i);//从某个顶点开始遍历图 } } //printf("请输入所创建有向图的顶点数和边数(用空格隔开):"); //scanf_s("%d%d", &numV, &numE); //G->vexnum = numV;//顶点数图的深度优先遍历DFS （邻接矩阵实现） 图的遍历是指从图中的某一顶点出发， 按照一定的策略访问图中的每一个顶点。每个顶点有且只能被访问一次。
它的遍历规则：先选择一个初始顶点，再规定一个方向，例如往右边一直遍历。于是就往右边一直走，把访问过的顶点做好标记，沿着右边访问完后，回溯到之前访问过的顶点，找找还有没有顶点没有访问的，当所有顶点被访问，完成遍历。
DFS是一个递归地将图中所有顶点访问的过程， 类似于树的前序遍历。
用邻接矩阵实现时需注意设置一个布尔类型的访问标志数组 visited
