Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit a2bfa40

Browse filesBrowse files
mrzdevcoremrzdevcore
committed
dfs for oriented graph
1 parent 00f93a4 commit a2bfa40
Copy full SHA for a2bfa40

2 files changed

+105-13Lines changed: 105 additions & 13 deletions

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/algo.tex‎

Copy file name to clipboardExpand all lines: algorithm/algo.tex
+99-10Lines changed: 99 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -55,31 +55,120 @@ \subsubsection{DFS pour graphe non orienté}
5555

5656
On peut donc représenté l'algorithme comme suit:
5757

58+
%\renewcommand{\algorithmicforall}{\textbf{pour tout}}
59+
%\renewcommand{\algorithmicdo}{\textbf{faire}}
60+
%\renewcommand{\algorithmicif}{\textbf{si}}
61+
%\renewcommand{\algorithmicthen}{\textbf{alors}}
62+
63+
5864
%\begin{algorithm}
5965
%\caption{Depth First Search: graphe non orienté}
6066
%\begin{algorithmic}
6167
%\State $ARBRE \gets \emptyset$
6268
%\State $RETOUR \gets \emptyset$
69+
%\State $i \gets 1$
70+
%\ForAll{sommet dans G}
71+
% \State $sommet.pere \gets 0$
72+
% \State $sommet.k \gets 0$
73+
%\EndFor
74+
%
75+
%\ForAll{sommet dans G}
76+
% \If{ $ sommet.k = 0 $}
77+
% \State $i \gets i+1$
78+
% \State $sommet.dfn \gets i$
79+
% \State $sommet.k\gets 1$
80+
% \State $u \gets sommet$
81+
% \ForAll{$arête\ non\ examiné\ incident\ à\ sommet$}
82+
%
83+
%
84+
%
85+
% \EndFor
86+
% \EndIf
87+
%\EndFor
6388
%
6489
%
6590
%
6691
%\end{algorithmic}
6792
%\end{algorithm}
6893

69-
\begin{verbatim}
70-
ARBRE = []
71-
RETOUR = []
72-
i = 1
73-
pour tout sommet de G
74-
sommet.pere = 0
75-
sommet.k = 0
76-
fin pour
94+
%\begin{verbatim}
95+
%ARBRE = []
96+
%RETOUR = []
97+
%i = 1
98+
%pour tout sommet de G
99+
% sommet.pere = 0
100+
% sommet.k = 0
101+
%fin pour
102+
%
103+
%\end{verbatim}
104+
\begin{enumerate}
105+
\item Mettre $ARBRE \leftarrow\ \emptyset,\ RETOUR \leftarrow\ \emptyset\ et\ et\ i\leftarrow\ 1$. Pour tout sommet x de G, mettre $pere(x)\leftarrow 0$ et $k(x)\leftarrow 0$
106+
\item Choisir un sommet r pour lequel k(r)=0 (condition utile pour les graphes non connexes, voir étape 6). Mettre $DFN(r) \gets i,\ k(r) \gets 1,\ u \gets r$
107+
\item Si tous les arêtes incident à u sont tous examiné, va vers étape 5, ou alors choisir un arête e=(u,v) qui n'a pas été examiné
108+
\item On oriente l'arête e de u vers v et on le marque comme examiné
109+
\begin{enumerate}
110+
\item si k(v)=0, alors on met $i \gets i+1,\ DFN(v)\gets i,\ ARBRE\gets ARBRE \cup\{e\},\ k(v)\gets 1,\ pere(v)\gets u\ et\ u\gets v$, et retourne à l'étape 3
111+
\item si k(v)=1, alors on met $RETOUR\gets RETOUR\cup\{e\}$, et retourne à l'étape 3
112+
\end{enumerate}
113+
\item Si $pere(u)\neq 0$, alors $u\gets pere(u)$, et on retourne à l'étape 3
114+
\item (Seulement pour les graphes non connexe, pour qu'on puisse passé d'un composant à un autre.) Si il existe un sommet r tel que k(r)=0, alors $i\gets i+1$ et on retourne à l'étape 2.
115+
\item Stop
116+
\end{enumerate}
117+
118+
119+
120+
\subsubsection{DFS pour les graphes orientés}
121+
La DFS dans un digraphe G (connexe et acyclique) est similaire au cas d'un graphe non orienté. L'algorithme divise les arcs de G en quatre classes différentes. Si la recherche arrive à un arc e=(x,y) non examiné, alors les quatre classes possibles sont:
122+
\begin{enumerate}
123+
\item Si y n'a pas encore été visité, alors e est un arête de l'arbre de la DFS
124+
\item Si y a été visité, alors il y a trois cas possible:
125+
\begin{enumerate}
126+
\item y est un descendant de x dans le sous graphe induit par un arbre de la DFS existant, alors e est un arête avant et DFN(y)>DFN(x)
127+
\item x est descendant de y dans le sous graphe induit par un arbre de la DFS, alors e est un arête de retour et DFN(y)<DFN(x)
128+
\item x et y n'ont aucune relation par rapport à aucun arbre de la DFS existant. Alors e est un arête de travers et DFN(y)<DFN(x).(Note: il est impossible que DFN(y)>DFN(x))
129+
\end{enumerate}
130+
\end{enumerate}
131+
132+
Le sous graphe orienté de G induit par les arêtes de l'arbre est appelé forêt de la DFS (forêt orienté). Si DFN(y)>DFN(x) pour un arc(x,y), alors (x,y) est un arête avant ou bien arête de l'arbre de la DFS.
133+
Durant la recherche, il est facile de différentier ces deux cas puisque (x,y) est un arête de l'arbre si y n'a pas encore été visité, et arête avant sinon. Si DFN(y)<DFN(x), alors (x,y) est un arête de retour ou bien arête de travers. Durant la recherche, il est aussi facile de distinguer les deux puisque (x,y) est un arête de travers si y est complètement analysé, et arête de retour sinon.
134+
77135

78-
\end{verbatim}
136+
Dans la suite, pere, k, ARBRE et RETOUR sont définis comme précédemment. On a aussi deux nouveaux variables "AVANT" et "TRAVERS" et $$L(x)= \left\{
137+
\begin{array}{l l}
138+
1 & \quad \text{si le x est complètement analysé}\\
139+
0 & \quad \text{sinon}
140+
\end{array} \right. $$
141+
142+
On peut donc présenter l'algorithme comme suit:
79143
\begin{enumerate}
80-
\item Mettre $ARBRE \longleftarrow\ \emptyset\ et\ i\longleftarrow\ 1$,
144+
\item Mettre $ARBRE \leftarrow\ \emptyset,\ RETOUR \leftarrow\ \emptyset\ et\ et\ i\leftarrow\ 1,\ AVANT\gets\emptyset,\ TRAVERS\gets\emptyset$. Pour tout sommet x de G, mettre $pere(x)\leftarrow 0$, $k(x)\leftarrow 0,\ L(x)\gets0$
145+
\item Choisir un sommet r pour lequel k(r)=0. Mettre $DFN(r) \gets i,\ k(r) \gets 1,\ u \gets r$
146+
\item Si tous les arêtes sortant de u sont tous examiné, va vers étape 5, sinon choisir un arête e=(u,v) qui n'a pas été examiné
147+
\item Marque l'arc e comme examiné
148+
\begin{enumerate}
149+
\item si k(v)=0, alors on met $i \gets i+1,\ DFN(v)\gets i,\ ARBRE\gets ARBRE \cup\{e\},\ k(v)\gets 1,\ pere(v)\gets u\ et\ u\gets v$, et retourne à l'étape 3
150+
\item si k(v)=1 et DFN(v)>DFN(u), alors on met $AVANT\gets AVANT\cup\{e\}$, et retourne à l'étape 3
151+
\item si k(v)=1 et DFN(v)<DFN(u) et L(v)=0, alors on met $RETOUR\gets RETOUR\cup\{e\}$, et retourne à l'étape 3
152+
\item si k(v)=1 et DFN(v)<DFN(u) et L(v)=1, alors on met $TRAVERS\gets TRAVERS\cup\{e\}$, et retourne à l'étape 3
153+
\end{enumerate}
154+
\item Si $pere(u)\neq 0$, alors $u\gets pere(u)$, et on retourne à l'étape 3
155+
\item (Seulement pour les graphes non connexe, pour qu'on puisse passé d'un composant à un autre.) Si il existe un sommet r tel que k(r)=0, alors $i\gets i+1$ et on retourne à l'étape 2.
156+
\item Stop
81157
\end{enumerate}
82158

83159

160+
161+
162+
163+
164+
165+
166+
167+
168+
169+
170+
171+
172+
84173

85174

Collapse file

‎conf.tex‎

Copy file name to clipboardExpand all lines: conf.tex
+6-3Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,9 @@
22
%
33
%\usepackage{algorithmicx}
44
%
5-
%\usepackage{algorithm}
6-
%\usepackage[noend]{algpseudocode}
7-
%%\usepackage{algorithmic}
5+
\usepackage{algorithm}
6+
\usepackage[noend]{algpseudocode}
7+
%\usepackage{algorithmic}
8+
9+
%nécessaire pour numéroter jusqu'au paragraph
10+
\setcounter{secnumdepth}{4}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.