import java.util.*;
public class Main{
static int MAX_VERTEXNUM = 100;
static int [] visited = new int[MAX_VERTEXNUM];
public static void main(String [] args){
Graph G = new Graph();
creatGraph(G);
output(G);
for(int i=0;i
visited[i]=0;
System.out.println("DFS周遊的結果是：");
dfs(G,0);//從G.node_list[0]開始DFS周遊
}
static void creatGraph(Graph G){
Scanner in = new Scanner(System.in);
System.out.println("請輸入頂點數v和邊數e,(v e):");
G.vertex_num = in.nextInt();
G.edge_num= in.nextInt();
System.out.println("請輸入各頂點資訊：");
for(int i=0;i
G.node_list[i] = new VertexNode();
G.node_list[i].date = in.next();
G.node_list[i].first_edge = null; //很重要
}
System.out.println("請輸入各邊資訊(以空格隔開)：");
for(int i=0;i
EdgeNode p = new EdgeNode();
String str1 = in.next();
String str2 = in.next();
int v1 = locateVex(G,str1);
int v2 = locateVex(G,str2);
p.vertex = v1;
p.next = G.node_list[v2].first_edge;
G.node_list[v2].first_edge = p;
EdgeNode q = new EdgeNode();//如果是有向圖，則不存在下面的代碼(上面的代碼的存儲順序可能有變化)
q.vertex = v2;
q.next = G.node_list[v1].first_edge;
G.node_list[v1].first_edge = q;
}
}
static int locateVex(Graph G,String s){
for(int i=0;i
if(G.node_list[i].date.equals(s))
return i;
}
return -1;
}
static void output(Graph G){
System.out.println("輸出鄰接表存儲情況：");
EdgeNode p = new EdgeNode();
for(int i=0;i
System.out.print(G.node_list[i].date);
p = G.node_list[i].first_edge;
while(p!=null){
System.out.print("->"+G.node_list[p.vertex].date);
p = p.next;
}
System.out.println();
}
}
static void dfs(Graph G,int k){
System.out.println(G.node_list[k].date);
visited[k]=1;
EdgeNode p = new EdgeNode();
p = G.node_list[k].first_edge;
while(p!=null){
if(visited[p.vertex]!=1)
dfs(G,p.vertex);
p = p.next;
}
}
}
//頂點存儲
class VertexNode{
String date;
EdgeNode first_edge = new EdgeNode();
}
//邊存儲
class EdgeNode{
int vertex;
EdgeNode next;
}
//圖存儲
class Graph{
VertexNode [] node_list = new VertexNode[100];
int vertex_num,edge_num;
}
//輸出結果：注意：(鄰接表的儲存順序與輸入邊的順序有關)
資料結構(11) -- 鄰接表存儲圖的DFS和BFS
/// //圖的鄰接表表示法以及DFS和BFS ...
PTA 鄰接表存儲圖的廣度優先周遊(20 分)
6-2 鄰接表存儲圖的廣度優先周遊(20 分) 試實作鄰接表存儲圖的廣度優先周遊. 函數接口定義: void BFS ( LGraph Graph, Vertex S, void (*Visit)(V ...
PTA 鄰接表存儲圖的廣度優先周遊
試實作鄰接表存儲圖的廣度優先周遊. 函數接口定義: void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ) 其中LGraph是鄰接表存儲的 ...
資料結構之---C語言實作圖的鄰接表存儲表示
// 圖的數組(鄰接矩陣)存儲表示 #include #include #include #defi ...
圖的鄰接表存儲表示(C)
//---------圖的鄰接表存儲表示------- #include #include #define MAX_VERTEXT_NUM ...
圖的鄰接表存儲 c實作
圖的鄰接表存儲 c實作 (轉載) 用到的資料結構是 一個是頂點表,包括頂點和指向下一個鄰接點的指針 一個是邊表, 資料結構跟頂點不同,存儲的是頂點的序号,和指向下一個的指針 剛開始的時候把頂點表初始化 ...
c++ 由無向圖構造鄰接表，實作深度優先周遊、廣度優先周遊。
#include #i ...
SDUT 2142 資料結構實驗之圖論二：基于鄰接表的廣度優先搜尋周遊
資料結構實驗之圖論二:基于鄰接表的廣度優先搜尋周遊 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Descript ...
DS實驗題 Old_Driver UnionFindSet結構 指針實作鄰接表存儲
題目見前文:DS實驗題 Old_Driver UnionFindSet結構 這裡使用鄰接表存儲敵人之間的關系,鄰接表用指針實作: // // main.cpp // Old_Driver3 // // ...
随機推薦
requerjs 合并 優化配置
/* * This is an example build file that demonstrates how to use the build system for * require.js. * ...
在IIS伺服器上部署svg/woff/woff2字型
在url沒錯的前提下,字型檔案報404錯誤,如.woff,.woff2 出錯原因: IIS不認SVG,WOFF/WOFF2這幾個檔案類型 解決方案: 在IIS伺服器上部署svg/woff/woff2字 ...
JQuery 定時器 (Jquery Timer 插件)
jQuery Timers插件位址: http://plugins.jquery.com/project/timers JQuery Timers應用知識提供了三個函式1. everyTime(時 ...
Dijkstra算法親自實踐
按路徑長度遞增次序産生算法: 把頂點集合V分成兩組: (1)S:已求出的頂點的集合(初始時隻含有源點V0) (2)V-S=T:尚未确定的頂點集合 将T中頂點按遞增的次序加入到S中,保證: (1)從源點 ...
CSU 1552: Friends 圖論比對+超級大素數判定
1552: Friends Time Limit: 3 Sec Memory Limit: 256 MBSubmit: 163 Solved: 34[Submit][Status][Web Boa ...
BZOJ 1620: [Usaco2008 Nov]Time Management 時間管理
Description Ever the maturing businessman, Farmer John realizes that he must manage his time effecti ...
移動周報：十款最實用的Android UI設計工具
上一周可以說是一個不斷Mark周,從最實用的Android UI設計工具.免費移動應用測試架構推薦,到HTML5開發架構等等,各種開發工具.架構精彩豐呈,看得小夥伴們是不亦樂乎.當然,還有不容錯過的M ...
Volist标簽 key值的使用
Volist标簽是thinkphp架構view中常用到的一個标簽.主要用于在模闆中循環輸出資料集或者多元數組.今天使用key屬性時出了點問題,記錄一下. volist标簽(循環輸出資料) 閉合 非閉合 ...
HTML學習(七)表格
表格表格由
| 标簽定義).字母 td 指表格資料(ta ... 無法通路 ASP 相容性模式 |